DSC_MDI_U2_02

Vista previa del material en texto

1
Matemáticas discretas
Unidad 2. Grafos y árboles
2.2. Caminos y circuitos 
2.2.4. Circuito de Hamilton
Ejemplo de circuito de Hamilton
Los siguientes ejemplos muestran casos de grafos con un circuito Hamiltoniano y otro que no lo tiene. El grafo 
de la Figura (a) tiene un circuito Hamiltoniano, el circuito (1, 2, 3, 4, 5, 1) es un circuito Hamiltoniano. El grafo 
de la Figura (b) no tiene un circuito Hamiltoniano; para producir un circuito Hamiltoniano en este grafo será 
necesario eliminar dos aristas, una incidente en el vértice v2 y otra incidente en el vértice v4.
Grafo (a) con circuito Hamiltoniano, y (b) sin circuito Hamiltoniano.
Educación Superior Abierta y a Distancia • Ciencias Exactas, Ingenierías y Tecnología