Grafos: generalidades

Notas para el curso de Matemática Discreta 2021, dictado por

Mariana Haim y Leandro Bentancur.
(Extraido y adaptado de las notas del curso 2020)
Centro de Matemática.
Facultad de Ciencias - UdelaR

Para motivar este capı́tulo presentaremos dos problemas. El primero es un problema

célebre que data del siglo XVI y que, según se considera, da origen a la teorı́a de grafos.
El segundo es un problema lúdico que circula entre los escolares (o circulaba en alguna
época y alguna escuela).
1. Problema de los puentes de Königsberg
La ciudad de Königsberg (antigua capital de Prusia Oriental, hoy llamada Kaliningra-
do) estaba atravesada por el rı́o Pregel, sobre el que se disponı́an siete puentes como
se muestra a continuación:

En este escenario se plantea el siguiente problema: ¿Es posible recorrer todos los puentes
pasando por cada uno una única vez y terminando el recorrido en el punto de partida?
Es posible resolver el problema listando todos los posibles recorridos que no repitan
puentes y verificando si entre ellos hay uno que cumpla las condiciones. Sin embargo el
matemático suizo Leonard Euler dio una solución en el año 1736 (en una publicación
titulada Solutio problematis ad geometriam situs pertinentis) que puede generalizarse
a toda una familia de problemas similares a este.
El primer paso en el análisis del problema consiste en simplificar el contexto hasta que-
darse con los elementos esenciales del mismo. Observamos entonces que hay dos tipos
de objeto en el problema: las regiones y los puentes. Se puede entonces representar el
mapa anterior por medio de la siguiente figura, donde las regiones son representadas
por puntos y los puentes por aristas. A los efectos del problema que estamos conside-
rando no hay diferencia entre el mapa y esta figura (a la que vamos a denominar grafo,
o más especificamente en este caso, multigrafo).

En la actualidad, la disposición de los puentes es diferente a la descrita, por lo que el

problema ha cambiado. El lector puede plantearse entonces, además del propuesto, el
problema de los puentes de Kaliningrado.
2. Problema de la conexión de servicios básicos en el plano
Se disponen en un territorio plano tres casas y tres usinas de servicios públicos: agua,
telefonı́a y electricidad. El problema consiste en conectar las tres casas a los tres ser-
vicios mediante conectores independientes (cables o ductos) que no se corten entre sı́.
(Como nos encontramos en un mundo plano, no es posible pasar un cable por encima
de otro.)
Hay una diferencia esencial entre el primer problema y el segundo. Mientras que el
primero depende solamente de la estructura del grafo, es decir, de como están conec-
tados los puntos mediante aristas, en el segundo se agrega una nueva circunstancia:
el hecho de que el grafo está contenido en el plano. Veremos más adelante que estos
corresponden a dos tipos diferentes de problemas más generales y mostraremos sus
soluciones.

0.1. Primeras definiciones y ejemplos

Un grafo dirigido es un par (V, E) donde V es un conjunto finito al que llamamos
conjunto de vértices y E es un subconjunto de V × V al que llamamos conjunto de
aristas.
Observar que el conjunto de aristas es una relación en el conjunto de vértices. Tene-
mos una nueva representación (esta vez geométrica) de las relaciones definidas en un
conjunto. Por ejemplo, para el conjunto X = {x1 , x2 , x3 , x4 } podemos representar la re-
lación R = {(x1 , x1 ), (x1 , x2 ), (x2 , x3 ), (x2 , x4 ), (x3 , x1 ), (x3 , x4 ), (x4 , x1 ), (x4 , x2 )} como
sigue:
Nos interesa sobretodo definir grafos no dirigidos, es decir, que tengan aristas no orien-
tadas. Para esto debemos reemplazar los pares ordenados por pares no ordenados.
Dados dos conjuntos X e Y consideramos el conjunto

X · Y = {{x, y} : x ∈ X, y ∈ Y }.

