Deberes


Circuito de Hamilton
Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.
El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario sesabe que es NP-completo.
Los caminos y ciclos hamiltonianos se llaman así en honor de William Rowan Hamilton, inventor de un juego que consistía en encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, aunque su solución no era generalizable a todos los grafos.
Índice
• 1 Definición
• 2 Ejemplos
• 3 Notas
• 4 Teorema deBondy-Chvátal
• 5 Referencias
Definición
Un camino hamiltoniano es un camino que pasa por cada vértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano si es un ciclo que pasa por cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.
Estosconceptos se pueden extender para los grafos dirigidos los cuales son igual a un carro.
Existe una relación simple entre los problemas de encontrar un camino de Hamilton y un ciclo Hamiltoniano. En una dirección, el problema del camino Hamiltoniano para el grafo G es equivalente al problema ciclo Hamiltoniano en un grafo H obtenido de G mediante la adición de un nuevo vértice y de la conexión atodos los vértices de G. Por lo tanto, la búsqueda de un camino de Hamilton no puede ser significativamente más lenta (n el peor de los casos, como una función del número de vértices) que encontrar un ciclo de Hamilton.
En la otra dirección, un grafo G tiene un ciclo de Hamilton utilizando la arista uv y sólo si el grafo H es obtenido por G mediante la sustitución de la arista por un par devértices de grado 1, uno conectado a u y el otro conectado a v, tiene un camino de Hamilton. Por lo tanto, al tratar esta sustitución para todas las aristas incidentes hasta cierto vértice seleccionado de G, el problema del ciclo Hamiltoniano puede ser resuelto como máximo por n cálculos en la mayoría de los caminos Hamiltonianos, donde n es el número de vértices en el grafo.
El problema del Ciclohamiltoniano es también un caso especial del Problema del viajante, obtenido mediante el establecimiento de la distancia entre dos ciudades a uno si son adyacentes y dos en otro caso, y la verificación de que la distancia total recorrida es igual a n (si es así, la ruta es un circuito hamiltoniano; si no hay circuito Hamiltoniano a continuación entonces la ruta más corta será más larga).Algoritmos[editar]
Hay n! diferentes secuencias de vértices que pueden ser caminos Hamiltonianos dado un grafo de n vertices (y son, en un grafo completo), por lo que un algoritmo de búsqueda de fuerza bruta que pone a prueba todas las posibles secuencias serían muy lento. Hay varios enfoques más rápidos. Un procedimiento de búsqueda por Frank Rubin2 divide a las aristas del grafo en tres clases: los que debenestar en el camino, los que no pueden estar en el camino, e indecisos. A medida que procede la búsqueda, un conjunto de reglas de decisión que clasifica las aristas indecisas, y determina si se debe detener o continuar la búsqueda. El algoritmo divide el grafo en componentes que pueden ser resueltas por separadas. Además, un algoritmo de programación dinámica de Bellman, Held, y Karp puede serutilizado para resolver el problema en un tiempo O(n2 2n). En este método, se determina, para cada conjunto S de vértices y cada vértice v en S, si existe un camino que cubre exactamente los vértices en S y termina en v. Para cada elección de S y v, existe un camino para (S,v) si y sólo si v tiene un vecino w tal que existe un camino para (S − v,w), que puede ser visto de la información ya...