Teoría de grafos

DM – p.1/82
 Teoría de grafos

Contenidos
1. Nociones generales
• Notación y definiciones básicas
• Grafos dirigidos
• Árboles. Árbol generador de peso mínimo (algoritmos de Kruskal y Prim)
2. Grafos planos, eulerianos y hamiltonianos
• Grafos planos. La fórmula de Euler. El teorema de Kuratowsky
• Grafos eulerianos (algoritmo de Fleury)
• Grafos hamiltonianos
• Emparejamientos en grafos
3. Coloraciones y Caminos mínimos
• Coloraciones en grafos (algoritmo voraz)
• Caminos de longitud mínima (algoritmo de Dijkstra)

DM – p.2/82
 Teoría de grafos

Aplicaciones prácticas:
• Algoritmos en informática.
• Estructura de datos.
• Diseño de circuitos, redes de transporte, redes informáticas, etc.
• Encontrar una ruta que nos conduzca a los sitios más interesantes de París sin
repetir calles.
• Encontrar el vuelo Madrid–Tokio más barato o el más rápido o el que tenga
menos transbordos.
• Diseñar un circuito con el menor número de puntos “débiles”.
• Diseñar una red que maximice la salida de información.

DM – p.3/82
 Motivación

Problema 1
El primer dı́a de curso se encuentran en una clase 121 alumnos. Demostrar que siempre existe
una persona que conoce a un número par de personas.

¿Cómo describir eficientemente el problema?

Planteamiento:

1. Los alumnos son puntos •.

2. El conocimiento es mutuo y cero es par.
3. Si dos alumnos se conocen trazo una línea entre los correspondientes puntos:

El problema es equivalente a probar que en un grafo con 2n + 1 puntos, existe al menos

un punto con un número par de líneas que salen de él.

DM – p.4/82
 Grafos no orientados: definición

Definición 1
Un grafo simple G = (V, E) está compuesto por un conjunto no vacı́o de vértices V y un
conjunto de aristas E , que es un conjunto de pares de elementos distintos de V .

Si la arista e une los vértices (también llamados nodos o puntos) u, v ∈ V , diremos que
u y v son adyacentes o vecinos y que la arista e es incidente con u y v.

Definición 2
Un multigrafo G = (V, E) está compuesto por un conjunto no vacı́o de vértices V , un
conjunto de aristas E en el que se permite que haya aristas múltiples (que son aquellas
que conectan el mismo par de vértices).

Definición 3
Un lazo o bucle (“loop”) es una arista que une un vértice consigo mismo. Un pseudografo
G = (V, E) es un grafo en el que se permiten aristas múltiples y bucles.

Ejemplos:

DM – p.5/82
 Definiciones

Definición 4
El número de aristas incidentes con un vértice v de un grafo G se denomina grado o valencia
de v y se denota por d(v).

Nota: Los lazos contribuyen con dos unidades al grado del vértice correspondiente.

Definición 5
Los vértices de grado 1 se denominan terminales. Los vértices de grado 0 se denominan
aislados. Un grafo sin aristas se denomina trivial.

Ejemplos: b c b c b c

a a a

(1) d(a) = 1 d(b) = 4 d(c) = 3

(2) d(a) = 1 d(b) = 2 d(c) = 3
(3) d(a) = 1 d(b) = 2 d(c) = 1

DM – p.6/82
 Algunos teoremas sencillos

Teorema 6 La suma de los grados de los vértices de un grafo G = (V, E) es dos veces el
número de aristas. Es decir:
X
d(i) = 2|E| .
i∈V

Nota: Esto es cierto para pseudografos y multigrafos.

Corolario 7 En todo grafo G la suma de los grados de sus vértices es par.

Teorema 8 El número de vértices de grado impar en un grafo G es par.

D EMOSTRACI ÓN : Si
Vpar y Vimpar son los subconjuntos de vértices con grado par e impar
respectivamente, entonces el teorema anterior implica que
X X X
2|E| = d(i) = d(i) + d(i) .
i∈V i∈Vpar i∈Vimpar

Claramente d(i) es par, luego d(i) debe ser par. Por lo tanto, el número de
P P
i∈Vpar i∈Vimpar
vértices de grado impar debe ser par. 
DM – p.7/82
 Algunos teoremas sencillos

Corolario 9 En todo grafo G con número impar de vértices hay un número impar de vértices
de grado par.

D EMOSTRACI ÓN : El
teorema anterior implica que el número de vértices de grado impar
siempre es par. Si el número total de vértices es también impar, entonces el número de
vértices de grado par debe ser impar. 

Nota: Para este tipo de grafos habrá, por tanto, al menos un vértice de grado par.
Podemos aplicar precisamente esto al problema número uno que se había planteado:
El primer día de curso se encuentran en una clase 121 alumnos. Según lo que acabamos
de ver siempre existe una persona que conoce a un número par de personas.

Definición 10
Un grafo es regular si todos sus vértices tienen el mismo grado.

DM – p.8/82
 Algunos grafos sencillos

• Grafo completo de n vértices Kn .

• Camino Pn y ciclo Cn de n vértices.
• Rueda de n + 1 vértices Wn .

Definición 11
Un grafo G = (V, E) es bipartito si V se puede dividir en dos conjuntos no vacı́os y
disjuntos V1 y V2 , de manera que cada arista e ∈ E conecta un vértice de V1 con otro de
V2 y viceversa.

• Grafo bipartito completo de n y m vértices Kn,m si se une cada n con cada m.

K4 C4 W4 K2,2 P4

De izquierda a derecha: completo, ciclo, rueda, completo bipartito y camino.

DM – p.9/82
 Algunos grafos sencillos

Definición 12
El grafo Qn (o cúbico) es aquel formado por vértices que representan las cadenas de bits de
longitud n. Dos vértices son adyacentes si y sólo si difieren en exactamente un bit.

10 11

0 1
00 01
Q1 Q2

110 111
100 101

Q3
010 011
000 001

DM – p.10/82
 Grafos complementarios

Definición 13
El grafo complementario G = (V, E) de un grafo simple G = (V, E) es aquel formado
por el mismo conjunto de vértices y tal que dos vértices son adyacentes en G si y sólo si no
son adyacentes en G.

G G

Problema 2  
|V |
Demostrar que |E| + |E| = .
2

