Clase de la asignatura Matemática Discreta

CAMINOS Y CICLOS HAMILTONIANOS

G. Argiroffo S. Bianchi L. Moroni

1 Deptartamento de Matemática

Escuela de Ciencias Exactas y Naturales

UNR

28 de marzo de 2022

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 1 / 44

O UTLINE

1 D EFINICIONES Y EJEMPLOS

2 R ESULTADOS SOBRE CICLOS Y CAMINOS HAMILTONIANOS

3 U N PROBLEMA REAL ASOCIADO A CICLOS HAMILTONIANOS

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 2 / 44

O UTLINE

1 D EFINICIONES Y EJEMPLOS

2 R ESULTADOS SOBRE CICLOS Y CAMINOS HAMILTONIANOS

3 U N PROBLEMA REAL ASOCIADO A CICLOS HAMILTONIANOS

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 3 / 44

I NTRODUCCI ÓN

Sea G = (V, E) grafo o multigrafo con |V| ≥ 3.

Recordar
{a, b} ⊂ V , P camino simple a-b en G (P no repite vértices ni aristas y
a 6= b).
C ciclo en G (camino simple cerrado con al menos 3 aristas).
Ejemplo: Juego ideado por Sir William R. Hamilton (1805-1865)

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 4 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Solución

D EFINICI ÓN
Si G = (V, E) es un grafo o un multigrafo con |V| ≥ 3, decimos que G tiene un
ciclo hamiltoniano si existe en G un ciclo que contiene cada vértice de V .
Un camino hamiltoniano es un camino simple de G que contiene todos sus
vértices.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 5 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Sea G = (V, E).

Recordar
{a, b} ⊂ V , un a-b recorrido euleriano en G utiliza todas las aristas en E
exactamente una vez.
Un circuito euleriano en G es un circuito en G que utiliza todas las aristas
en E exactamente una vez.

T EOREMA DE E ULER
Un grafo tiene un circuito euleriano si y sólo si todos los vértices tienen grado
par.

No existe resultado similar para determinar la existencia de un ciclo

hamiltoniano en un grafo.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 6 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Ejemplo 1 Grafo completo Kn .

Es fácil ver que cualquier permutación en los vértices de V(Kn ) induce un
ciclo hamiltoniano. Cuántos ciclos hamiltonianos distintos tiene Kn ? Cuántos
caminos hamiltonianos distintos? (ejercicio).
Ejemplo 2
b

a c

e
d

f
g

h
i

G j

V(G) = V1 ∪ V2 , con V1 = {a, e, g, i} y V2 = {b, c, d, f , h, j}. No existen arcos

{u, w} con u, v ∈ Vi con i = 1, 2. G es bipartito.
Si existiera un camino hamiltoniano, deberı́a existir una secuencia alternada
de vértices en V1 y V2 . Pero |V1 | = 4 y |V2 | = 6. No existe camino (o ciclo)
hamiltoniano en G.
S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 7 / 44
C ICLOS Y CAMINOS HAMILTONIANOS

Observaciones
Si C es un ciclo hamiltoniano en G y e ∈ C, entonces C − e es un camino
hamiltoniano en G.
G puede tener un camino hamiltoniano y no tener un ciclo hamiltoniano.
Veamos el siguiente grafo:

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 8 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Las aristas {a, b}, {b, c}, {c, f }, {f , e}, {e, d}, {d, g}, {g, h}, {h, i} forman un
camino hamiltoniano en G.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 9 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Vemos que |V(G)| = 9, si G tiene un ciclo hamiltoniano entonces éste tiene 9

aristas.
Comencemos en el vértice b y veamos si es posible construir un ciclo
hamiltoniano.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 10 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Debido a la simetrı́a del grafo, es lo mismo utilizar la arista {a, b} o la arista

{b, c}. Utilizamos la última.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 11 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Ahora podemos usar la arista {c, i} o la arista {c, f }. Utilizamos la última por
simetrı́a y eliminamos {c, i} como posibilidad de elección para el ciclo.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 12 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Como necesitamos incorporar el vértice i en el ciclo y la arista {c, i} ya no

está disponible, utilizamos la arista {f , i}.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 13 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Como necesitamos incorporar el vértice i en el ciclo y la arista {c, i} ya no

está disponible, utilizamos la arista {f , i}.
Quitamos la arista {e, f } porque no participará del ciclo.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 13 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Las únicas opciones son agregar las aristas {i, h} y {h, g}.

a b c

e f
d

h i
g

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 14 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Si elegimos la arista {g, d}, eliminamos {g, a}. Resulta que no podemos
volver al vértice b sin dejar fuera del ciclo al vértice e.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 15 / 44

