ciclos_ de_hamilton

Vista previa del material en texto

UNSL MATEMATICA DISCRETA 2018
TRABAJO PRACTICO
Grafos
Ciclos de Hamilton
1. En la figura 1, determinar si cada grafo contiene un ciclo de Hamilton. Si es aśı, exhibir uno; en
otro caso, dar un argumento para demostrar que no lo hay.
a b c
d e
f
g
h
i j
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
a
b
c
d
e f g h
i
j
k
l
a b
c
d
ef
g
h
i j
kl
m
Figura 1
2. La terminoloǵıa de circuito de Hamilton viene de un juego, llamado The Icosian Puzzle, inventado
en 1857 por el matemático irlandés Sir William Rowan Hamilton. Este consist́ıa de un dodecahedro
con una clavija en cada vértice y una cuerda. Los 20 vértices del dodecahedro estaban etiquetados
con los nombres de diferentes ciudades del mundo. El objetivo del rompecabezas era comenzar en
una ciudad y viajar a lo largo de las aristas del dodecahedro, visitando cada una de las 19 ciudades
restantes exactamente una vez, y regresar a la primera ciudad. El circuito recorido se marcaba
usando la cuerda y las clavijas. Una versión bidimensional del grafo formado por los 20 vértices y
las aristas del dodecahedro se muestra en la figura 2. Hallar un circuito de Hamilton en este grafo.
Figura 2
3. En cada caso, dar un ejemplo de un grafo que verifique la condición requerida.
1
UNSL MATEMATICA DISCRETA 2018
(a) Que contenga un ciclo de Euler pero no uno de Hamilton.
(b) Que contenga un ciclo de Hamilton pero no uno de Euler.
(c) Que contenga un ciclo de Euler que también sea un ciclo de Hamilton.
(d) Que contenga un ciclo de Euler y un ciclo de Hamilton que no sean iguales.
4. (a) Dar un argumento que muestre que si n ¥ 3, el grafo completo sobre n vértices Kn contiene
un ciclo de Hamilton.
(b) ¿Cuándo el grafo completo bipartito Km,n contiene un ciclo de Hamilton?
5. (a) Sea G un grafo bipartito conectado con V pGq particionado como tV1, V2u. Poabar que si
cardpV1q � cardpV2q entonces G no puede tener un ciclo de Hamilton.
(b) Probar que si el grafo del inciso anterior tiene un camino de Hamilton, entonces | cardpV1q �
cardpV2q| � 1.
(c) Dar un ejemplo un grafo bipartito conectado G con V pGq particionado como tV1, V2u y
cardpV1q � cardpV2q � 1, pero que no tenga un camino de Hamilton.
6. Resolver el problema del agente viajero para el grafo de la figura 3
ab
c
de
3
6
4
5
4
6
5
7
7
2
Figura 3
7. Una trayectoria de Hamilton en un grafo G es una trayectoria simple que contiene a todos los
vértices en G exactamente una vez.
(a) Si un grafo contiene un ciclo de Hamilton, ¿debe contener una trayectoria de Hamilton? Jus-
tificar la respuesta.
(b) Si un grafo contiene una trayectoria de Hamilton, ¿debe contener un ciclo de Hamilton? Jus-
tificar la respuesta.
8. Probar el siguiente resultado
Teorema (Ore, 1960) Sea G � pV,Eq un grafo simple con cardpV pGqq � n ¥ 3. Si degpxq �
degpyq ¥ n para todo x, y P V pGq tales que tx, yu R EpGq, entonces G contiene un ciclo de Hamilton.
9. Demostrar con un ejemplo que la afirmación rećıproca del Teorema de Ore es falsa.
10. Probar el siguiente resultado
Teorema (Dirac, 1952) Sea G � pV,Eq un grafo simple con cardpV pGqq � n ¥ 3. Si degpxq ¥ n2
para todo x P V pGq, entonces G contiene un ciclo de Hamilton.
11. Probar el siguiente resultado
Teorema Sea G � pV,Eq un grafo simple con cardpV pGqq � n ¥ 3. Si cardpEpGqq ¥ Cpn �
1, 2q � 2, entonces G contiene un ciclo de Hamilton.
2
UNSL MATEMATICA DISCRETA 2018
12. Probar que Kr;2r;3r tiene un ciclo de Hamilton para todo r P N.
13. Sea G � pV,Eq un grafo simple r-regular con cardpV pGqq ¥ 2r� 2. Probar que G tiene un ciclo de
Hamilton.
14. (a) Mostrar que el grafo de Petersen, figura 4, no tiene un ciclo de Hamilton, pero tiene un camino
de Hamilton.
(b) Mostrar que si cualquier vértice (y las aristas incidentes en el) es removido del grafo de Petersen
entonces el subgrafo resultante tiene un ciclo de Hamilton.
Figura 4
15. Considerar el grafo G de la figura 5 y sea w � tpta, bu, 3q, pta, eu, 5q, pta, hu, 4q, ptb, cu, 2q,
ptb, eu, 5q, ptb, fu, 7q, ptc, du, 3q, ptc, fu, 2q, ptc, gu, 6q, ptd, gu, 7q, ptd, zu, 2q, pte, fu, 4q, pte, hu, 7q,
ptf, gu, 4q, ptf, hu, 5q, ptf, iu, 4q, ptf, ju, 3q, ptg, zu, 6q, ptg, ju, 4q, pth, iu, 2q, pti, ju, 6q, ptj, zu, 5q una
función de peso definida sobre EpGq. Encontrar en G � pV,E,wq la longitud de una ruta más corta
entre el par de vértices que se indica
(a) pa, fq. (b) pa, zq. (c) pb, jq. (d) ph, dq.
a
b c d
e f g
h i j
z
Figura 5
16. Mostrar que el Algoritmo de Dijkstra puede fallar si hay aristas con pesos negativos.
17. Explicar cómo hallar un camino con el menor número de aristas entre dos vértices en un grafo no
dirigido tratándolo como un problema de trayectoria más corta en un grafo ponderado.
18. Extender el Algoritmo de Dijkstra para hallar la longitud de una trayectoria más corta entre dos
vértices en un grafo simple ponderado conectado, de manera que sea hallada la longitud de una
trayectoria más corta entre el vértice a y cualquier otro vértice.
19. Extender el Algoritmo de Dijkstra para hallar la longitud de una trayectoria más corta entre dos
vértices en un grafo simple conectado, de manera que sea construida una trayectoria más corta
entre esos vértices.
3