Solución: |E| + |E| son todas las aristas posibles entre cada pareja de vértices. Es
|V |
decir, las tomamos de dos en dos así que |E| + |E| = 2

DM – p.11/82
 Grafos complementarios

Problema 3
Demostrar que si un grafo simple es autocomplementario G = G, entonces su número de
vértices es o bien múltiplo de cuatro o bien múltiplo de cuatro más uno.

Solución:
Como es autocomplementario él y su complementario tienen el mismo número de
aristas. Así que |E| = |E|. Si denotamos |V | = n y tenemos en cuenta que
 
|V |
|E| + |E| = ,
2
entonces

1
2|E| = n(n − 1) y 4|E| = n(n − 1)
2
que es múltiplo de 4 al ser cuatro veces algo. Esto nos dice que n(n − 1) es múltiplo de
4 al ser cuatro veces algo, lo que implica que o bien n o bien (n − 1) es múltiplo de 4,
pero no las dos cosas a la vez al tener paridades distintas. En el primer caso ya lo
tenemos y el segundo implica que n tiene que ser múltiplo de 4 más 1 para que cuando
se le reste el 1 dé un múltiplo de 4.
DM – p.12/82
 Subgrafos

Definición 14
Un grafo H = (W, F ) es un subgrafo de G = (V, E) si W ⊆ V y F ⊆ E .

Definición 15
G1 = (V1 , E1 ) y G2 = (V2 , E2 ) es el grafo simple
La unión de dos grafos simples
G1 ∪ G2 = (V1 ∪ V2 , E1 ∪ E2 ).

a b a b a b

=
S

d c d c d

DM – p.13/82
 Ejemplos

Problema 4
Sea Kn el grafo completo de n vértices.
• Dibujar K1 , K2 , K3 , K4 y K5 .
• ¿Cuál es el grado de los vértices de Kn ? Solución: n + 1
n

n(n−1)
• ¿Cuántas aristas tiene Kn ? Solución: 2 = 2

DM – p.14/82
 Ejemplos

Problema 5
Encontrar los grafos complementarios de K3,3 , C3 , C4 y C5 .

Solución:
Dos ciclos de 3 vértices.
Un trivial de 3 vértices.
Dos grafos de una arista y dos vértices.
Él mismo (C5 ).

DM – p.15/82
 Ejemplos

Problema 6
Demostrar que en todo grafo simple sin vértices aislados hay al menos dos vértices del mismo
grado.

Solución: Por ser no trivial d(i) ≥ 1, pues no tiene vértices aislados. Por ser grafo
simple se puede conectar con todos excepto con él mismo así que d(i) ≤ |V | − 1. El
problema es equivalente a |V | − 1 cajas y |V | bolas. El principio del palomar garantiza
que al menos en una caja hay 2 bolas, luego al menos 2 vértices tienen el mismos grado.

Problema 7
Hallar el mı́nimo número de vértices de un grafo con 7 aristas si d(i) ≤ 3 para todo i ∈ V .

Solución: Tenemos que |E| = 7 y d(i) ≤ 3 para todo vértice. Debe cumplirse que
X
d(i) = 2|E| = 14,
i

que expandido podemos escribir a lo más como 3 + 3 + 3 + 3 + 2 = 14

DM – p.16/82
 Representación numérica de un grafo

Definición 16
Sea G = (V, E) un grafo. Consideremos una ordenación v1 , v2 , . . . , v|V | de los vértices
de G. La matriz de adyacencia de G asociada a dicha ordenación es la matriz |V | × |V |
cuyas entradas Aij cuentan el número de aristas que unen vi con vj .

 1 2 3 4 
2 0 1 0 2 1
1  1 1 1 1 2
AG = 
 
 0 1 0 1 3

4 3
2 1 1 0 4

• AG es simétrica.
• Si G es simple, Aii = 0 y Aij ∈ {0, 1}.
• Si G es un multigrafo, Aii = 0.
¡Cuidado!, una distinta ordenación nos da una matriz distinta.
DM – p.17/82
 Representación numérica de un grafo

