Ejercicios
Encuentre un ciclo hamiltoniano en cada gráfica. 2.
1. a i
h
a b c j b
g
o
f p
d e h f n
g l k c
m
i j d
e
Prof. Marco Tigre ITS Sucúa
346 Capítulo 8 ◆ Teoría de gráficas
Demuestre que ninguna gráfica contiene un ciclo hamiltoniano. 8.
a b
3.
a
b c d d
c e
e f g h
i j k f g
4. 9. Dé un ejemplo de una gráfica que tiene un ciclo de Euler pero no
contenga un ciclo de Hamilton.
a b
10. Dé un ejemplo de una gráfica que tiene un ciclo de Euler que tam-
c d bién es un ciclo de Hamilton.
e 11. Dé un ejemplo de una gráfica que tiene un ciclo de Euler y un ci-
h
f g i k clo de Hamilton que no son idénticos.
j
l ★12. ¿Para qué valores de m y n la gráfica del ejercicio 37, sección 8.2,
m n contiene un ciclo de Hamilton?
o p 13. Modifique la gráfica del ejercicio 37, sección 8.2, insertando una
arista entre el vértice en la fila i, columna 1, y el vértice en la fila
i, columna m, para i = 1, . . . , n. Demuestre que la gráfica obte-
5.
nida siempre tiene un ciclo de Hamilton.
a b c d e 14. Demuestre que si n ≥ 3, la gráfica completa sobre n vértices Kn
contiene un ciclo hamiltoniano.
15. ¿Cuándo la gráfica completa bipartita Km,n contiene un ciclo ha-
miltoniano?
f g h
16. Demuestre que el ciclo (e, b, a, c, d, e) proporciona una solución
al problema del agente viajero para la gráfica mostrada.
i j
d 5 e
7 4
Determine si cada gráfica contiene un ciclo de Hamilton. Si así es, ex- 3
6 6
hiba uno; de otra manera, dé un argumento para demostrar que no hay 8
4 c 7
un ciclo de Hamilton.
6. a 5 b
a b
17. Resuelva el problema del agente viajero para la gráfica dada.
h i j c a
m 5
g l k d 3 4
6
b c d
4 7
f e 7
5 2
7. 6 e
★18. Sean m y n enteros que satisfacen 1 ≤ m ≤ 2n. Pruebe que el cu-
a b c bo-n tiene un ciclo simple de longitud m si y sólo si m ≥ 4 y m es
e f par.
d g 19. Use el Teorema 8.3.6 para calcular el código Gray G4.
h i j l 20. Sea G una gráfica bipartita con conjuntos ajenos de vértices V1 y
k m
V2, como en la definición 8.1.11. Demuestre que si G tiene un ci-
n o clo de Hamilton, V1 y V2 tienen el mismo número de elementos.
p q r
21. Encuentre un ciclo de Hamilton en GK6 (vea el ejemplo 8.3.9).
s t 22. Describa un modelo de gráficas adecuado para resolver el siguien-
te problema: ¿Pueden arreglarse las permutaciones de {1, 2, . . . , n}
Prof. Marco Tigre ITS Sucúa
8.4 ◆ Un algoritmo de la ruta más corta 347
en una sucesión de manera que las permutaciones adyacentes 26. Si una gráfica tiene una trayectoria de Hamilton, ¿debe tener un
ciclo de Hamilton? Explique.
p: p 1 , . . . , pn y q: q1 , . . . , qn 27. ¿La gráfica de la figura 8.3.5 tiene una trayectoria de Hamilton?
28. ¿La gráfica de la figura 8.3.7 tiene una trayectoria de Hamilton?
satisfagan pi qi para i = 1, . . . , n?
29. ¿La gráfica del ejercicio 3 tiene una trayectoria de Hamilton?
23. Resuelva el problema del ejercicio 22 para n = 1, 2, 3, 4. (La res-
puesta a la pregunta es “sí” para n ≥ 5; vea [problema 1186] en las 30. ¿La gráfica del ejercicio 4 tiene una trayectoria de Hamilton?
referencias). 31. ¿La gráfica del ejercicio 5 tiene una trayectoria de Hamilton?
24. Demuestre que las etiquetas consecutivas de los vértices en el 32. ¿La gráfica del ejercicio 6 tiene una trayectoria de Hamilton?
círculo unitario de la descripción de Bain del cubo-n dan un códi-
33. ¿La gráfica del ejercicio 7 tiene una trayectoria de Hamilton?
go Gray (vea los ejercicios 43 a 45, sección 8.1).
34. ¿La gráfica del ejercicio 8 tiene una trayectoria de Hamilton?
Una trayectoria de Hamilton en una gráfica G es un trayectoria simple
que contiene todos los vértices en G exactamente una vez. (Una trayec- 35. ¿Para qué valores de m y n la gráfica del ejercicio 37, sección 8.2,
toria de Hamilton inicia y termina en vértices diferentes). tiene una trayectoria de Hamilton?
25. Si una gráfica tiene ciclo de Hamilton, ¿debe tener una trayecto- 36. ¿Para qué valor de n la gráfica completa sobre n vértices tiene una
ria de Hamilton? Explique. trayectoria de Hamilton?
Prof. Marco Tigre ITS Sucúa
