Camino hamiltoniano

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Camino en un gráfico que visita cada vértice exactamente una vez

Un ciclo Hamiltoniano alrededor de una red de seis vértices

En el campo matemático de la teoría de grafos, un camino hamiltoniano (o camino trazable) es un camino en un gráfico dirigido o no dirigido que visita cada vértice exactamente una vez. Un ciclo hamiltoniano (o circuito hamiltoniano) es un ciclo que visita cada vértice exactamente una vez. Una ruta hamiltoniana que comienza y termina en vértices adyacentes se puede completar agregando una arista más para formar un ciclo hamiltoniano, y eliminar cualquier arista de un ciclo hamiltoniano produce una ruta hamiltoniana. Determinar si tales caminos y ciclos existen en los gráficos (el problema del camino hamiltoniano y el problema del ciclo hamiltoniano) es NP-completo.

Los caminos y ciclos hamiltonianos llevan el nombre de William Rowan Hamilton, quien inventó el juego icosiano, ahora también conocido como rompecabezas de Hamilton, que consiste en encontrar un ciclo hamiltoniano en el gráfico de borde del dodecaedro.. Hamilton resolvió este problema utilizando el cálculo icosiano, una estructura algebraica basada en raíces de unidad con muchas similitudes con los cuaterniones (también inventado por Hamilton). Esta solución no se generaliza a grafos arbitrarios.

A pesar de llevar el nombre de Hamilton, los ciclos hamiltonianos en poliedros también habían sido estudiados un año antes por Thomas Kirkman, quien, en particular, dio un ejemplo de un poliedro sin ciclos hamiltonianos. Incluso antes, los ciclos y caminos hamiltonianos en el gráfico del caballo del tablero de ajedrez, el recorrido del caballo, habían sido estudiados en el siglo IX en las matemáticas indias por Rudrata, y casi al mismo tiempo en las matemáticas islámicas por al. -Adli ar-Rumi. En la Europa del siglo XVIII, las giras de los caballeros fueron publicadas por Abraham de Moivre y Leonhard Euler.

Definiciones

Un camino hamiltoniano o camino trazable es un camino que visita cada vértice del gráfico exactamente una vez. Un gráfico que contiene un camino hamiltoniano se denomina gráfico rastreable. Un grafo es conexo hamiltoniano si por cada par de vértices existe un camino hamiltoniano entre los dos vértices.

Un ciclo hamiltoniano, circuito hamiltoniano, recorrido por vértices o ciclo gráfico es un ciclo que visita cada vértice Exactamente una vez. Un gráfico que contiene un ciclo hamiltoniano se denomina gráfico hamiltoniano.

Pueden definirse nociones similares para gráficos dirigidos, donde cada borde (arco) de un camino o ciclo solo puede trazarse en una sola dirección (es decir, los vértices están conectados con flechas y los bordes trazado "cola a cabeza").

Una descomposición hamiltoniana es una descomposición por aristas de un gráfico en circuitos hamiltonianos.

Un laberinto de Hamilton es un tipo de rompecabezas lógico en el que el objetivo es encontrar el ciclo hamiltoniano único en un gráfico dado.

Ejemplos

Proyecciones ortográficas y diagramas Schlegel con ciclos Hamiltonianos de los vértices de los cinco sólidos platónicos – sólo el octaedro tiene un camino o ciclo eulerio, extendiendo su camino con el puntado uno

Un gráfico completo con más de dos vértices es Hamiltonian
Cada gráfico de ciclo es Hamiltonian
Cada torneo tiene un número impar de caminos Hamiltonianos (Rédei 1934)
Cada sólido platónico, considerado como gráfico, es Hamiltonian
El gráfico Cayley de un grupo finito de Coxeter es Hamiltonian (Para obtener más información sobre los caminos Hamiltonianos en los gráficos de Cayley, vea la conjetura de Lovász.)
Los gráficos de Cayley sobre grupos nilpotent con subgrupo de conmutadores cíclicos son Hamiltonian.
El gráfico flip de un polígono convexo o equivalentemente, el gráfico de rotación de los árboles binarios, es Hamiltonian.

Propiedades

El gráfico Herschel es el gráfico poliedral más pequeño posible que no tiene un ciclo Hamiltoniano. Se muestra un posible camino Hamiltoniano.

Cualquier ciclo hamiltoniano se puede convertir en una ruta hamiltoniana eliminando uno de sus bordes, pero una ruta hamiltoniana se puede extender a un ciclo hamiltoniano solo si sus extremos son adyacentes.

Todos los gráficos hamiltonianos están biconectados, pero un gráfico biconectado no necesita ser hamiltoniano (ver, por ejemplo, el gráfico de Petersen).