Definición 17
Sea G = (V, E) un grafo. Consideremos una ordenación v1 , v2 , . . . , v|V | de los vértices
de G y una ordenación e1 , e2 , . . . , e|E| de las aristas de G. La matriz de incidencia de G
asociada a dichas ordenaciones es la matriz |V | × |E| con entradas
(
0 si ej no es incidente con vi
Iij =
1 si ej es incidente con vi

b  a b c d e f g 
a 2 1 0 0 0 0 1 1 1
1  1 1 1 1 0 0 0  2
g f c IG = 
 
d  0 0 1 0 1 0 0 3


4 3
e 0 0 0 1 1 1 1 4

DM – p.18/82
 Isomorfismos

Importante: No confundir un grafo con su representación gráfica.

Definición 18
Dos grafos simples G1 = (V1 , E1 ) y G2 = (V2 , E2 ) son isomorfos si y sólo si existe una
función biyectiva f : V1 → V2 con la siguiente propiedad: a y b son adyacentes en G1 si y
sólo si f (a) y f (b) son adyacentes en G2 . Dicha función f se denomina isomorfismo.

• Una condición necesaria (pero no suficiente) para que dos grafos sean isomorfos
es que |V1 | = |V2 | y |E1 | = |E2 |.
• Existen n! funciones biyectivas entre dos grafos de n vértices.
• Dos grafos son isomorfos si existen ordenaciones de sus vértices tales que sus
matrices de adyacencia sean iguales.

DM – p.19/82
 Isomorfismos

Problema 8
Decir si son isomorfos los siguientes grafos:

Solución:
No lo son, pues el segundo tiene un vértice de grado 4, cosa que el primero no tiene.

DM – p.20/82
 Isomorfismos

Problema 9
Dibujar, salvo isomorfismos, todos los grafos simples de cinco vértices y cinco aristas.

DM – p.21/82
 Caminos en un grafo

Definición 19
Un camino (o cadena) en un grafo G = (V, E) es una secuencia alternada de vértices y
aristas de la forma v0 , {v0 , v1 }, v1 , {v1 , v2 }, v2 , . . . , vℓ−1 , {vℓ−1 , vℓ }, vℓ . La longitud
del camino es igual al número de aristas ℓ que lo componen. Existe una dirección implı́cita en
todo camino: v0 es el vértice inicial y vℓ , el vértice final.

Notas:
• En un grafo simple, un camino se puede representar por los vértices que lo
componen: v1 → v2 → . . . → vℓ .
• En un camino se pueden repetir aristas/vértices.

d c
Camino = (d, a, b, c, a, b)

a b

DM – p.22/82
 Caminos en un grafo

Definición 20
Un camino en el que todas las aristas son distintas se denomina camino simple. Un circuito
es un camino simple cerrado (v0 = vℓ ). (se pueden repetir vértices)

Un camino simple en el que todos los vértices v0 , v1 , . . . , vℓ son distintos (excepto quizás
los extremos v0 y vℓ ) se denomina camino elemental. Un camino elemental cerrado es un
ciclo.

Nota: En un camino simple se pueden repetir vértices.

e
Circuito = (c, d, a, b, d, e, c)
c d
Camino elemental = (a, c, e, d)
Ciclo = (a, b, d, a)
a b

Ejemplo: (c, e, d, b, a, d, c) es circuito pero no ciclo.

DM – p.23/82
 Grafos conexos

Definición 21
Un grafo es conexo si cada par de vértices v, w ∈ V pueden ser conectados por un camino
elemental. Un grafo no conexo está formado por la unión de varios subgrafos conexos y
desconectados entre sı́ que se denominan componentes conexas del grafo.

Nota: Si dos vértices de un grafo se pueden conectar por un camino, entonces existe un
camino elemental que los une.

a b c
Camino = (a, b, c, e, b, c, f )

d e f

DM – p.24/82
 Grafos conexos

Definición 22
Un punto de articulación o de corte de un grafo G es un vértice tal que si lo eliminamos
(junto con todas las aristas que le son incidentes) obtenemos un subgrafo con más compo-
nentes conexas que G. Un puente de un grafo G es una arista tal que si la eliminamos (pero
no los vértices con los que es incidente) obtenemos un grafo con más componentes conexas
que G.

a d f g
Ejemplo:

b c e h

• Puntos de articulación: b, c, y e.
• Puentes: las aristas {a, b} y {c, e}.

DM – p.25/82
 Número de caminos entre dos vértices

Teorema 23 Sea un grafo G con matriz de adyacencia A con respecto al orden

{v1 , v2 , . . . , v|V | }. El número de caminos orientados diferentes de longitud n ≥ 1 que
empiezan en vi y acaban en vj está dado por la entrada (i, j) de la matriz An .

Corolario 24 Sea G un grafo simple con matriz de adyacencia A, entonces

• A2ii = d(i) para todo 1 ≤ i ≤ |V |.
• tr A2 = 2|E|.
• tr A3 = 6 × Número de triángulos no orientados en G.
   
1 2 0 1 1 0 2 1 1 2
 1 0 1 1   1 3 2 1 
A =   A2 = 
   
 1 1 0 1   1 2 3 1


3 4 0 1 1 0 2 1 1 2
 
2 5 5 2
 5 4 5 5  tr A2
= 2|E| = 10
A3 = 
 
 5 5 4 5  tr A3 = 6|T | = 12


2 5 5 2
DM – p.26/82
 Número de caminos entre dos vértices

Nota: Si el grafo no es simple (multigrafo o pseudografo) el Corolario anterior no

puede aplicarse.

1    
0 1 2 5 3 1
A =  1 1 1  A2 =  3 3 3 
   
2
2 1 0 1 3 5
3

X
2
tr A = 13 6= 2|E| = d(i) = 10
i∈V

d(1) = 3 6= (A2 )11 = 5

d(2) = 4 6= (A2 )22 = 3
 
5 9 13
A3 =  9 9 9  ⇒ tr A3 = 19 6= 6|T | = 12
 
12 9 5

DM – p.27/82
 Grafos orientados o dirigidos

Definición 25
Un grafo dirigido G = (V, E) está compuesto por un conjunto no vacı́o de vértices V y
un conjunto de aristas (o arcos) E , que es un conjunto ordenado de pares de elementos
distintos de V .

Si u, w ∈ V , entonces una arista e ∈ E es el par ordenado (u, w), representado por

u w

Nota: Las definiciones de multigrafo y pseudografo dirigidos son análogas, no

permitiéndose la contradirección.

DM – p.28/82
 Grados en un grafo dirigido

En un grafo dirigido los vértices tienen dos tipos de grados:

Definición 26
El grado (o semigrado) interno de un vértice v de un grafo dirigido G es el número de
aristas que llegan a v . El grado (o semigrado) externo de un vértice v de un grafo dirigido
G es el número de aristas que salen de v .

b c b c b c

a a a

(1) di (a) = 0, de (a) = 1, di (b) = 2, de (b) = 2, di (c) = 2, de (c) = 1

(2) di (a) = 0, de (a) = 1, di (b) = 2, de (b) = 0, di (c) = 1, de (c) = 2
(3) di (a) = 0, de (a) = 1, di (b) = 1, de (b) = 1, di (c) = 1, de (c) = 0

Proposición 27 En un grafo dirigido G = (V, E) la suma de los grados internos de los

vértices es igual a la suma de los grados externos.

DM – p.29/82
 Representación numérica de un grafo dirigido

Definición 28
Sea G = (V, E) un grafo dirigido. Consideremos una ordenación v1 , v2 , . . . , v|V | de los
vértices de G. La matriz de adyacencia de G asociada a dicha ordenación es la matriz
|V | × |V | cuyas entradas Aij cuentan el número de aristas que comienzan en vi y acaban
en vj .

 1 2 3 4 
0 0 0 0 1
1 2  1 1 0 1 2
AG = 
 
 0 1 0 0 3

4 3
2 0 1 0 4

• AG es no es simétrica en general.
• Si G es simple, Aii = 0 y Aij ∈ {0, 1}.
• Si G es un multigrafo, Aii = 0.

DM – p.30/82
 Caminos en un grafo dirigido

Definición 29
Un camino en un grafo dirigido G = (V, E) es una sucesión de aristas de la forma
(v0 , v1 ), (v1 , v2 ), . . . , (vℓ−1 , vℓ ).

Notas:
• Nótese que todas las aristas del camino tienen la misma dirección.
• Las definiciones de camino elemental, camino simple, circuito y ciclo para grafos
dirigidos son análogas.

c d
Camino = (c, a, b, d, a, b)

a b

DM – p.31/82
 Árboles

Definición 30
Un árbol es un grafo simple y conexo que no contiene ciclos. Un bosque es un grafo simple
que no contiene ciclos. Cada componente conexa de un bosque es un árbol.

raíz
rama

hojas
Ejemplos:

• Árbol genealógico.
• Árbol de directorios de un ordenador.
• Organigrama de una empresa.

DM – p.32/82
 Caracterización de los árboles

Teorema 31 (a) El grafo G es un árbol si y sólo si es conexo y al borrar cualquier arista se

obtiene un grafo disconexo.
(b) El grafo G es un árbol si y sólo si no contiene ciclos y al añadir cualquier arista se crea
un ciclo.

Proposición 32 Sea G un grafo conexo tal que contenga un ciclo C . Entonces al borrar
cualquier arista de C el grafo resultante es conexo.

Teorema 33 Un grafo G = (V, E) es un árbol si y sólo si existe un único camino elemental

(no se repiten ni aristas ni vértices) entre cualquier par de vértices.

Teorema 34 Todo árbol con al menos dos vértices tiene al menos dos vértices de grado uno.

Definición 35
Procedimiento para hacer crecer un árbol:

1. Comenzar con G = ({r}, ∅), dónde r es el nodo raı́z.

2. Dado G = (V, E), añadir un nuevo vértice u y una nueva arista {u, v} donde v ∈ V .

Teorema 36 Todo grafo obtenido por este procedimiento es un árbol y todo árbol se puede
construir de este modo.
DM – p.33/82
 Propiedades de los árboles

Teorema 37 Todo árbol de n vértices tiene n − 1 aristas.

D EMOSTRACI ÓN : El
árbol con n = 1 no tiene aristas. El Teorema 36 nos garantiza que
podemos construir un árbol añadiendo un vértice y una arista en cada paso. Pero así no
modificamos la diferencia entre |E| y |V |. 

Teorema 38 Si G es un grafo de n vértices, entonces las siguientes afirmaciones son equi-

valentes:
1. G es un árbol.
2. G es conexo y tiene n − 1 aristas.
3. G tiene n − 1 aristas y no tiene ciclos.

DM – p.34/82
 Propiedades de los árboles

Problema 10
Demostrar que las parafinas Cn H2n+2 tienen moléculas de tipo árbol.

DM – p.35/82
 Propiedades de los árboles

Solución:
Los carbonos (vértices) tiene cuatro enlaces (4 aristas adyacentes) y los hidrógenos
(vértices) uno (una arista adyacente). Así que tendremos 4n grados para los carbonos,
2n grados para los hidrógenos que no están en los extremos y queda 2 para esos
extremos. Así que
X
d(i) = 4n + 2n + 2.
i

Como X
d(i) = 2|E|,
i

podemos decir que |E| = 3n + 1. Por otro lado, de la fórmula química deducimos que
|V | = n + (2n + 2) = 3n + 2 y comparando concluimos que |E| + 1 = |V |. Como el
grafo es conexo (sólo un molécula) y el número de aristas es sólo una menos que el
número de vértices podemos afirmar que es árbol.

DM – p.36/82
 Ejercicios

Problema 11
Dibujar todos los árboles (salvo isomorfismos) de cuatro y cinco vértices.

DM – p.37/82
 Ejercicios

Problema 12
¿Cuántos árboles tiene un bosque de 62 vértices y 51 aristas?

Solución:
del enunciado E1 + E2 + · · · + Ek = 51 y V1 + V2 + · · · + Vk = 62. Como es árbol
E = V − 1, así que E1 + 1 + E2 + 1 + · · · + Ek + 1 = E1 + E2 + · · · + Ek + k = 62.
Comparando esta última expresión con la primera 51 + k = 62, luego k = 11

Problema 13
Demostrar que si en un árbol todos los vértices que no son hojas tienen grado tres, entonces el
árbol tiene un número par de vértices.

Solución:
La hojas tiene grado 1 (impar) y los demás tiene grado 3 (impar). Todos los vértices
tiene grado impar. Y según un teorema ya visto el número de vértices de grado impar
(todos en este caso) en un grafo G es par.

DM – p.38/82
 Árboles generadores

Definición 39
Un árbol generador o recubridor de un grafo conexo G es un árbol que contiene todos los
vértices de G y es subgrafo de G.

G Sí No No

Definición 40
Un grafo ponderado G = (V, E, ω) es un grafo en el que a cada arista e ∈ E se le asocia
un peso ω(e) ∈ R.

ω3
ω1 ω2

DM – p.39/82
 Árboles generadores mínimos

Definición 41
Un árbol generador mı́nimo de un grafo conexo ponderado es un árbol generador tal que la
suma de los pesos de sus aristas es la más pequeña posible.

Aplicación:
Construir una línea telefónica (o un sistema de autopistas) entre una serie de ciudades
tal que el coste sea mínimo y todas estén conectadas.
Nota:
El número de árboles con n vértices crece muy rápidamente con n.

Definición 42
Un algoritmo voraz es aquel que en cada paso toma la elección óptima.

La elección óptima en cada paso intermedio no garantiza una solución óptima para todo
el problema. Sin embargo, en el caso del árbol generador de peso mínimo los
algoritmos (voraces) de Prim y Kruskal sí funcionan.

Nota: el árbol recubridor de peso mínimo no tiene por qué ser único.
DM – p.40/82
 Algoritmo de Prim, 1957

Algoritmo 43 (Algoritmo de Prim)

procedure Prim(G: grafo ponderado conexo con n vértices)
T = arista con peso mı́nimo
for i = 1 to n − 2
begin
e = arista de peso mı́nimo incidente con un vértice de T
y que no forme un ciclo si se le añade a T
T = T con la arista e añadida
end

Notas:
• La arista e puede no ser única.
• El árbol generador de peso mínimo puede no ser único
• El resultado es un árbol con n vértices, luego tiene que tener n − 1 aristas.
• En este caso es necesaria la incidencia.

Teorema 44 Dado un grafo conexo ponderado G, el algoritmo de Prim produce un árbol

generador mı́nimo de G.
DM – p.41/82
 Algoritmo de Prim

a a a

3 1 3 1 3 1
4 4 4
f b f b f b
3 3 3
3 2 3 2 3 2
e c e c e c
2 2 2
1 2 1 2 1 2

d d d
(A) (B) (C)

(A): {e, d} ∪ {e, c} ∪ {c, b} ∪ {b, a} ∪ {a, f }

(B): {e, d} ∪ {d, c} ∪ {c, b} ∪ {b, a} ∪ {a, f }
(C): {a, b} ∪ {b, c} ∪ {c, e} ∪ {e, d} ∪ {e, f }
X
ω(e) = 9
e∈E(T )

DM – p.42/82
 Algoritmo de Kruskal, 1957

Algoritmo 45 (Algoritmo de Kruskal)

procedure Kruskal(G: grafo ponderado conexo con n vértices)
T = (∅, ∅)
for i = 1 to n − 1
begin
e = arista de peso mı́nimo que no forme un ciclo si se le añade a T
T = T con la arista e añadida
end

Notas:
• La arista e puede no ser única.
• La arista e puede no ser incidente con ningún vértice en T .

Teorema 46 Dado un grafo conexo ponderado G, el algoritmo de Kruskal produce un árbol

generador mı́nimo de G.

Nota: en este caso la incidencia no es necesaria.

DM – p.43/82
 Algoritmo de Kruskal

a a a

3 1 3 1 3 1
4 4 4
f b f b f b
3 3 3
3 2 3 2 3 2
e c e c e c
2 2 2
1 2 1 2 1 2

d d d
(A) (B) (C)

(A): {e, d} ∪ {a, b} ∪ {e, c} ∪ {c, b} ∪ {a, f }

(B): {e, d} ∪ {a, b} ∪ {c, b} ∪ {c, d} ∪ {a, f }
(C): {a, b} ∪ {e, d} ∪ {e, c} ∪ {c, b} ∪ {e, f }
X
ω(e) = 9
e∈E(T )

DM – p.44/82
 Notas:

• Ambos algoritmos se pueden usar para obtener un árbol generador de un grafo

conexo [no ponderado] G = (V, E).
• Los algoritmos voraces pueden fallar en problemas parecidos.

Problema 14
Encontrar un ciclo que pase por todos los vértices de un grafo y minimice la suma de los pesos
de las aristas correspondientes.

d 3 c d 3 c
5 5
3 1 2 3 1 2

a 1 b a 1 b

• Algoritmo voraz: {a, b} ∪ {a, c} ∪ {c, d} ∪ {d, a} ⇒

P
e ω(e) = 10.
• Ciclo mínimo: {a, b} ∪ {b, c} ∪ {c, d} ∪ {d, a} ⇒
P
e ω(e) = 9.

DM – p.45/82
 Ejemplo: Diseño de una red telefónica local

Problema 15
El plano muestra los puntos de conexión y las posibles lı́neas telefónicas en una urbanización.
La zona quedará comunicada cuando dos puntos cualquiera estén conectados. En rojo está
indicado el precio de cada lı́nea en miles de euros. Calcular el diseño de la red más barata que
conecte la zona.

b 12 e 4 h 20 k

6 10 3 8 11 7 11 13 6
9 2 10 11 12
a n
c f i ℓ
3 4 15 9 15 11 5 5

d 10 g 13 j 9 m

DM – p.46/82
 Más ejemplos

Problema 16
Calcular mediante el algoritmo de Kruskal un árbol generador mı́nimo del grafo:

13

1 12

6 14 3 4
5 15
7 9 11 8

2 10

16

DM – p.47/82
 Más ejemplos

Problema 17
Estudiar si el siguiente grafo admite un árbol generador de peso menor o igual que 12:

f e c
3
1
6
3
5
1
3 2
g 7 d
h
7 5
2
4 2

a 2 b

DM – p.48/82
 Grafos planares

Definición 47
Un grafo es planar si puede ser dibujado en el plano sin que sus aristas se crucen. Una
representación de un grafo planar en la que las aristas no se crucen se denomina grafo
plano.

Ejemplo: K4 es planar; pero K5 y K3,3 no lo son.

Teorema 48 (Kuratowsky, 1930) Un grafo es planar si y sólo si no contiene como subgrafo

a ninguna subdivisión de K5 ni de K3,3 .

Definición 49
Insertar un nuevo vértice en una arista de un grafo se denomina subdividir dicha arista. La
subdivisión de una o más aristas de un grafo G da lugar a una subdivisión de G.

DM – p.49/82
 Grafos planares y grafos duales

Teorema 50 (Fórmula de Euler, 1752) Un grafo G

= (V, E) plano y conexo divide al plano
en R regiones de manera que |V | − |E| + R = 2 .

R = 2 + |E| − |V | = 2 + 6 − 5= 3

Definición 51
Dado un grafo G = (V, E) plano, podemos construir su grafo dual G⋆ = (V ⋆ , E ⋆ ) de la
siguiente manera: introducimos un vértice del grafo dual r ∈ V ⋆ por cada región r en la que
G divide al plano. Los vértices r1 , r2 ∈ V ⋆ tienen tantas aristas incidentes e ∈ E ⋆ como
aristas comparten las regiones r1 , r2 definidas por el grafo G.

|E ⋆ | = |E|
|V ⋆ | = R
R⋆ = |V |

DM – p.50/82
 Grafos duales

Definición 52
El grado de una región r de un grafo plano se define como el grado del vértice correspon-
diente r ∈ V ⋆ en el grafo dual.

Teorema 53 En un grafo plano y conexo se cumple que

2|E| = Suma de los grados de las regiones .

D EMOSTRACI ÓN : Sabemos que 2|E| = i∈V d(i). Aplicamos esta fórmula al grafo dual
P

G⋆ = (V ⋆ , E ⋆ )
X X
⋆
2|E | = d(i) = d(r)
i∈V ⋆ r∈R

Como |E| = |E ⋆ | el teorema está demostrado. 

Teorema 54 (Teorema de los cuatro colores, v2) Todo mapa (en una esfera) puede ser
coloreado con a lo sumo cuatro colores.

DM – p.51/82
Algunos ejemplos

1⋆ 1⋆ 1⋆

2⋆
a b a b a b c

|R| = 1 |R| = 2 |R| = 1

d(1⋆ ) = 2 d(1⋆ ) = 2 d(1⋆ ) = 4

c
1⋆
2⋆ |R| = 2
a b d(1⋆ ) = 3

DM – p.52/82
 Algunos corolarios

Corolario 55 Si G es un grafo simple, conexo y plano con |V | ≥ 3, entonces |E| ≤

3|V | − 6.

D EMOSTRACI ÓN :
2|E| = r d(r) ≥ 3R (3 es el grado mínimo). Según Euler |V | − |E| + R = 2, así
P

que R = 2 − |V | + |E| que podemos multiplicar por 3 quedando

3R = 6 − 3|V | + 3|E|, que podemos sustituir en la primera ecuación quedando
2|E| ≥ 6 − 3|V | + 3|E| y que simplificamos hasta |E| =≤ |V | − 6. 

Aplicación:
K5 no es planar. |V | = 5; |E| = 10. Luego, 10 = |E| > 3|V | − 6 = 9.

DM – p.53/82
 Algunos corolarios

Corolario 56 Si G es un grafo simple, conexo y plano con |V | ≥ 3 y no tiene ciclos de

longitud 3, entonces |E| ≤ 2|V | − 4.

Problema 18
Usar el corolario para probar que K3,3 no es planar.

Solución:
|V | = 6 por tanto se cumple que |V | ≥ 3, no tiene ciclos y es conexo. Si fuese plano
|E| ≤ 2|V | − 4, como |E| = 9 vemos que 9 ≤ 2 · 4 = 8, no es cierto, así que por tanto
no es plano.

DM – p.54/82
 Ejemplo

Problema 19
Sean dos grafos G1 y G2 . G1 es un grafo plano conexo de 10 vértices y que divide al plano en
3 regiones. G2 es un grafo de 10 vértices todos ellos de grado mayor o igual que 3. ¿Son
isomorfos G1 y G2 ?

Solución: Para G1 tenemos que |V | − |E| + R = 2, que en este caso es

10 − |E| + 3 = 2, así que |EG1
P| = 11
Para G2 tenemos que 2|E| = i d(i), que en nuestros caso es 2|E| ≥ 3 · 10, así que
|EG2 | ≥ 15
Como para que sean isomorfos deben tener el mismo número de vértices y aristas como
mínimo, como en este caso el número de aristas es incompatible entonces no son
isomorfos.

DM – p.55/82
 Emparejamientos en grafos

Definición 57
Un emparejamiento completo o perfecto de un grafo con 2n vértices es un subgrafo gene-
rador formado por n aristas disjuntas.

• Todos los vértices de G pertenecen al subgrafo.

• Cada vértice de G sólo tiene una arista incidente perteneciente al subgrafo.
• En grafos bipartitos es menos difícil:

Teorema 58 Si todos los vértices de un grafo bipartito tienen el mismo grado d ≥ 1, en-
tonces contiene un emparejamiento perfecto.

• ¿Es posible que en una fiesta todos los participantes que se conozcan bailen
simultáneamente?
DM – p.56/82
 Grafos eulerianos

Problema 20
En la ciudad de Königsberg (Kaliningrado) hay un rı́o y siete puentes. ¿Es posible dar una vuelta
y cruzar cada puente una sola vez?

Representación en término de grafos:

DM – p.57/82
 Grafos eulerianos

Problema 21
Dado un grafo G = (V, E), ¿existe un circuito que contenga cada arista e ∈ E ? [Al ser
circuito debe contener cada arista una sola vez].

Definición 59
Un circuito euleriano es un circuito que contiene a todas las aristas del grafo. Un grafo que
admite un circuito euleriano se denomina grafo euleriano.
Un camino euleriano es un camino simple y abierto que contiene todas las aristas del grafo.
Un grafo no euleriano que admite un camino euleriano se denomina grafo semi-euleriano.

Teorema 60 Un grafo conexo es euleriano si y sólo si todos sus vértices tienen grado par.
Un grafo conexo es semi-euleriano si y sólo si contiene exactamente dos vértices de grado
impar.
Un grafo dirigido conexo es euleriano si y solo si para cualquier vértice el grado interno coin-
cide con el grado externo.

Luego, el problema de los puentes de Königsberg no tiene solución: el grafo

correspondiente no es ni euleriano ni semi-euleriano.
Problema 22
¿Para qué valores de n son eulerianos los grafos Kn , Cn y Qn ?
DM – p.58/82
 Algoritmo de Fleury

Sea G = (V, E) un grafo conexo con todos los vértices de grado par:

(1) Paso inicial: Escogemos un vértice v0 como origen del circuito C0 = {v0 }.
(2) Extensión del circuito: Sea el circuito Ci = {v0 , e1 , v1 , . . . , ei , vi } donde vi ∈ V
y ei ∈ E.
• Si existe una única arista ei+1 = {vi , w} ∈ E \ {e1 , e2 , . . . , ei }:
• Ci → Ci+1 = {v0 , e1 , v1 , . . . , ei , vi , ei+1 , w}
• V → V \ {vi }
• E → E \ {ei+1 }
• Si hay varias aristas incidentes con vi : elegimos cualquiera de ellas con la
condición que no sea puente. Si escogemos
ei+1 = {vi , w} ∈ E \ {e1 , e2 , . . . , ei }:
• Ci → Ci+1 = {v0 , e1 , v1 , . . . , ei , vi , ei+1 , w}
• E → E \ {ei+1 }
(3) Repetimos el Paso (2) hasta que E = ∅ (|E| pasos).
C|E| es el circuito euleriano buscado.

DM – p.59/82
 Ejemplo

Problema 23
Encontrar un circuito euleriano en el siguiente grafo:

d e f

a b g

Problema 24
Encontrar un circuito euleriano en el siguiente grafo:

f b

d c e g

a h
DM – p.60/82
 Ejemplo

Problema 25
Diseñar un algoritmo para encontrar un camino euleriano.

Problema 26
Encontrar un camino euleriano en el siguiente grafo:

f b

d c e g

a h

DM – p.61/82
 Grafos hamiltonianos

Problema 27
En una cena entre diplomáticos hay que tener cuidado de sentar juntos a diplomáticos de paı́ses
amigos y sentar separados a diplomáticos de paı́ses enemigos. ¿Es posible hacer esto con n
diplomáticos?

Problema 28
¿Es posible encontrar un ciclo en G tal que pase por cada vértice una sola vez?

Este tipo de problemas son equivalentes a que su grafo sea hamiltoniano.

DM – p.62/82
 Grafos hamiltonianos

Definición 61
Un ciclo hamiltoniano es un ciclo que contiene a todos los vértice del grafo. Un grafo que
admite un ciclo hamiltoniano se denomina grafo hamiltoniano.
Un camino hamiltoniano es un camino elemental y abierto que contiene todos los vértices
del grafo. Un grafo no hamiltoniano que admite un camino hamiltoniano se denomina grafo
semi-hamiltoniano.

Nota: El problema de decidir si un grafo G arbitrario tiene un ciclo hamiltoniano es

mucho más difícil que decidir si tiene un circuito euleriano. El problema no tiene
solución general, aunque existen condiciones suficientes del estilo siguiente:

Teorema 62 (Dirac, 1950) Si G es un grafo simple con n vértices y cada vértice tiene un
grado ≥ n/2, entonces G es hamiltoniano.

DM – p.63/82
 Grafos hamiltonianos

Problemas:
• Demostrar que Kn es hamiltoniano para todo n ≥ 3.

Solución:
El grado de cada vértice es d(i) = n − 1. Según el teorema de Dirac si
n − 1 ≥ n/2 es hamiltoniano, caso que se cumple cuando n ≥ 3, pues 2 ≥ 3/2

• Demostrar que Kn,m es hamiltoniano si y sólo si n = m ≥ 2.

Solución:
Los grados de los vértices son o bien n (el más pequeño) o bien m, así que
|V | = m + n. Según el teorema de Dirac y eligiendo el caso más conflictivo
n ≥ n+m2 , que se cumple si sólo si n = m.

DM – p.64/82
 El problema del viajante

Problema 29
Un viajante tiene que cubrir n ciudades interconectadas todas entre sı́. Su objetivo es salir de
su casa, visitarlas todas una sola vez y volver a su casa al finalizar de manera que la distancia
recorrida sea mı́nima.

Este problema consiste en encontrar entre todos los ciclos hamiltonianos del grafo
ponderado Kn = (Vn , En , ω) uno C que minimice la función
X
E(C) = ωe .
e∈V (C)

Este problema es muy difícil y no se conocen algoritmos polinómicos que lo resuelvan.

DM – p.65/82
 Problemas

Problema 30
Demostrar que el número de ciclos hamiltonianos no dirigidos que tiene Kn con n ≥ 3 es
(n − 1)!/2.

Solución: Al principio hay (n − 1) a elegir, luego (n − 2) y así sucesivamente por lo

que (n − 1)(n − 2)(n − 3) · · · = (n − 1)!. Como no es dirigido estamos contando el
doble así que el numero de ciclos es 1/2(n − 1)!

Problema 31
Encontrar los árboles generadores de menor y mayor peso en el siguiente grafo ponderado:

d 3 e

1 6
4 2 6

a 5 b 7 c

DM – p.66/82
 Problemas

Problema 32
¿Existe algún grafo simple de n vértices y m aristas y tal que su matriz de adyacencia satisfaga
tr A3 = (2n + 1)(2m + 1)?

Solución: Sabemos que T rA3 = 6T , pero como 2(n + 1) y (2m + 1) son impares su
producto es impar que no puede ser 6 veces algo, que es par.

Problema 33
Encontrar un circuito euleriano en el siguiente grafo orientado:
g h i

e
d f

a b c

Solución: Un posible circuito es (a, e, f, i, h, f, c, b, e, h, g, d, b, a)

DM – p.67/82
 Otros algoritmos

Contenidos

1. Coloraciones en grafos (algoritmo voraz)

2. Caminos de longitud mínima (algoritmo de Dijkstra)

DM – p.68/82
 Coloraciones propias de un grafo

Problema 34
En un congreso hay seis conferencias de una hora programadas para el dı́a inaugural
{c1 , c2 , . . . , c6 }. Entre la audiencia hay quienes quieren escuchar los pares de conferencias
{c1 , c2 }, {c1 , c4 }, {c3 , c5 }, {c2 , c6 }, {c4 , c5 }, {c5 , c6 } y {c1 , c6 }. ¿Cuántas horas son
necesarias para poder dar todas las conferencias sin solaparse?

Definición 63
Una coloración propia (con q colores) de un grafo G = (V, E) es una función c : V →
{1, 2, . . . , q} tal que c(u) 6= c(w) siempre que u y w sean adyacentes.

Notas:
• Dado un grafo G = (V, E) el número total de coloraciones (propias y no propias)
con q colores es q |V | .
• En todo lo que sigue consideraremos sólo coloraciones propias.
• En la definición coloreamos los vértices de G. También se pueden
colorear las aristas de G con la siguiente condición: si e, f ∈ E, c(e) 6= c(f )
siempre que e, f sean incidentes con el mismo vértice.

DM – p.69/82
 Coloraciones propias de un grafo

q=3

Dos preguntas difíciles:

1. ¿Cuántas coloraciones con q colores PG (q) se pueden conseguir sobre G?

2. ¿Cuántos colores q necesito cómo mínimo para poder colorear G?

Definición 64
El número cromático χ(G) de un grafo G es el menor entero q tal que existe una coloración
de G con q colores; es decir, PG (q) > 0 para todo q ≥ χ(G) ∈ N.

Notas:
• El número cromático del grafo anterior es χ(G) = 3.
• No hay algoritmos polinómicos para calcular PG (q) ó χ(G).

DM – p.70/82
 Algoritmo voraz para colorear un grafo

Algoritmo 65 (Algoritmo voraz)

procedure (G: grafo simple conexo con n vértices)
Ordenamos los vértices de V : {v1 , v2 , . . . , vn }
c(v1 ) = 1
for i = 2 to n
begin
Si = {q | c(vk ) = q , para todo vk vecino de vi con k < i}
c(vi ) = color más pequeño que no esté en Si
end

Notas:
• No calculamos χ(G), sino una cota superior (muy) dependiente de la ordenación
usada.
• Para calcular χ(G) habría que considerar las n! ordenaciones posibles de los
vértices (tiempo exponencial).

Problema 35
Calcular el número de coloraciones con q colores que puedo obtener con el grafo Kn .

DM – p.71/82
 Algunos teoremas

Teorema 66 Si G es un grafo con grado máximo k , entonces χ(G) ≤ k+1 .

Teorema 67 (Brooks, 1941) Si G es un grafo no completo, conexo y con grado máximo

k ≥ 3, entonces χ(G) ≤ k .

Ejemplos:

• K4 es regular con grado 3 y χ(K4 ) = 4.

• C2n+1 es regular con grado 2 y χ(C2n+1 ) = 3.

Proposición 68 Un grafo G es bipartito si y sólo si χ(G) = 2.

Teorema 69 Un grafo es bipartito si y sólo si no contiene ciclos de longitud impar.

Corolario 70 Todos los árboles son bipartitos

DM – p.72/82
 El teorema de los cuatro colores

Teorema 71 (Appel y Haken, 1976) PG (4) > 0 para todo grafo planar G.
Bastan cuatro colores para colorear un mapa de tal modo que los países vecinos tengan
colores distintos.
Notas:
• Fue conjeturado en 1852.
• En 1879 Kempe publicó una prueba errónea; pero encontró las ideas
fundamentales.
• Heawood (1890) encontró el error en la prueba de Kempe y demostró el teorema
de los cinco colores.
• La prueba original fue asistida por ordenador (¡más de 1200 horas de CPU!).
• No existe aún una prueba analítica.
• No existe un teorema de los tres colores: existen grafos planares con número
cromático χ(G) = 4: e.g. K4 .

DM – p.73/82
 Problemas de camino mínimo

Problema 36
Encontrar el camino de longitud mı́nima que une un vértice inicial s y un vértice final t en un
grafo G = (V, E) conexo, simple y ponderado con todos los pesos positivos (ωi > 0 para todo
i ∈ E ).

Solución: El algoritmo de Dijkstra (1959).

Teorema 72 El algoritmo de Dijkstra encuentra la longitud del camino más corto entre dos
vértices de un grafo conexo, simple y ponderado con todos los pesos positivos.

Proposición 73 El algoritmo de Dijkstra, aplicado sobre un grafo conexo, simple y ponderado

con todos los pesos positivos y con n vértices, realiza O(n2 ) operaciones (sumas y
comparaciones).

DM – p.74/82
 El algoritmo de Dijkstra

Idea:
En cada iteración a cada vértice j se le asignan dos etiquetas que pueden ser o bien
temporales (δj , Pj ) o bien permanentes (δj , Pj ) .
• La etiqueta δj es una estimación de la longitud del camino mínimo desde el
vértice inicial s hasta el vértice actual j.
• La etiqueta Pj es una estimación del predecesor del vértice j en dicho camino.
Denotaremos ωij > 0 al peso de la arista {i, j} ∈ E.

Problema 37
Calcular el camino de menor longitud entre s y t en el siguiente grafo:

b 5 d
4 6
8
s 1 2 t

2 2
c 10 e

DM – p.75/82
 El algoritmo de Dijkstra (2)

(1) Paso inicial: Marcamos el origen s con la etiqueta permanente (0, s) .

El resto de los vértices j ∈ V (j 6= s) se marcan temporalmente:
• Si {j, s} ∈ E, se marca con (ωs,j , s).
• Si {j, s} 6∈ E, se marca con (∞, −).
(2) Sea v ∈ V el último vértice que se ha vuelto permanente. Examinamos cada
vértice temporal j comparando δj con el valor de δv + ωv,j .
• Si δv + ωv,j < δj , cambiamos (δj , Pj ) por ( δv + ωv,j , v).
• Si δv + ωv,j ≥ δj , no hacemos nada.
(3) De entre todos los vértices temporales j examinados, elegimos aquél cuya δj sea
mínima δmin .
• Si δmin = ∞ el algoritmo termina: no hay camino entre s y t.
• Si δmin < ∞, marcamos dicho vértice con etiqueta permanente.
(Esta estimación sólo puede empeorar porque ωij > 0).
(4) Si el vértice marcado es t, el algoritmo termina: el camino más corto entre s y t se
obtiene siguiendo las etiquetas permanentes.
Si no es t, volver al paso (2).
DM – p.76/82
El algoritmo de Dijkstra: Ejemplo

b 5 d
4 6
8
s 1 2 t

2 3
c 10 e

Vértice Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6

s (0, s) ⋆ ⋆ ⋆ ⋆ ⋆
b (4, s) (3, c) (3, c) ⋆ ⋆ ⋆
c (2, s) (2, s) ⋆ ⋆ ⋆ ⋆
d ∞ (10, c) (8, b) (8, b) ⋆ ⋆
e ∞ (12, c) (12, c) (10, d) (10, d) ⋆
t ∞ ∞ ∞ (14, d) (13, e) (13, e)

DM – p.77/82
 El algoritmo de Dijkstra: Ejemplo con grafos dirigidos

El algoritmo de Dijkstra permite, con las variaciones obvias, obtener el camino más
corto en un grafo dirigido
b 5 d
4 6
8
s 1 2 t

2 3
c 10 e

Vértice Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6

s (0, s) ⋆ ⋆ ⋆ ⋆ ⋆
b (4, s) (4, s) ⋆ ⋆ ⋆ ⋆
c ∞ (5, b) (5, b) ⋆ ⋆ ⋆
d ∞ ∞ (13, c) (13, c) ⋆ ⋆
e ∞ ∞ (15, c) (15, c) (15, c) ⋆
t ∞ ∞ ∞ (19, d) (18, e) (18, e)
DM – p.78/82
Más ejemplos: distancia entre s y b

b 1 d
10 6
5
s 20 2 t

2 3
c 10 e

Vértice Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6

s (0, s) ⋆ ⋆ ⋆ ⋆ ⋆
b (10, s) (10, s) (8, d) (8, d) ⋆ ⋆
c (2, s) (2, s) ⋆ ⋆ ⋆ ⋆
d ∞ (7, c) (7, c) ⋆ ⋆ ⋆
e ∞ (12, c) (9, d) (9, d) (9, d) ⋆
t ∞ ∞ (13, d) (13, e) (12, e) (12, e)

DM – p.79/82
 Más ejemplos

Problema 38
Hallar un camino de longitud mı́nima entre los vértices a y z del grafo siguiente. Hallar también
las distancias d(a, a), d(a, z), d(b, z) y d(c, z).

b d
5
2 2

a 2 1 z

3 4
c 5 e

DM – p.80/82
 Problemas

Problema 39
Utilizar el algoritmo de Dijkstra para determinar en el grafo ponderado siguiente un camino de
longitud mı́nima entre los vértices Z y A.

E 2 D

3 1 1 5

Z
2 F G
2 A

1 1 1 4

C 5 B

DM – p.81/82
Agradecimientos

Jesus Salas

Eduardo J. S. Villaseñor

DM – p.82/82