Ciclo (teoría de grafos)

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án conectados por una arista que no pertenece al ciclo. Un antiagujero es el complemento de un agujero del grafo. Los ciclos sin cuerdas pueden usarse para caracterizar grafos perfectos : según el teorema del grafo perfecto fuerte , 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 tamaño mayor que tres.

La circunferencia de un grafo es la longitud de su ciclo más corto; este ciclo necesariamente carece de 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 que posee la propiedad de que cualquier par de aristas que no pertenecen al 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. Existen muchos espacios de ciclos, uno para cada cuerpo de coeficientes o anillo. El más común es el espacio de ciclos binario (generalmente llamado simplemente espacio de ciclos ), que consta de los conjuntos de aristas que tienen grado par en cada vértice; forma un espacio vectorial sobre el cuerpo de dos elementos . Según 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 ciclos binarios 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 por si una búsqueda en profundidad (DFS) encuentra una arista que apunta a un ancestro del vértice actual (es decir, contiene una arista de retroceso ). ^{[ 4 ]} Todas las aristas de retroceso que DFS omite son parte de ciclos. ^{[ 5 ]} En un grafo no dirigido, la arista al padre de un nodo no debe contarse como una arista de retroceso, pero encontrar cualquier otro vértice ya visitado indicará una arista de retroceso. En el caso de grafos no dirigidos, solo se requiere un 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 ordenación topológica también detectan ciclos, ya que estos son obstáculos para la existencia del orden topológico. Además, si un grafo dirigido se ha dividido en componentes fuertemente conexas , los ciclos solo existen dentro de las componentes y no entre ellas, dado que los ciclos están fuertemente conexos. ^{[ 5 ]}

Para grafos 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 regresará a sí mismo. Los algoritmos distribuidos de detección de ciclos son útiles para procesar grafos a gran escala mediante un sistema de procesamiento de grafos distribuido en un clúster de computadoras (o supercomputadora ).

Las aplicaciones de la detección de ciclos incluyen el uso de grafos de espera para detectar interbloqueos en sistemas concurrentes. ^{[ 6 ]}

Para cada vértice v: visitado(v) = terminado(v) = falso Para cada vértice v: DFS(v)

DFS(v) = si finalizado(v): devolver si se visitó(v): "Ciclo encontrado" devolver visitado(v) = verdadero para cada vecino w: DFS(w) terminado(v) = verdadero

En su artículo de 1736 sobre los Siete Puentes de Königsberg , ^{[ 7 ]} ampliamente considerado como el nacimiento de la teoría de grafos, ^{[ 8 ] [ 9 ]} Leonhard Euler demostró que, para que un grafo finito no dirigido tenga un camino cerrado que visite cada arista exactamente una vez (haciéndolo un sendero cerrado), es necesario y suficiente que sea conexo excepto por vértices aislados (es decir, todas las aristas están contenidas en un componente) y tenga grado par en cada vértice. ^{[ 7 ]} La ​​caracterización correspondiente para la existencia de un camino cerrado que visite cada arista exactamente una vez en un grafo dirigido es que el grafo sea fuertemente conexo y tenga igual 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 grado par en cada uno de sus vértices, independientemente de si es conexo, entonces es posible encontrar un conjunto de ciclos simples que juntos cubren cada arista exactamente una vez: este es el teorema de Veblen . ^{[ 10 ]} Cuando un grafo conexo no cumple las condiciones del teorema de Euler, se puede encontrar, sin embargo, un camino cerrado de longitud mínima que cubra cada arista al menos una vez en tiempo polinomial resolviendo el problema de inspección de ruta .

El problema de encontrar un ciclo simple que recorra cada vértice exactamente una vez, en lugar de recorrer las aristas, es mucho más difícil. Dicho ciclo se conoce como ciclo hamiltoniano , y determinar si existe es un problema NP-completo . ^{[ 11 ]} Se han publicado numerosas investigaciones sobre clases de grafos que garantizan la presencia de ciclos hamiltonianos; un ejemplo es el teorema de Ore, que establece que siempre se puede encontrar un ciclo hamiltoniano en un grafo cuyos grados, sumados para cada par de vértices no adyacentes, sean al menos iguales al número total de vértices del grafo. ^{[ 12 ]}

La conjetura de la doble cobertura cíclica afirma 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. ^{[ 13 ]}

Varias clases importantes de grafos pueden definirse o caracterizarse por sus ciclos. Estas incluyen:

• Grafo bipartito , un grafo sin ciclos impares (ciclos con un número impar de vértices).
• Grafo de cactus , un grafo en el que cada componente biconectada no trivial es un ciclo.
• Gráfico cíclico , un gráfico que consta de un solo ciclo.
• Grafo cordal , un gráfico en el que cada ciclo inducido es un triángulo.
• Grafo acíclico dirigido , un grafo dirigido sin ciclos dirigidos.
• Bosque , un grafo sin ciclos
• Gráfico de línea perfecta , un gráfico en el que cada ciclo impar es un triángulo.
• Grafo perfecto , un grafo sin ciclos inducidos o sus complementos de longitud impar mayor que tres.
• Pseudobosque , un grafo en el que cada componente conectado tiene como máximo un ciclo.
• Grafo estrangulado , un grafo en el que cada ciclo periférico es un triángulo.
• Grafo fuertemente conectado , un grafo dirigido en el que cada arista forma parte de un ciclo.
• Grafo libre de triángulos , un grafo sin ciclos de tres vértices.
• Grafo sin ciclos pares , un grafo sin ciclos pares.
• Grafo sin agujeros pares , un grafo sin ciclos inducidos de longitud par.

• Espacio para bicicletas
• Base cíclica
• Detección de ciclos en una secuencia de valores de función iterados
• ciclo de peso medio mínimo

• Balakrishnan, VK (2005). Esquema de Schaum sobre la teoría y los problemas de la teoría de grafos (ed. [Nachdr.]  ). McGraw-Hill. ISBN 978-0070054899.
• Bender, Edward A.; Williamson, S. Gill (2010). Listas, decisiones y gráficos. Con una introducción a la probabilidad .