C ICLOS Y CAMINOS HAMILTONIANOS

Si elegimos la arista {g, a}, eliminamos {g, d}. Nuevamente que no podemos
volver al vértice b de partida sin dejar fuera del ciclo a los vértices d y e.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 16 / 44

D EFINICIONES Y EJEMPLOS

Este grafo es conocico como el grafo de Petersen,

a

f
e j
b
g

i
h

d c

existe un camino simple que recorre todos los vértices del grafo :
{a, f }, {f , h}, {h, c}, {c, b}, {b, g}, {g, j}, {j, e}, {e, d}, {d, i}.
Es decir existe un camino hamiltoniano.
Pero no existe ningún ciclo hamiltoniano (ejercicio).

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 17 / 44

S UGERENCIAS PARA ENCONTRAR UN CIRCUITO
HAMILTONIANO

Sea G = (V, E),

Si G tiene un ciclo hamiltoniano, entonces para todo v ∈ V vale

deg(v) ≥ 2.
Si a ∈ V y deg(a) = 2, entonces las dos aristas incidentes en a deben
participar del ciclo hamiltoniano.
Si a ∈ V y deg(a) > 2, una vez que el ciclo ha pasado por a se
desestiman las aristas que no fueron utilizadas.
Un ciclo hamiltoniano en G no es un ciclo hamiltoniano de un subgrafo G0
de G a menos que G0 sea un subgrafo por aristas.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 18 / 44

O UTLINE

1 D EFINICIONES Y EJEMPLOS

2 R ESULTADOS SOBRE CICLOS Y CAMINOS HAMILTONIANOS

3 U N PROBLEMA REAL ASOCIADO A CICLOS HAMILTONIANOS

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 19 / 44

G RAFO DIRIGIDO COMPLETO

Sea Kn∗ un grafo dirigido completo, que tiene n vértices y para cualquier par de
{x, y} ⊂ V se verifica que exactamente una de las arista (x, y) o (y, x) es una
arista en Kn∗ .
Veamos un ejemplo: K5∗

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 20 / 44

G RAFO DIRIGIDO COMPLETO

T EOREMA
Kn∗ contiene un camino hamiltoniano (dirigido).

Demostración: Sea m ≥ 2 y Pm un camino simple con m − 1 aristas

(v1 , v2 ), (v2 , v3 ), . . . , (vm−1 , vm ) en Kn∗ .
(porqué puedo asegurar que existe un tal camino?)

Si m = n el teorema está demostrado.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 21 / 44
G RAFO DIRIGIDO COMPLETO

Suponemos que m < n y por lo tanto existe v ∈ V que no pertenece a Pm .

Si (v, v1 ) es una arista de Kn∗ entonces agregamos (v, v1 ) al comienzo de Pm y
conseguimos un nuevo camino simple con m aristas.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 22 / 44

G RAFO DIRIGIDO COMPLETO

Si (v, v1 ) no es arista de Kn∗ entonces (v1 , v) es una arista de Kn∗ .

Si (v, v2 ) está en Kn∗ ,

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 23 / 44

G RAFO DIRIGIDO COMPLETO

Entonces quitamos (v1 , v2 ) a Pm y agregamos en su lugar las aristas (v1 , v) y

(v, v2 ). Obtenemos un camino con m aristas.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 24 / 44

G RAFO DIRIGIDO COMPLETO

Al continuar este proceso, tenemos dos posibilidades:

(1) para algún k con 1 ≤ k ≤ m − 1 las aristas (vk , v) y (v, vk+1 ) están en Kn∗ ,
y reemplazamos la arista (vk , vk+1 ) en Pm por estas dos, y obtenemos un
camino simple de longitud m
v1 v2 v3 vm-1 vm
vk vk+1

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 25 / 44

G RAFO DIRIGIDO COMPLETO

(2) (vm , v) está en Kn∗ y la agregamos al final de Pm y conseguimos también

un camino simple con m aristas.

Si m = n entonces el teorema está demostrado.

Caso contrario aplicamos el mismo procedimiento al camino de m + 1 vértices
Pm+1 .
?
S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 26 / 44
C ONDICI ÓN NECESARIA PARA LA EXISTENCIA DE CICLO
HAMILTONIANO

T EOREMA
Sea G = (V, E) grafo no dirigido. Si G tiene un ciclo hamiltoniano, entonces
dado S ⊂ V el grafo G − S tiene a lo sumo |S| componentes conexas.

Demostración

Si existe un ciclo hamiltoniano, éste al abandonar una componente conexa de

