En el área matemática de la teoría de grafos , un camino inducido en un gráfico no dirigido G es un camino que es un subgrafo inducido de G. Es decir, es una secuencia de vértices en G tal que cada dos vértices adyacentes en la secuencia están conectados por una arista en G , y cada dos vértices no adyacentes en la secuencia no están conectados por ninguna arista en G. A un camino inducido a veces se le llama serpiente , y el problema de encontrar caminos inducidos largos en gráficos de hipercubo se conoce como el problema de la serpiente en la caja .
De manera similar, un ciclo inducido es un ciclo que es un subgrafo inducido de G ; Los ciclos inducidos también se denominan ciclos sin cuerdas o (cuando la duración del ciclo es de cuatro o más) agujeros . Un antiagujero es un hueco en el complemento de G , es decir, un antiagujero es un complemento de un hueco.
La longitud del camino inducido más largo en un gráfico a veces se ha denominado número de desvío del gráfico; [1] para gráficos dispersos , tener un número de desvío acotado es equivalente a tener una profundidad de árbol acotada . [2] El número de camino inducido de un gráfico G es el número más pequeño de caminos inducidos en los que se pueden dividir los vértices del gráfico, [3] y el número de cobertura de camino estrechamente relacionado de G es el número más pequeño de caminos inducidos que juntos incluir todos los vértices de G . [4] La circunferencia de un gráfico es la longitud de su ciclo más corto, pero este ciclo debe ser un ciclo inducido ya que cualquier cuerda podría usarse para producir un ciclo más corto; por razones similares, la circunferencia impar de un gráfico es también la longitud de su ciclo inducido impar más corto.
La ilustración muestra un cubo, una gráfica con ocho vértices y doce aristas, y una trayectoria inducida de longitud cuatro en esta gráfica. Un análisis de caso sencillo muestra que ya no puede haber un camino inducido en el cubo, aunque tiene un ciclo inducido de longitud seis. El problema de encontrar el camino o ciclo inducido más largo en un hipercubo, planteado por primera vez por Kautz (1958), se conoce como el problema de la serpiente en la caja y ha sido estudiado extensamente debido a sus aplicaciones en la teoría de la codificación y la ingeniería. .
Muchas familias de gráficos importantes se pueden caracterizar en términos de las trayectorias o ciclos inducidos de los gráficos de la familia.
Es NP-completo determinar, para un gráfico G y parámetro k , si el gráfico tiene una ruta inducida de longitud al menos k . Garey y Johnson (1979) atribuyen este resultado a una comunicación inédita de Mihalis Yannakakis . Sin embargo, este problema se puede resolver en tiempo polinomial para ciertas familias de gráficos, como gráficos sin asteroides triples [5] o gráficos sin agujeros largos. [6]
También es NP-completo determinar si los vértices de un gráfico se pueden dividir en dos caminos inducidos o dos ciclos inducidos. [7] Como consecuencia, determinar el número de ruta inducida de un gráfico es NP-difícil.
La complejidad de aproximar los problemas de ciclo o trayectoria inducida más larga se puede relacionar con la de encontrar grandes conjuntos independientes en gráficos, mediante la siguiente reducción. [8] A partir de cualquier gráfico G con n vértices, forme otro gráfico H con el doble de vértices que G , sumando a G n ( n − 1)/2 vértices que tengan dos vecinos cada uno, uno para cada par de vértices en G . Entonces , si G tiene un conjunto independiente de tamaño k , H debe tener un camino inducido y un ciclo inducido de longitud 2 k , formado por la alternancia de vértices del conjunto independiente en G con vértices de I. Por el contrario, si H tiene un camino o ciclo inducido de longitud k , cualquier conjunto máximo de vértices no adyacentes en G de este camino o ciclo forma un conjunto independiente en G de tamaño al menos k /3. Por lo tanto, el tamaño del conjunto independiente máximo en G está dentro de un factor constante del tamaño del camino inducido más largo y del ciclo inducido más largo en H. Por lo tanto, según los resultados de Håstad (1996) sobre la inaproximabilidad de conjuntos independientes, a menos que NP=ZPP, no existe un algoritmo de tiempo polinomial para aproximar el camino inducido más largo o el ciclo inducido más largo dentro de un factor de O( n 1/ 2-ε ) de la solución óptima.
Los agujeros (y antiagujeros en gráficos sin ciclos sin cuerdas de longitud 5) en un gráfico con n vértices y m aristas se pueden detectar en el tiempo (n+m 2 ). [9]
Los ciclos atómicos son una generalización de los ciclos sin cuerdas, que no contienen n -cordas. Dado un ciclo, una cuerda n se define como un camino de longitud n que conecta dos puntos del ciclo, donde n es menor que la longitud del camino más corto del ciclo que conecta esos puntos. Si un ciclo no tiene n cuerdas, se llama ciclo atómico porque no se puede descomponer en ciclos más pequeños. [10] En el peor de los casos, los ciclos atómicos en un gráfico se pueden enumerar en tiempo O ( m 2 ), donde m es el número de aristas en el gráfico.