Un grafo euleriano $G$ (un grafo conexo en el que cada vértice tiene un grado par) tiene necesariamente un recorrido euleriano, un recorrido cerrado camine pasando por cada borde de $G$ exactamente una vez. Este recorrido corresponde a un ciclo hamiltoniano en el gráfico lineal $L (G)$ , por lo que el gráfico lineal de cada gráfico euleriano es hamiltoniano. Los gráficos lineales pueden tener otros ciclos hamiltonianos que no corresponden a los recorridos de Euler y, en particular, el gráfico lineal $L (G)$ de cada gráfico hamiltoniano $G$ es en sí mismo hamiltoniano, independientemente de si el gráfico $G$ es euleriano.

Un torneo (con más de dos vértices) es hamiltoniano si y solo si está fuertemente conectado.

El número de ciclos hamiltonianos diferentes en un gráfico no dirigido completo en $n$ vértices es $(n - 1)! / 2$ y en un gráfico dirigido completo en $n$ vértices es $(n - 1)!$ . Estos recuentos asumen que los ciclos que son iguales aparte de su punto de inicio no se cuentan por separado.

Teorema de Bondy-Chvátal

La mejor caracterización del grado de vértice de los gráficos hamiltonianos fue proporcionada en 1972 por el teorema de Bondy-Chvátal, que generaliza resultados anteriores de G. A. Dirac (1952) y Øystein Ore. Tanto el teorema de Dirac como el de Ore pueden también derivarse del teorema de Pósa (1962). La hamiltonicidad se ha estudiado ampliamente en relación con varios parámetros, como la densidad del gráfico, la dureza, los subgráficos prohibidos y la distancia, entre otros parámetros. Los teoremas de Dirac y Ore básicamente establecen que un gráfico es hamiltoniano si tiene suficientes aristas.

El teorema de Bondy-Chvátal opera sobre el cierre $cl(G)$ de un grafo $G$ con $n$ vértices, obtenidos al agregar repetidamente un nuevo borde $uv$ conectando un par de vértices no adyacentes $u$ y $v$ con $grado(v) + grado(u) \geq n$ hasta que no se puedan encontrar más pares con esta propiedad.

Bondy-Chvátal Theorem (1976)—Un gráfico es Hamiltonian si y sólo si su cierre es Hamiltonian.

Como los gráficos completos son hamiltonianos, todos los gráficos cuyo cierre es completo son hamiltonianos, que es el contenido de los siguientes teoremas anteriores de Dirac y Ore.

Teorema de Dirac (1952)—Un gráfico simple con $n$ vértices $ngeq 3$ ) es Hamiltonian si cada vértice tiene grado $tfrac{n}{2}$ o mayor.

Teorema de Ore (1960)—Un gráfico simple con $n$ vértices $ngeq 3$ ) es Hamiltonian si, por cada par de vértices no adyacentes, la suma de sus grados es $n$ o mayor.

Los siguientes teoremas pueden considerarse versiones dirigidas:

Ghouila–Houiri (1960)—Un gráfico de dirección simple fuertemente conectado con $n$ vertices es Hamiltonian si cada vértice tiene un grado completo mayor o igual a $n$ .

Meyniel (1973)—Un gráfico de dirección simple fuertemente conectado con $n$ vértices es Hamiltonian si la suma de grados completos de cada par de vértices distintos no-adyacentes es mayor o igual a $2n-1$

El número de vértices debe duplicarse porque cada arista no dirigida corresponde a dos arcos dirigidos y, por lo tanto, el grado de un vértice en el gráfico dirigido es el doble del grado en el gráfico no dirigido.

Rahman–Kaykobad (2005)—Un gráfico simple con $n$ vertices tiene un camino Hamiltoniano si, por cada vértice no adyacente pare la suma de sus grados y su longitud más corta del camino es mayor que $n$ .

El teorema anterior solo puede reconocer la existencia de un camino hamiltoniano en un gráfico y no un ciclo hamiltoniano.

Muchos de estos resultados tienen analogías con los gráficos bipartitos equilibrados, en los que los grados de los vértices se comparan con el número de vértices de un solo lado de la bipartición en lugar del número de vértices del gráfico completo.

Existencia de ciclos hamiltonianos en grafos planos

Theorem—Una triangulación planaria de 4 conexiones tiene un ciclo Hamiltoniano.

Theorem—Un gráfico planar de 4 conexiones tiene un ciclo Hamiltoniano.

El polinomio del ciclo hamiltoniano

Una representación algebraica de los ciclos hamiltonianos de un dígrafo ponderado dado (a cuyos arcos se les asignan pesos de un determinado campo base) es el polinomio del ciclo hamiltoniano de su matriz de adyacencia ponderada definida como la suma de los productos de los pesos de los arcos de los Ciclos hamiltonianos de dígrafos. Este polinomio no es idénticamente cero como una función en los pesos de arco si y solo si el dígrafo es hamiltoniano. Grigoriy Kogan mostró la relación entre las complejidades computacionales de calcularlo y calcular lo permanente.

Contenido relacionado

Más resultados...