Demuestre que ninguna gráfica contiene un ciclo hamiltoniano.
Determine si cada gráfica contiene un ciclo de Hamilton. Si así es, exhiba
uno; de otra manera, dé un argumento para demostrar que no hay
un ciclo de Hamilton.
9. Dé un ejemplo de una gráfica que tiene un ciclo de Euler pero no
contenga un ciclo de Hamilton.
10. Dé un ejemplo de una gráfica que tiene un ciclo de Euler que también
es un ciclo de Hamilton.
11. Dé un ejemplo de una gráfica que tiene un ciclo de Euler y un ciclo
de Hamilton que no son idénticos.
12. ¿Para qué valores de m y n la gráfica del ejercicio 37, sección 8.2,
contiene un ciclo de Hamilton?
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 obtenida
siempre tiene un ciclo de Hamilton.
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 hamiltoniano?
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.
n tiene un ciclo simple de longitud m si y sólo si m ≥ 4 y m es
par.
19. Use el Teorema 8.3.6 para calcular el código Gray G4.
20. Sea G una gráfica bipartita con conjuntos ajenos de vértices V1 y
V2, como en la definición 8.1.11. Demuestre que si G tiene un ciclo
de Hamilton, V1 y V2 tienen el mismo número de elementos.
21. Encuentre un ciclo de Hamilton en GK6 (vea el ejemplo 8.3.9).
22. Describa un modelo de gráficas adecuado para resolver el siguiente
problema: ¿Pueden arreglarse las permutaciones de {1, 2, . . . , n}
en una sucesión de manera que las permutaciones adyacentes
p: p1, . . . , pn y q: q1, . . . , qn
satisfagan pi qi para i = 1, . . . , n?
23. Resuelva el problema del ejercicio 22 para n = 1, 2, 3, 4. (La respuesta
a la pregunta es “sí” para n ≥ 5; vea [problema 1186] en las
referencias).
24. Demuestre que las etiquetas consecutivas de los vértices en el
círculo unitario de la descripción de Bain del cubo-n dan un código
Gray (vea los ejercicios 43 a 45, sección 8.1).
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 trayectoria
de Hamilton inicia y termina en vértices diferentes).
25. Si una gráfica tiene ciclo de Hamilton, ¿debe tener una trayectoria
de Hamilton? Explique.
ciclo de Hamilton? Explique.
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?
29. ¿La gráfica del ejercicio 3 tiene una trayectoria de Hamilton?
30. ¿La gráfica del ejercicio 4 tiene una trayectoria de Hamilton?
31. ¿La gráfica del ejercicio 5 tiene una trayectoria de Hamilton?
32. ¿La gráfica del ejercicio 6 tiene una trayectoria de Hamilton?
33. ¿La gráfica del ejercicio 7 tiene una trayectoria de Hamilton?
34. ¿La gráfica del ejercicio 8 tiene una trayectoria de Hamilton?
35. ¿Para qué valores de m y n la gráfica del ejercicio 37, sección 8.2,
tiene una trayectoria de Hamilton?
36. ¿Para qué valor de n la gráfica completa sobre n vértices tiene una
trayectoria de Hamilton?