Un grafo no dirigido (también llamado simplemente grafo) es un par (V, E) donde

V es un conjunto finito y E ⊂ V · V . Las aristas de la forma {x, x} = {x} se denominan
lazos
En general, usaremos la notación G = (V, E) tanto para grafos dirigidos como para
grafos no dirigidos. Escribimos también en este caso V (G) = V y E(G) = E.

Decimos que dos vértices x y y de un grafo G (no dirigido) son adyacentes si {x, y}
es una arista del grafo.

Una arista del tipo {x} (o (x, x) para el caso dirigido) se dice lazo.
Dado un grafo G = (V, E) sin lazos y un vértice v ∈ V , el grado de v se define como

gr(v) = #{w ∈ V | v y w son adyacentes}

Notar que el grado de un vértice v coincide con la cantidad de aristas e tales que
v ∈ e. El primer resultado, simple y útil en Teorı́a de grafos es el que se conoce como
Hand-shaking Lemma o Lema del apretón de manos.

Lema 0.1.1. Lema de hand-shaking Dado un grado G = (V, E) sin lazos, se tiene la
siguiente igualdad X
gr(v) = 2#E
v∈V
Demostración. Cada sumando de la izquierda coincide con la cantidad de aristas que
“tocan.a v. En la suma, cada arista {v, w} está considerada dos veces, una en gr(v)
y otra en gr(w), por lo que el término de la izquierda es exactamente el doble de la
cantidad total de aristas.

La definición de grado de un vértice se extiende al caso de grafos (con eventuales lazos)

y también de multigrafos, y vale el lema de hand-shaking, como veremos en el próximo
capı́tulo.

0.1.1. Isomorfismos de grafos

Sean G1 = (V1 , E1 ) y G2 = (V2 , E2 ) dos grafos. Una función f : V1 → V2 es un
isomorfismo de grafos si

(i) f es biyectiva, y

(ii) {x, y} ∈ E1 si y sólo si {f (x), f (y)} ∈ E2 . Es decir, dos vértices son adyacentes
si y sólo si sus imágenes por f lo son.

Observar que si f : V1 → V2 es un isomorfismo de grafos, entonces queda definida una

función biyectiva f : E1 → E2 (usamos la misma notación que para la función en los
vértices) que asocia a la arista {x, y} ∈ E1 la arista {f (x), f (y)} ∈ E2 . Luego notamos
al isomorfismo por f : G1 → G2 entendiendo esto como una correspondencia tanto entre
lo vértices como entre las aristas de ambos grafos. Emplearemos la notación G1 ∼ = G2
para indicar que ambos grafos son isomorfos, es decir, si existe un isomorfismo entre
ellos.

Ejemplo 0.1.2. Consideramos los siguientes grafos:

V1 = {2, 3, 4, 5, 6} y E1 definido por x e y son adyacentes si x e y tienen algún

divisor primo en común.

V2 = {a, b, c, d, e} y E2 = {{a, b}, {a, c}, {a, e}, {b, c}}.

Definimos f : V1 → V2 por f (2) = c, f (3) = e, f (4) = b, f (5) = d y f (6) = a. Puede

verse que f es un isomorfismo entre los grafos G1 = (V1 , E1 ) y G2 = (V2 , E2 ).
Observar que f no es el único isomorfismo entre ambos grafos. Por ejemplo uno puede
considerar g : V1 → V2 por g(2) = b, g(3) = e, g(4) = c, g(5) = d y g(6) = a. ¿Hay
algún otro isomorfismo?

Si G1 y G2 son grafos dirigidos, entonces la definición de isomorfismo es análoga. La

única modificación que hay que hacer es cambiar los pares en (ii) por pares ordenados.
En general nos interesarán, más que los grafos, las clases de isomorfismo de grafos.
Por ejemplo, al mirar los grafos del Ejemplo 0.1.2, veremos los números y las letras
simplemente como puntos que están unidos de a pares, sin importar el nombre de los
vértices o la representación de las aristas.
Un grafo G = (V, E) se dice completo si E = (V · V ) \ D, donde