G − S a través de S, utiliza distintos vértices de S. Por lo tanto S tiene al menos
tantos vértices como κ(G − S). Es decir κ(G − S) ≤ |S| para todo S ⊂ V no
vacı́o.
S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 27 / 44
C ONDICI ÓN NECESARIA PARA LA EXISTENCIA DE CICLO
HAMILTONIANO

Veamos los siguientes grafos

f
e j
b
g

i
h

d c
El grafo de la izquierda no satisface la condición necesaria, por lo tanto no
admite un ciclo hamiltoniano.
El grafo de Petersen (que no admite ciclo hamiltoniano) satisface la condición
necesaria (ejercicio). Vemos que esta condición no es suficiente.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 28 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE UN
CAMINO HAMILTONIANO

T EOREMA
Sea G = (V, E) grafo sin lazos, n = |V| ≥ 2. Si deg(x) + deg(y) ≥ n − 1 para
todo par {x, y} ⊂ V entonces G tiene un camino hamiltoniano.

Demostración:
Suponemos G1 y G2 dos componentes conexas de G con ni = |V(Gi )|
i = 1, 2.
Sean u ∈ V(G1 ) y v ∈ V(G2 ).
Sigue que deg(u) ≤ n1 − 1, deg(v) ≤ n2 − 1 y
deg(u) + deg(v) ≤ (n1 + n2 ) − 2 ≤ n − 2. Esto contradice la hipótesis del
teorema.
G es conexo.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 29 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE
CAMINO HAMILTONIANO

Sea m ≥ 2 y Pm el camino simple {v1 , v2 }, {v2 , v3 }, . . . , {vm−1 , vm } de longitud

m − 1.
(porque se puede asegurar existe tal camino?)

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 30 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE
CAMINO HAMILTONIANO

Si existe v 6= vi con i = 2 . . . , m tal que v ∈ N(v1 ) entonces agrego la arista

{v, v1 } a Pm y ası́ obtengo un camino de longitud m + 1.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 31 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE
CAMINO HAMILTONIANO

Del mismo modo, si existe v 6= vi con i = 1 . . . , m − 1 tal que v ∈ N(vm ),

entonces agrego la arista {vm , v} a Pm y también consigo un camino de
longitud m + 1.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 32 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE
CAMINO HAMILTONIANO

Repito este procedimiento todas las veces que sea posible.

Si al cabo del proceso se tiene que el camino tiene longitud n − 1 entonces se
trata de un camino hamiltoniano.
En caso contrario, hemos construido un camino Pm de la forma

{v1 , v2 }, {v2 , v3 }, . . . , {vm−1 , vm }

y todo v ∈ V que no pertenece al camino, no es vecino ni de v1 ni de vm .

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 33 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE
CAMINO HAMILTONIANO

Afirmación Si m < n entonces los vértices en Pm inducen un ciclo.

Si v1 y vm son adyacentes es claro que
{v1 , v2 }, {v2 , v3 }, . . . , {vm−1 , vm }, {vm , v1 } es un ciclo.
Supongamos que no son adyacentes y sea S = N(v1 ). Es claro que
S ⊂ {v2 , . . . , vm−1 } y si llamamos k = |S| entonces k < m − 1.
Si existe vt ∈ S tal que vt−1 ∈ N(vm ), entonces conseguimos el ciclo de la
figura:

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 34 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE
CAMINO HAMILTONIANO

Ahora si para cada vt ∈ S ocurre que vt−1 ∈

/ N(vm ), sigue que
deg(vm ) ≤ (m − 1) − k ya que |S| = k.
entonces tenemos

deg(v1 ) + deg(vm ) = k + deg(vm ) ≤ k + (m − 1) − k = m − 1 < n − 1.

Esto último contradice la hipótesis deg(v1 ) + deg(vm ) ≥ n − 1.
La afirmación queda demostrada.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 35 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE
CAMINO HAMILTONIANO

Ahora sabemos que los vértices en Pm inducen un ciclo y además que existe
v ∈ V que no pertenece a Pm .
G es conexo, por lo tanto existe un camino simple desde v a un vértice de Pm .
Sea vr el primer vértice en Pm de ese camino simple. Veamos en la figura:

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 36 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE
CAMINO HAMILTONIANO

Si quitamos la arista {vr−1 , vr } (o {v1 , vr } si r = t) como indica la figura

Obtenemos un camino más largo que Pm . Aplicamos el mismo procedimiento

sobre este nuevo camino simple hasta incluir a todos los vértices en V .
?

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 37 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE CICLO
HAMILTONIANO

