Ciclo (teoría de grafos)

En la teoría de grafos, un ciclo en un gráfico es un camino no vacío en el que solo el primer y el último vértice son iguales. Un ciclo dirigido en un gráfico dirigido es un camino dirigido no vacío en el que solo el primer y el último vértice son iguales.

Un gráfico sin ciclos se llama gráfico acíclico. Un gráfico dirigido sin ciclos dirigidos se llama gráfico acíclico dirigido. Un grafo conexo sin ciclos se llama árbol.

Definiciones

Circuito y ciclo

• Un circuito es un camino no vacío en el que el primer y el último vértice son iguales (camino cerrado).

Sea G = (V, E, ϕ) una gráfica. Un circuito es un camino no vacío (e ₁, e ₂, …, e _n) con una secuencia de vértices (v ₁, v ₂, …, v _n, v ₁).

• Un ciclo o circuito simple es un circuito en el que solo el primer y el último vértice son iguales.

Circuito dirigido y ciclo dirigido

• Un circuito dirigido es un camino dirigido no vacío en el que el primer y el último vértices son iguales (camino dirigido cerrado).

Sea G = (V, E, ϕ) un grafo dirigido. Un circuito dirigido es un camino dirigido no vacío (e ₁, e ₂, …, e _n) con una secuencia de vértices (v ₁, v ₂, …, v _n, v ₁).

• Un ciclo dirigido o circuito dirigido simple es un circuito dirigido en el que solo el primer y el último vértice son iguales.

Ciclo sin cuerdas

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 pertenezca al ciclo. Un antiagujero es el complemento de un agujero gráfico. Los ciclos sin cuerda se pueden usar para caracterizar gráficos perfectos: según el teorema del gráfico perfecto fuerte, un gráfico 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 huecos de tamaño superior a tres.

La circunferencia de un gráfico es la longitud de su ciclo más corto; este ciclo es necesariamente sin cuerdas. 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 para bicicletas

El término ciclo también puede referirse a un elemento del espacio de ciclo 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 espacio de ciclo), que consiste en los conjuntos de bordes que tienen un grado par en cada vértice; forma un espacio vectorial sobre el campo de dos elementos. Por el teorema de Veblen, cada elemento del espacio del ciclo puede formarse como una unión disjunta de bordes de ciclos simples. Una base de ciclo del gráfico es un conjunto de ciclos simples que forma una base del espacio de ciclo.

Utilizando ideas de la topología algebraica, el espacio del ciclo binario se generaliza a espacios vectoriales o módulos sobre otros anillos como los números enteros, racionales o reales, etc.

Detección de ciclo

La existencia de un ciclo en gráficos dirigidos y no dirigidos se puede determinar si la búsqueda primero en profundidad (DFS) encuentra un borde que apunta a un antepasado del vértice actual (contiene un borde posterior). Todos los bordes posteriores que DFS salta son parte de ciclos. En un gráfico no dirigido, el borde al 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 esos 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.

Para gráficos dirigidos, se pueden usar 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 clúster de computadoras (o supercomputadora).

Las aplicaciones de la detección de ciclos incluyen el uso de gráficos de espera para detectar interbloqueos en sistemas concurrentes.

Algoritmo

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

DFS(v):
  si termino (v)
    devolver
  si es visitado(v)
    "Ciclo encontrado" y volver
  visitado (v) = verdadero
  para cada vecino w
    DFS(w)
  terminado (v) = verdadero

Vecino significa para gráficos dirigidos y no dirigidos todos los vértices conectados a v, excepto el que se llama DFS(v). Esto evita que el algoritmo también atrape ciclos triviales, que es el caso en cada gráfico no dirigido con al menos un borde.

Programación

El siguiente ejemplo en el lenguaje de programación C# muestra una implementación de un gráfico no dirigido usando listas de adyacencia. El gráfico no dirigido se declara como clase UndirectedGraph. La ejecución del programa utiliza el método Main, que, si existe, imprime el ciclo más corto y no trivial en la consola.

utilizando  el sistema ; 
usando  System.Collections.Generic ;

