En teoría de grafos , un ciclo en un grafo es un camino no vacío en el que los únicos vértices repetidos son el primero y el último vértice. Un ciclo dirigido en un grafo dirigido es un camino dirigido no vacío en el que los únicos vértices repetidos son el primer y el último vértice.
Un gráfico sin ciclos se llama gráfico acíclico . Un gráfico dirigido sin ciclos dirigidos se denomina gráfico acíclico dirigido . Un gráfico conectado sin ciclos se llama árbol .
Definiciones
Circuito, ciclo
- Un circuito es un camino no vacío en el que el primer vértice es igual al último vértice ( camino cerrado ). [1]
- Sea G = ( V , E , ϕ ) una gráfica. 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 ) .
- Un ciclo o circuito simple es un circuito en el que el único vértice repetido es el primer / último vértice. [1]
- La longitud de un circuito o ciclo es el número de aristas involucradas.
Circuito dirigido, ciclo
- Un circuito dirigido es un camino dirigido no vacío en el que el primer vértice es igual al último vértice. [1]
- Sea G = ( V , E , ϕ ) una gráfica dirigida. 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 ) .
- Un ciclo dirigido o circuito dirigido simple es un circuito dirigido en el que el único vértice repetido es el primer / último vértice. [1]
Ciclos sin acordes
Un ciclo sin cuerda en un gráfico, también llamado agujero o ciclo inducido, es un ciclo tal que no hay dos vértices del ciclo conectados por un borde que no pertenece al ciclo. Un anti-agujero es el complemento de un agujero de gráfico. Los ciclos sin cuerda se pueden utilizar para caracterizar gráficas perfectas : según el teorema de la gráfica perfecta fuerte , una gráfica es perfecta si y solo si ninguno de sus agujeros o anti-agujeros tiene un número impar de vértices mayor que tres. Un gráfico de cuerdas , un tipo especial de gráfico perfecto, no tiene agujeros de ningún tamaño mayor a tres.
La circunferencia de un gráfico es la longitud de su ciclo más corto; este ciclo es necesariamente sin acordes. Las jaulas se definen como los gráficos regulares más pequeños con combinaciones dadas de grado y circunferencia.
Un ciclo periférico es un ciclo en un gráfico con la propiedad de que cada dos aristas que no están en el ciclo pueden estar conectadas por un camino cuyos vértices interiores evitan el ciclo. En un gráfico que no se forma agregando un borde a un ciclo, un ciclo periférico debe ser un ciclo inducido.
Espacio de ciclo
El término ciclo también puede referirse a un elemento del espacio cíclico de un gráfico. Hay muchos espacios de ciclo, uno para cada campo de coeficiente o anillo. El más común es el espacio de ciclo binario (generalmente llamado simplemente el espacio de ciclo ), que consiste en los conjuntos de bordes que tienen un grado uniforme en cada vértice; forma un espacio vectorial sobre el campo de dos elementos . Según el teorema de Veblen , cada elemento del espacio cíclico puede formarse como una unión de aristas disjuntos de ciclos simples. Una base de ciclo del gráfico es un conjunto de ciclos simples que forma una base del espacio de ciclo. [2]
Usando ideas de topología algebraica , el espacio de ciclo binario se generaliza a espacios vectoriales o módulos sobre otros anillos como los enteros, números racionales o reales, etc. [3]
Detección de ciclo
La existencia de un ciclo en gráficos dirigidos y no dirigidos se puede determinar si la búsqueda en profundidad (DFS) encuentra un borde que apunta a un antepasado del vértice actual (contiene un borde posterior ). [4] Todos los bordes posteriores que DFS omite son parte de los ciclos. [5] En un gráfico no dirigido, el borde del padre de un nodo no debe contarse como un borde posterior, pero encontrar cualquier otro vértice ya visitado indicará un borde posterior. En el caso de gráficos no dirigidos, solo se requiere O ( n ) tiempo para encontrar un ciclo en un gráfico de n -vértices, ya que como máximo n - 1 aristas pueden ser aristas de árbol.
Muchos algoritmos de clasificación topológica también detectarán ciclos, ya que estos son obstáculos para que exista el orden topológico. Además, si un gráfico 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 gráficos dirigidos, se pueden utilizar algoritmos basados en mensajes distribuidos. 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 distribuidos en un grupo de computadoras (o supercomputadora).
Las aplicaciones de la detección de ciclos incluyen el uso de gráficos de espera para detectar puntos muertos en sistemas concurrentes. [6]
Cubriendo gráficos por ciclos
En su artículo de 1736 sobre los siete puentes de Königsberg , ampliamente considerado 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 borde exactamente una vez, es necesario y suficiente que estar conectados excepto por los vértices aislados (es decir, todos los bordes están contenidos en un componente) y tener un grado par en cada vértice. La caracterización correspondiente para la existencia de un paseo cerrado que visita cada borde exactamente una vez en un gráfico dirigido es que el gráfico está fuertemente conectado y tiene el mismo número de bordes entrantes y salientes en cada vértice. En cualquier caso, la caminata resultante se conoce como ciclo de Euler o recorrido de Euler. Si un gráfico 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 borde exactamente una vez: este es el teorema de Veblen . [7] Cuando un gráfico conectado no cumple las condiciones del teorema de Euler, no obstante, se puede encontrar una caminata cerrada de longitud mínima que cubra cada borde al menos una vez en tiempo polinomial resolviendo el problema de inspección de ruta .
El problema de encontrar un solo ciclo simple que cubra cada vértice exactamente una vez, en lugar de cubrir los bordes, es mucho más complicado. Tal ciclo se conoce como ciclo hamiltoniano , y determinar si existe es NP-completo . [8] Se han publicado muchas investigaciones sobre clases de gráficos que se puede garantizar que contienen ciclos hamiltonianos; un ejemplo es el teorema de Ore de que un ciclo hamiltoniano siempre se puede encontrar en un gráfico 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 gráfico. [9]
La conjetura de la doble cobertura del ciclo establece que, para cada gráfico sin puente , existe un conjunto múltiple de ciclos simples que cubre cada borde del gráfico exactamente dos veces. Demostrar que esto es cierto (o encontrar un contraejemplo) sigue siendo un problema abierto. [10]
Clases de gráficos definidas por ciclos
Varias clases importantes de gráficos pueden definirse o caracterizarse por sus ciclos. Éstas incluyen:
- Gráfico bipartito , un gráfico sin ciclos impares (ciclos con un número impar de vértices).
- Gráfico de cactus , un gráfico en el que cada componente biconectado no trivial es un ciclo
- Gráfico de ciclo , un gráfico que consta de un solo ciclo.
- Gráfico cordal , un gráfico en el que cada ciclo inducido es un triángulo
- Gráfico acíclico dirigido , un gráfico dirigido sin ciclos
- Gráfico de línea perfecta , un gráfico en el que cada ciclo impar es un triángulo
- Gráfico perfecto , un gráfico sin ciclos inducidos o sus complementos de longitud impar superior a tres
- Pseudoforest , un gráfico en el que cada componente conectado tiene como máximo un ciclo
- Gráfico estrangulado , un gráfico en el que cada ciclo periférico es un triángulo
- Gráfico fuertemente conectado , un gráfico dirigido en el que cada borde es parte de un ciclo
- Gráfico sin triángulos , un gráfico sin ciclos de tres vértices
Ver también
- Espacio de ciclo
- Base de ciclo
- Detección de ciclo en una secuencia de valores de función iterados
Referencias
- ↑ a b c d Bender y Williamson , 2010 , p. 164.
- ^ Bruto, Jonathan L .; Yellen, Jay (2005), "4.6 Gráficos y espacios vectoriales" , Teoría de gráficos y sus aplicaciones (2ª ed.), CRC Press, págs. 197–207, ISBN 9781584885054.
- ^ Diestel, Reinhard (2012), "1.9 Un poco de álgebra lineal" , Teoría de grafos , Textos de posgrado en matemáticas, 173 , Springer, págs. 23-28.
- ^ Tucker, Alan (2006). "Capítulo 2: Circuitos de cobertura y coloraciones de gráficos". Combinatoria aplicada (5ª ed.). Hoboken: John Wiley e hijos. pag. 49. ISBN 978-0-471-73507-6.
- ^ a b Sedgewick, Robert (1983), "algoritmos de gráficos", algoritmos , Addison-Wesley, ISBN 0-201-06672-6
- ^ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Conceptos del sistema operativo . John Wiley & Sons, INC. Págs. 260 . ISBN 0-471-25060-0.
- ^ Veblen, Oswald (1912), "An Application of Modular Equations in Analysis Situs", Annals of Mathematics , Segunda serie, 14 (1): 86–94, doi : 10.2307 / 1967604 , JSTOR 1967604.
- ^ Richard M. Karp (1972), "Reducibilidad entre problemas combinatorios" (PDF) , en RE Miller y JW Thatcher (ed.), Complexity of Computer Computations , Nueva York: Plenum, págs. 85-103.
- ^ Mineral, Ø. (1960), "Nota sobre los circuitos de Hamilton", American Mathematical Monthly , 67 (1): 55, doi : 10.2307 / 2308928 , JSTOR 2308928.
- ^ Jaeger, F. (1985), "Un estudio de la doble ciclo conjetura cubierta", Annals of Discrete Mathematics 27 - ciclos en los gráficos , North-Holland Matemáticas Estudios, 27 , pp 1-12,. Doi : 10.1016 / S0304-0208 (08) 72993-1..
- Balakrishnan, VK (2005). Esquema de la teoría y problemas de la teoría de grafos de Schaum ([Nachdr.] Ed.). McGraw – Hill. ISBN 978-0070054899.
- Bender, Edward A .; Williamson, S. Gill (2010). Listas, Decisiones y Gráficos. Con una introducción a la probabilidad .