D = {{x, x} : x ∈ V }

es el conjunto de los lazos en V . Es decir que es el grafo sin lazos de vértices V con el
máximo número de aristas. Podemos observar que la clase de isomorfismo de un grafo
completo sólo depende del número de vértices, es decir para cada n ≥ 1 todos los grafos
completos con n vértices son isomorfos. Luego notamos por Kn a cualquiera de ellos
(o a todos ellos).
Un grafo G = (V, E) es bipartito si V = V1 ∪V2 con V1 ∩V2 = ∅ y E = V1 ·V2 . Haciendo
la misma consideración que para el grafo completo, ponemos la notación Kn,m para
referirnos al grafo bipartito con vértices V = V1 ∪ V2 con #V1 = n y #V2 = m.

0.1.2. Subgrafos
Sea G = (V, E) un grafo (o grafo dirigido). Decimos que el grafo G0 = (V 0 , E 0 ) es un
subgrafo de G si V 0 ⊂ V y E 0 ⊂ E. Si fijamos un grafo (o grafo dirigido) G, podemos
notar el conjunto de los subgrafos de G como S(G) y definir en este la siguiente relación
de orden:
G1 ≤ G2 ⇔ G1 es subgrafo de G2 .
Puede verse que en general esta relación de orden no es total y que tiene al grafo vacı́o
como mı́nimo y al grafo G como máximo.
Un encaje de un grafo G1 = (V1 , E1 ) en otro grafo G2 = (V2 , E2 ) es una función
inyectiva f : V1 → V2 tal que si {x, y} ∈ E1 , entonces {f (x), f (y)} ∈ E2 . Denotamos
también al encaje por f : G1 → G2 , y por f : E1 → E2 a la función inducida en las
aristas. De forma similar se define un encaje de un grafo dirigido en otro.
Dados dos grafos (o grafos dirigidos) G1 y G2 escribimos

G1  G2 ⇔ existe un encaje de G1 en G2 .

Observación 0.1.3. La relación  es reflexiva y transitiva pero no es antisimétrica.

De todas maneras se tiene un resultado en la dirección de la antisimetrı́a que es el
siguiente:
G1  G2  G1 ⇒ G1 ∼ = G2
En efecto, probaremos que el encaje f : G1 → G2 es un isomorfismo: como hay una
función inyectiva (f ) de V1 a V2 y una función inyectiva (g) de V2 a V1 , se deduce que
#V1 = #V2 y por tanto f : V1 → V2 es biyectiva.
Por otra parte, notar que f induce una función fE : E1 → E2 definida por f ({x, y}) =
{f (x), f (y)}. Es claro que fE es inyectiva. De la misma manera se tiene una función
inyetiva gE : E2 → E1 . Se deduce que #E1 = #E2 y por lo tanto fE es biyectiva. A
partir de esto es claro que f es un isomorfismo.

Proposición 0.1.4. Se tiene que G1  G2 si y sólo si existe G01 un subgrafo de G2 que

es isomorfo a G1 .

Demostración.
(⇒) Supongamos que tenemos G1 = (V1 , E1 ) y G2 = (V2 , E2 ), y que f : G1 → G2 es
un encaje. Luego definimos el subgrafo G01 = (f (V1 ), f (E1 )). Es claro por la definición
de encaje que f define un isomorfismo entre G1 y G01 .
(⇐) Un isomorfismo f : G1 → G01 (con G02 ≤ G2 ) se extiende de forma obvia a un
encaje f : G1 → G2 .

Sea G = (V, E) un grafo (o grafo dirigido) y V 0 ⊂ V un subconjunto cualquiera. El