// Declara la clase para los vértices del grafo 
class  Node 
{ 
	public  int  index; 
	valor de cadena pública ; public HashSet < Nodo > adyacenteNodes = new HashSet < Nodo >(); // Conjunto de vértices vecinos } 
	      


// Declara la clase para el gráfico no dirigido 
class  UndirectedGraph 
{ 
	public  HashSet < Node >  nodes  =  new  HashSet < Node >();
	
	// Este método conecta el nodo1 y el nodo2 entre sí 
	public  void  ConnectNodes (Nodo  nodo1,  Nodo  nodo2) 
	{ 
		nodo1. nodosadyacentes. Añadir (nodo2); 
		nodo2. nodosadyacentes. Añadir (nodo1); 
	} 
}

class  Program 
{ 
	// Este método devuelve el ciclo en la forma A, B, C,... como texto. 
	public  static  string  ToString (Lista < Nodo >  ciclo) 
	{ 
		texto de cadena  = ""; for (int i = 0; i < ciclo. Cuenta; i ++) // bucle for, iterando los vértices { texto += ciclo [ i ]. valor + ", ";  
		         
		
			    
		} 
		texto  =  texto. Subcadena (0,  texto. Longitud  -  2); 
		devolver  texto; 
	}
	
	// Método principal ejecutando el programa 
	public  static  void  Main (string []  args) 
	{ 
		// Declara e inicializa 5 vértices 
		Node  node1  =  new  Node { index  =  0,  value  =  "A" }; 
		Nodo  nodo2  =  nuevo  Nodo { índice  =  1,  valor  =  "B" }; 
		Nodo  nodo3  =  nuevo  Nodo { índice  =  2, valor  =  "C" }; 
		Nodo  nodo4  =  nuevo  Nodo { índice  =  3,  valor  =  "D" }; 
		// Declara e inicializa una matriz que contiene los vértices 
		Node []  nodes  =  { node1,  node2,  node3, node4 }; // Crea un grafo no dirigido UndirectedGraph undirectedGraph = new UndirectedGraph (); int numeroDeNodos = nodos. Longitud; 
		
		    
		   
		for  (int  i  =  0;  i  <  numberOfNodes;  i ++)  // for-loop, iterando todos los vértices 
		{ 
			undirectedGraph. nodos _ Agregar (nodos [ i ]);  // Agrega los vértices al gráfico 
		} 
		// Conecta los vértices del gráfico entre sí 
		undirectedGraph. ConnectNodes (nodo1,  nodo1); 
		Gráfico no dirigido. ConnectNodes (nodo1,  nodo2);
		Gráfico no dirigido. ConnectNodes (nodo2,  nodo3); 
		Gráfico no dirigido. ConnectNodes (nodo3,  nodo1); 
		Gráfico no dirigido. ConnectNodes (nodo3,  nodo4); 
		Gráfico no dirigido. ConnectNodes (nodo4,  nodo1);
		
		HashSet < Nodo >  newNodes  =  new  HashSet < Nodo >(nodos);  // Conjunto de nuevos vértices para iterar 
		HashSet < List < Node >>  paths  =  new  HashSet < List < Node >>();  // Conjunto de rutas actuales 
		para  (int  i  =  0;  i  <  numberOfNodes;  i ++)  // for-loop, iterando todos los vértices del gráfico 
		{ 
			Node  node =  nodos [ i ]; 
			nuevosNodos. Añadir (nodo);  // Agregar el vértice al conjunto de nuevos vértices para iterar 
			List < Node >  path  =  new  List < Node >(); 
			camino _ Añadir (nodo); 
			caminos _ Añadir (ruta);  // Agrega una ruta para cada nodo como un vértice inicial 
		} 
		HashSet < List < Node >>  shortestCycles  =  new  HashSet< Lista < Nodo >>();  // Conjunto de ciclos más cortos 
		int  lengthOfCycles  =  0;  // Longitud de los ciclos más cortos 
		bool  CyclesAreFound  =  false ;  // Si se encontraron ciclos o no 
		while  (! CyclesAreFound  &&  newNodes. Count  >  0)  // Siempre que todavía tuviéramos vértices para iterar 
		{ 
			newNodes. Borrar ();  // Vacía el conjunto de nodos para iterar 
			HashSet < Lista < Nodo >> newPaths  =  new  HashSet < Lista < Nodo >>();  // Conjunto de rutas recién encontradas 
			foreach  (Lista < Nodo >  ruta  en  rutas)  // bucle foreach, iterando todas las rutas actuales 
			{ 
				Node  lastNode  =  ruta [ ruta. Cuenta  -  1 ]; 
				nuevosNodos. Añadir (últimoNodo);  // Agrega el vértice final de la ruta a la lista de vértices para iterar 
				foreach  (Node  nextNode en  último nodo. nodosadyacentes)  // foreach-loop, iterando todos los vecinos del nodo anterior 
				{ 
					if  (ruta. Cuenta  >=  3  &&  ruta [ 0 ]  ==  siguienteNodo)  // Si se encuentra un ciclo con una longitud mayor o igual a 3 
					{ 
						ciclosAreFound  =  true ; 
						ciclos más cortos. Añadir (ruta);  // Agrega la ruta al conjunto de ciclos 
						lengthOfCycles  =  ruta. contar; 
					} 
					si (! ruta. Contiene (nextNode))  // Si la ruta no contiene el vecino 
					{ 
						newNodes. Añadir (siguienteNodo);  // Agrega el vecino al conjunto de vértices para iterar 
						// Crea una nueva ruta 
						List < Node >  newPath  =  new  List < Node >(); 
						nuevaRuta. AddRange (ruta);  // Agrega el vértice de la ruta actual a la nueva ruta en el orden correcto 
						newPath. Añadir (siguienteNodo); // Agrega el vecino a la nueva ruta 
						newPaths. Agregar (nuevaRuta);  // Agrega la ruta al conjunto de rutas recién encontradas 
					} 
				} 
			} 
			paths  =  newPaths;  // Actualiza el conjunto de rutas actuales 
		} 
		if  (shortestCycles. Count  >  0)  // Si se encontraron ciclos 
		{ 
			Console. WriteLine ("El gráfico contiene "  +  shortestCycles. Count  +  " ciclos de longitud "  +  lengthOfCycles  +  ".");  // Imprimir en la consola 
			foreach  (Lista < Nodo >  ciclo  en  shortestCycles)  // foreach-loop, iterando todos los ciclos encontrados 
			{ 
				Console. WriteLine (ToString (ciclo));  // Imprimir en la consola 
			} 
		} 
		else 
		{ 
			Console. WriteLine ("El gráfico no contiene ciclos.");  // Imprimir a la consola 
		}
		
		consola _ Línea de lectura (); 
	} 
}

Gráficos de cobertura 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 no dirigido finito tenga un camino cerrado que visite cada borde exactamente una vez (lo que lo convierte en un camino cerrado), es necesario y suficiente que esté conectado excepto por los vértices aislados (es decir, todos los bordes están contenidos en un componente) y que tenga un grado par en cada vértice. La caracterización correspondiente a la existencia de un recorrido cerrado que visita 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 no dirigido finito tiene grado par en cada uno de sus vértices, sin importar si es conexo,Cuando un grafo conexo no cumple las condiciones del teorema de Euler, se puede encontrar en tiempo polinomial un paseo cerrado de longitud mínima que cubra cada borde al menos una vez 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 difícil. Tal ciclo se conoce como ciclo hamiltoniano y determinar si existe es NP-completo. Se ha publicado mucha investigación sobre clases de gráficos que se puede garantizar que contienen ciclos hamiltonianos; un ejemplo es el teorema de Ore de que siempre se puede encontrar un ciclo hamiltoniano 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.

La conjetura de la doble cubierta 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.

Clases de grafos definidas por ciclo

Varias clases importantes de gráficos pueden definirse o caracterizarse por sus ciclos. Éstos 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 dirigidos
• 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 mayor que tres
• Pseudobosque, 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