En teoría de grafos , un ciclo en un grafo es un camino no vacío en el que solo el primer y el último vértice son iguales. Un ciclo dirigido en un grafo dirigido es un camino dirigido no vacío en el que solo el primer y el último vértice son iguales.
Un grafo sin ciclos se llama grafo acíclico . Un grafo dirigido sin ciclos dirigidos se llama grafo acíclico dirigido . Un grafo conexo sin ciclos se llama árbol .
Un ciclo sin cuerdas en un grafo, también llamado agujero o ciclo inducido, es un ciclo tal que ningún par de vértices del ciclo está conectado por una arista que no pertenece al ciclo. Un antiagujero es el complemento de un agujero de grafo. Los ciclos sin cuerdas se pueden utilizar para caracterizar grafos perfectos : por el teorema fuerte del grafo perfecto , un grafo es perfecto si y solo si ninguno de sus agujeros o antiagujeros tiene un número impar de vértices mayor que tres. Un grafo cordal , un tipo especial de grafo perfecto, no tiene agujeros de ningún tamaño mayor que tres.
La circunferencia de un grafo es la longitud de su ciclo más corto; este ciclo es necesariamente sin cuerdas. Las jaulas se definen como los grafos regulares más pequeños con combinaciones dadas de grado y circunferencia.
Un ciclo periférico es un ciclo en un grafo con la propiedad de que cada dos aristas que no están en el ciclo pueden conectarse mediante un camino cuyos vértices interiores evitan el ciclo. En un grafo que no se forma añadiendo una arista a un ciclo, un ciclo periférico debe ser un ciclo inducido.
El término ciclo también puede referirse a un elemento del espacio de ciclos de un grafo. Hay muchos espacios de ciclos, uno para cada cuerpo o anillo de coeficientes. El más común es el espacio de ciclos binario (usualmente llamado simplemente espacio de ciclos ), que consiste en los conjuntos de aristas que tienen grado par en cada vértice; forma un espacio vectorial sobre el cuerpo de dos elementos . Por el teorema de Veblen , cada elemento del espacio de ciclos puede formarse como una unión disjunta de aristas de ciclos simples. Una base de ciclos del grafo es un conjunto de ciclos simples que forma una base del espacio de ciclos. [2]
Utilizando ideas de la topología algebraica , el espacio de ciclo binario se generaliza a espacios vectoriales o módulos sobre otros anillos como los números enteros, racionales o reales, etc. [3]
La existencia de un ciclo en grafos dirigidos y no dirigidos se puede determinar si una búsqueda en profundidad (DFS) encuentra una arista que apunta a un ancestro del vértice actual (es decir, contiene una arista posterior ). [4] Todas las aristas posteriores que DFS omite son parte de ciclos. [5] En un grafo no dirigido, la arista hacia el padre de un nodo no debe contarse como una arista posterior, pero encontrar cualquier otro vértice ya visitado indicará una arista posterior. En el caso de grafos no dirigidos, solo se requiere tiempo O ( n ) para encontrar un ciclo en un grafo de n -vértices, ya que como máximo n − 1 aristas pueden ser aristas de árbol.
Muchos algoritmos de ordenamiento topológico también detectarán ciclos, ya que estos son obstáculos para que exista un orden topológico. Además, si un grafo dirigido se ha dividido en componentes fuertemente conectados , los ciclos solo existen dentro de los componentes y no entre ellos, ya que los ciclos están fuertemente conectados. [5]
Para los gráficos dirigidos, se pueden utilizar algoritmos distribuidos basados en mensajes. Estos algoritmos se basan en la idea de que un mensaje enviado por un vértice en un ciclo volverá a sí mismo. Los algoritmos de detección de ciclos distribuidos son útiles para procesar gráficos a gran escala utilizando un sistema de procesamiento de gráficos distribuido en un clúster de computadoras (o supercomputadora).
Las aplicaciones de detección de ciclos incluyen el uso de gráficos de espera para detectar bloqueos en sistemas concurrentes. [6]
El uso mencionado anteriormente de la búsqueda en profundidad para encontrar un ciclo se puede describir de la siguiente manera:
Para cada vértice v: visitado(v) = terminado(v) = falsoPara cada vértice v: DFS(v)
dónde
Función diferencial(v) = si esta terminado(v): regresar Si se visita (v): "Ciclo encontrado" devolver visitado(v) = verdadero para cada vecino w: DFS(w) terminado(v) = verdadero
En el caso de los grafos no dirigidos, "vecino" significa todos los vértices conectados a v , excepto el que invocó recursivamente DFS(v) . Esta omisión impide que el algoritmo encuentre un ciclo trivial de la forma v → w → v ; estos existen en todos los grafos no dirigidos con al menos una arista.
Una variante que utilice la búsqueda en amplitud encontrará un ciclo con la menor longitud posible.
En su artículo de 1736 sobre los Siete Puentes de Königsberg , considerado ampliamente como el nacimiento de la teoría de grafos, Leonhard Euler demostró que, para que un grafo finito no dirigido tenga un recorrido cerrado que visite cada arista exactamente una vez (lo que lo convierte en un sendero cerrado), es necesario y suficiente que esté conectado excepto por los vértices aislados (es decir, todas las aristas están contenidas en un componente) y tenga un grado par en cada vértice. La caracterización correspondiente para la existencia de un recorrido cerrado que visite cada arista exactamente una vez en un grafo dirigido es que el grafo esté fuertemente conectado y tenga el mismo número de aristas entrantes y salientes en cada vértice. En cualquier caso, el sendero cerrado resultante se conoce como sendero euleriano . Si un grafo finito no dirigido tiene un grado par en cada uno de sus vértices, independientemente de si está conectado, entonces es posible encontrar un conjunto de ciclos simples que juntos cubran cada arista exactamente una vez: este es el teorema de Veblen . [7] Cuando un grafo conexo no cumple las condiciones del teorema de Euler, se puede encontrar, no obstante, en tiempo polinomial un recorrido cerrado de longitud mínima que cubra cada arista al menos una vez, resolviendo el problema de inspección de ruta .
El problema de encontrar un único ciclo simple que cubra cada vértice exactamente una vez, en lugar de cubrir las aristas, es mucho más difícil. Un ciclo de este tipo se conoce como ciclo hamiltoniano y determinar si existe es NP-completo . [8] Se han publicado muchas investigaciones sobre las clases de grafos que se puede garantizar que contienen ciclos hamiltonianos; un ejemplo es el teorema de Ore que dice que siempre se puede encontrar un ciclo hamiltoniano en un grafo para el cual cada par de vértices no adyacentes tiene grados que suman al menos el número total de vértices en el grafo. [9]
La conjetura de doble recubrimiento de ciclos establece que, para cada grafo sin puentes , existe un multiconjunto de ciclos simples que cubre cada arista del grafo exactamente dos veces. Demostrar que esto es cierto (o encontrar un contraejemplo) sigue siendo un problema abierto. [10]
Varias clases importantes de grafos pueden definirse o caracterizarse por sus ciclos. Entre ellas se incluyen: