stringtranslate.com

Ciclo (teoría de grafos)

Un gráfico con aristas coloreadas para ilustrar un paseo cerrado , H–A–B–A–H, en verde; un circuito que es un paseo cerrado en el que todas las aristas son distintas, B–D–E–F–D–C–B, en azul; y un ciclo que es un paseo cerrado en el que todos los vértices son distintos, H–D–G–H, en rojo.

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 .

Definiciones

Circuito y ciclo

Sea G = ( V , E , Φ ) un grafo. Un circuito es un camino no vacío ( e 1 , e 2 , ..., e n ) con una secuencia de vértices ( v 1 , v 2 , ..., v n , v 1 ) .

Circuito dirigido y ciclo dirigido

Sea G = ( V , E , Φ ) un grafo dirigido. Un circuito dirigido es un camino dirigido no vacío ( e 1 , e 2 , ..., e n ) con una secuencia de vértices ( v 1 , v 2 , ..., v n , v 1 ) .

Ciclo sin cuerdas

En este gráfico, el ciclo verde A–B–C–D–E–F–A no tiene cuerda, mientras que el ciclo rojo G–H–I–J–K–L–G sí. Esto se debe a que la arista {K, I} es una cuerda.

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.

Espacio para bicicletas

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]

Detección de ciclos

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]

Algoritmo

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 vwv ; 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.

Cobertura de gráficos por ciclo

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é conexo 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 conexo 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á conexo, 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]

Clases de gráficos definidas por ciclo

Varias clases importantes de grafos pueden definirse o caracterizarse por sus ciclos. Entre ellas se incluyen:

Véase también

Referencias

  1. ^ abcd Bender y Williamson 2010, pág. 164.
  2. ^ Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Gráficos y espacios vectoriales", Teoría de grafos y sus aplicaciones (2.ª ed.), CRC Press, págs. 197-207, ISBN 9781584885054, archivado desde el original el 4 de febrero de 2023 , consultado el 27 de septiembre de 2016.
  3. Diestel, Reinhard (2012), "1.9 Algo de álgebra lineal", Graph Theory , Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28, archivado desde el original el 2023-02-04 , consultado el 2016-09-27.
  4. ^ Tucker, Alan (2006). "Capítulo 2: Recubrimiento de circuitos y coloraciones de grafos". Combinatoria aplicada (5.ª ed.). Hoboken: John Wiley & sons. pág. 49. ISBN 978-0-471-73507-6.
  5. ^ ab Sedgewick, Robert (1983), "Algoritmos de grafos", Algoritmos , Addison–Wesley, ISBN 0-201-06672-6
  6. ^ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Conceptos de sistemas operativos . John Wiley & Sons, INC., págs. 260. ISBN 0-471-25060-0.
  7. ^ Veblen, Oswald (1912), "Una aplicación de ecuaciones modulares en el análisis in situ", Anales de matemáticas , Segunda serie, 14 (1): 86–94, doi :10.2307/1967604, JSTOR  1967604.
  8. ^ Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF) , en RE Miller y JW Thatcher (ed.), Complexity of Computer Computations , Nueva York: Plenum, págs. 85-103, archivado (PDF) desde el original el 2021-02-10 , consultado el 2014-03-12.
  9. ^ Ore, Ø. (1960), "Nota sobre circuitos de Hamilton", American Mathematical Monthly , 67 (1): 55, doi :10.2307/2308928, JSTOR  2308928.
  10. ^ Jaeger, F. (1985), "Un estudio de la conjetura de doble cobertura del ciclo", Annals of Discrete Mathematics 27 – Ciclos en gráficos , North-Holland Mathematics Studies, vol. 27, págs. 1–12, doi :10.1016/S0304-0208(08)72993-1.