subgrafo inducido por V 0 es el máximo (bajo el orden ≤ definido al comienzo de esta
sección) subgrafo de G que tiene a V 0 como conjunto de vértices.

En la siguiente figura puede verse el grafo inducido por los vértices b, c y d de un grafo
G = (V, E) con V = {a, b, c, d, e, f } y E = {{a, f }, {b, c}, {b, e}, {c, d}, {d, e}, {d, f }}.
Definimos el complemento de un grafo sin lazos G = (V, E) como el grafo

Gc = (V, (V · V ) \ (E ∪ D)),

donde D es el conjunto de lazos en V . Es decir que es el grafo que resulta de sacarle a

Kn las aristas de G, donde n = #V .

0.1.3. Multigrafos
Volvamos al problema de los puentes de Königsberg y a la forma de modelarlo.
Como podemos ver, hay dos aristas entre 1 y 2 y dos aristas entre 2 y 3, luego la figura
anterior no se ajusta a nuestra definición de grafo. Haremos entonces las siguientes
definiciones:
Un multigrafo es un par G = (V, E) donde V es un conjunto finito y E es un subcon-
junto finito de (V · V ) × N.
Un multigrafo dirigido es un par G = (V, E) donde V es un conjunto finito y E es
un subconjunto finito de (V × V ) × N.

Las definiciones generales dadas anteriormente pueden extenderse (tanto en el caso

dirigido como en el caso no dirigido) para definir:
 isomorfismo de multigrafos,

encaje de un multigrafo en otro,

sub-multigrafo, y

sub-multigrafo inducido por un subconjunto de vértices.

No lo hacemos para no entrar en detalles técnicos, pero invitamos al lector interesado

a intentarlo.

0.2. Caminatas en grafos

Un camino en un grafo G = (V, E) es una secuencia de vértices (x0 , x1 , . . . , xn ) tal
que {xi−1 , xi } ∈ E para todo i = 1, . . . , n. En este caso decimos que el camino une x0
con xn . Si x0 = xn el camino se dice cerrado.

La longitud del camino es, en este caso, el número n (la cantidad de aristas por las
que se pasa). El camino cerrado (x0 ) se dice trivial y su longitud es 0.
Decimos que un camino es un recorrido si no repite aristas, y que es un camino
simple si no repite vértices con excepción de que se repitan los extremos.
Llamaremos circuito a un recorrido cerrado y ciclo a un camino simple cerrado.
Observar que un camino simple abierto (no cerrado) es un recorrido. También sucede
que un ciclo de longitud mayor o igual a tres es un circuito.
Observar que las definiciones de arriba valen tanto para grafos como para grafos diri-
gidos.
Para dar un camino en un multigrafo, debemos especificar cuál de las aristas se toma
al unir dos vértices adyacentes. Teniendo esto en cuenta definimos un camino en un
multigrafo G = (V, E) como una secuencia

(x0 , e0 , x1 , e1 , . . . , en−1 , xn )

donde x1 , . . . , xn ∈ V y para cada i = 0, . . . , n − 1, ei es una arista que une xi con xi+1 .

Para multigrafos dirigidos la definición es análoga.

También de manera análoga, se definen camino, recorrido, circuito, camino simple

y ciclo en multigrafo o en un multigrafo dirigido.
Enunciamos y probamos el siguiente resultado para grafos, aunque vale (y la prueba
también) para grafos dirigidos, multigrafos, multigrafos dirigidos.

Proposición 0.2.1. Sea G = (V, E) un grafo y x, y ∈ V . Si existe un camino que une

x con y, entonces existe un camino simple que une ambos puntos.

Demostración. Supongamos que tenemos un camino de largo n desde x a y. Conside-

