En el área matemática de la teoría de grafos , un camino inducido en un grafo no dirigido G es un camino que es un subgrafo inducido de G. Es decir, es una secuencia de vértices en G de modo 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. Un camino inducido a veces se denomina serpiente , y el problema de encontrar caminos inducidos largos en grafos 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 longitud del ciclo es cuatro o más) agujeros . Un antiagujero es un agujero en el complemento de G , es decir, un antiagujero es un complemento de un agujero.
La longitud del camino inducido más largo en un grafo a veces se ha llamado el número de desvío del grafo; [1] para grafos 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 grafo G es el número más pequeño de caminos inducidos en los que se pueden dividir los vértices del grafo, [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 incluyen todos los vértices de G. [4] La circunferencia de un grafo 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 grafo es también la longitud de su ciclo inducido impar más corto.
La ilustración muestra un cubo, un grafo con ocho vértices y doce aristas, y una trayectoria inducida de longitud cuatro en este grafo. Un análisis de caso sencillo muestra que ya no puede haber una trayectoria inducida en el cubo, aunque tiene un ciclo inducido de longitud seis. El problema de encontrar la trayectoria 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 se ha estudiado ampliamente debido a sus aplicaciones en la teoría de 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 grafo G y parámetro k , si el grafo tiene una trayectoria 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 grafos, como los grafos sin triples asteroidales [5] o los grafos 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 camino inducido de un gráfico es NP-difícil.
La complejidad de aproximar los problemas de camino o ciclo inducido más largo se puede relacionar con la de encontrar grandes conjuntos independientes en grafos, mediante la siguiente reducción. [8] A partir de cualquier grafo G con n vértices, forme otro grafo H con el doble de vértices que G , añadiendo 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 alternando vértices del conjunto independiente en G con vértices de I . A la inversa, si H tiene un camino o ciclo inducido de longitud k , cualquier conjunto máximo de vértices no adyacentes en G a partir 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 el 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 la trayectoria inducida más larga 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 -cuerdas. Dado un ciclo, una n -cuerda se define como un camino de longitud n que conecta dos puntos en el ciclo, donde n es menor que la longitud del camino más corto en el 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 grafo se pueden enumerar en tiempo O( m 2 ), donde m es el número de aristas en el grafo.