T EOREMA
Sea G = (V, E) un grafo no dirigido sin lazos con |V| = n ≥ 3. Si
deg(x) + deg(y) ≥ n para todo par x, y ∈ V no adyacentes entonces G tiene un
ciclo hamiltoniano.

Demostración
Supongamos que G no tiene un ciclo hamiltoniano.
Agregamos aristas a G de modo de obtener un subgrafo H de Kn que
satisfaga la condición:
H no tiene ciclo hamiltoniano pero para toda arista e ∈ E(Kn ) − E(H) se tiene
que H + e tiene ciclo hamiltoniano.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 38 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE CICLO
HAMILTONIANO

Sea e = {a, b} una arista que no está en H . Sigue H + e tiene un ciclo

hamiltoniano que llamamos C.
Numeramos los vértices de H (y de G) sobre el ciclo como sigue:

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 39 / 44

C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE CICLO
HAMILTONIANO

Afirmación: Para cualquier i = 3, . . . , n si la arista {b, vi } está en H entonces

{a, vi−1 } no está en H .
Supongamos que para algún i = 3, . . . , n las aristas {b, vi } y {a, vi−1 } están
en H . Entonces obtenemos el ciclo hamiltoniano

se encuentra en H . Lo cual contradice la condición impuesta sobre H y la

afirmación queda demostrada.
S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 40 / 44
C ONDICI ÓN SUFICIENTE PARA LA EXISTENCIA DE CICLO
HAMILTONIANO

Entonces para cada i = 3, . . . , n, a lo sumo una de las aristas {b, vi } y

{a, vi−1 } está en H .
En consecuencia
degH (a) + degH (b) < n.
Es claro que degH (v) ≥ deg(v) para cualquier v ∈ V y entonces

deg(a) + deg(b) < n.

Por hipótesis deg(a) + deg(b) ≥ n puesto que no son adyacentes. Por lo tanto
G contiene un ciclo hamiltoniano.
C OROLARIO
Si G = (V, E) grafo no dirigido sin lazos tal que |V| = n, n ≥ 3 y deg(v) ≥ 2n
para todo v ∈ V , entonces G tiene un ciclo hamiltoniano.

Demostración Ejercicio.
S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 41 / 44
O UTLINE

1 D EFINICIONES Y EJEMPLOS

2 R ESULTADOS SOBRE CICLOS Y CAMINOS HAMILTONIANOS

3 U N PROBLEMA REAL ASOCIADO A CICLOS HAMILTONIANOS

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 42 / 44

E L PROBLEMA DEL VIAJANTE

Supongamos un número de ciudades y las correspondientes distancias entre

ellas. El problema del viajante o TSP (Travelling salesman problem) consiste
en encontrar un ciclo que incluya a las n ciudades y que recorra la menor
distancia posible.
Este es uno de los problemas más importantes en Optimización Combinatoria.
El origen del problema tiene como protagonista al viajante de comercio que
debe visitar un número determinado de ciudades y luego regresar a su casa
recorriendo la menor distancia, empleando el menor tiempo o el menor costo
posible.
Existen otros problemas, que si bien tienen distinta ı́ndole admiten
formulaciones similares. Por ejemplo, el problema de una máquina
agujereadora que debe realizar miles de agujeros en una placa de circuitos
electrónicos y regresar al lugar de partida. En este caso, la cantidad de tiempo
necesario para desplazar el cabezal de la máquina entre un agujero y el
siguiente, es crucial para determinar el tiempo necesario para concluir una
placa de circuitos.
S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 43 / 44
E L PROBLEMA DEL VIAJANTE

El TSP está relacionado con los circuitos hamiltonianos. Más aún, un tour
entre las n ciudades que debe visitar el viajante es precisamente un ciclo
hamiltoniano en el grafo completo determinado por las n ciudades.
El problema de la existencia de un ciclo hamiltoniano en un grafo puede
reducirse al problema del viajante.
Sea G un grafo con n nodos. Definimos la distancia entre dos nodos de la
siguiente manera: si los nodos son adyacentes la distancia es 1, si no lo son la
distancia es 2.
Si el grafo G contiene un ciclo hamiltoniano, entonces se trata de un tour de
longitud n para el TSP. Si el grafo no contiene un ciclo hamiltoniano, el tour
más corto para el TSP tiene distancia mayor o igual a n + 1.
Esto asegura que un algoritmo que resuelva en forma eficiente el TSP brinda
un criterio eficiente que determina si un grafo dado tiene un ciclo hamiltoniano.
Hasta el momento no existe un algoritmo eficiente que resuelva el TSP.

S. Bianchi (UNR) CAMINOS Y CICLOS HAMILTONIANOS 28 de marzo de 2022 44 / 44