ramos entonces el conjunto de todos los caminos de x a y con longitud menor o igual
a n, al que notamos por Cn . Es claro que este conjunto es no vacı́o, además es finito
porque V es finito. Luego existe un camino c = (x = x0 , x1 , . . . , xk = y) que minimiza
la longitud de todos los elementos de Cn .
Si c no es un camino simple, entonces existen dos ı́ndices diferentes i, j ∈ {0, . . . , k}
tal que xi = xj . Sin pérdida de generalidad, podemos suponer i < j.
Si j < n, podemos observar que c0 = (x0 , . . . , xi , xj+1 , . . . , xk ) es un camino en Cn de
longitud estrictamente menor a k.
Si j = n, se tiene que i 6= 0 (la repetición es xi = xn ) y por tanto el camino
c0 = (x0 , . . . , xi ) es un camino en Cn de longitud estrictamente menor a k.
En ambos casos, se construyó un camino c0 en Cn de longitud estrictamente menor a
k, lo que contradice el hecho de que k es el mı́nimo de las longitudes de los caminos en
Cn .
Concluimos entonces que c debe ser un camino simple.

0.3. Conexión
Diremos que un grafo G = (V, E) es conexo si para todo par de vértices x, y ∈ V ,
existe un camino que los une.
Dado un grafo G = (V, E), podemos definir la relación R en el conjunto de los vértices
de la siguiente manera:

xRy ⇔ existe un camino que une x con y.

La componente conexa de un vértice v ∈ V es el subgrafo de G inducido por el
subconjunto de vértices
V 0 = {x ∈ V | existe un camino de x a v}.

Usaremos la notación κ(G) para indicar el número de componentes conexas del grafo
G, que coincide con el cardinal del cociente V /R. Observar que G es conexo si y sólo
si κ(G) = 1.

Puede observarse que la relación R es de equivalencia cuyas clases de equivalencia son

exactamente las componentes conexas (se deja como ejercicio).
La definición de conexión y de componente conexa vale para multigrafos. También vale
que la relación R es de equivalencia.
Sin embargo, en el caso dirigido cambia un poco la situación.
Un grafo (o multigrafo) dirigido G se dice conexo si el grafo (multigrafo) que resulta
de quitarle el sentido a las flechas de G es conexo.
Al grafo considerado en la definición anterior se lo llama grafo subyacente de G.
Para definir componente conexa en el caso dirigido, también se considera el grafo
(multigrafo) subyacente.
La relación R para grafos (multigrafos) dirigidos se define de la misma manera y es
claro que no es simétrica. Se tiene un resultado bien diferente en este caso.
Observación 0.3.1. Si G = (V, E) es un grafo dirigido sin ciclos,la relación R es de
orden.
Por otro lado, un conjunto ordenado puede verse como un grafo dirigido sin ciclos
(sacando los lazos). Sin embargo, si ≤ es una relación de orden en V , entonces existe
más de un grafo que genera ≤. En efecto, los siguientes grafos dirigidos generan la
misma relación de orden R.
Hay una noción de componente conexa en grafos dirigidos, pero su definición es un
poco más técnica y no la presentaremos aquı́ .

0.4. Distancia
Hay una noción de distancia natural en los grafos conexos que está relacionada con la
noción de longitud: para un par de vértices x, y ∈ V tomamos C(x, y) el conjunto de
los caminos que unen a x con y, luego definimos
dist(x, y) = mı́n{long(c) : c ∈ C(x, y)}.
Observación 0.4.1. En general, una distancia o métrica en un conjunto X es una
función d : X × X → [0, +∞) que cumple:

d(x, y) = 0 si y sólo si x = y.
d(x, y) = d(y, x) para todo par de puntos x, y ∈ X.
Dados tres puntos x, y, z, se cumple d(x, z) ≤ d(x, y) + d(y, z). (Esta es la des-
igualdad triangular.)

Luego dist : V × V → N es efectivamente una distancia.

Si G = (V, E) es un grafo dirigido y definiéramos análogamente dist, no resultarı́a una

distancia en V , ya que no se cumple la segunda condición de la Observación 0.4.1.