Zyklus (Graphentheorie)

Begriff aus der Graphentheorie

Ein Zyklus ist in der Graphentheorie ein Kantenzug mit unterschiedlichen Kanten in einem Graphen, bei dem Start- und Endknoten gleich sind. Ein zyklischer Graph ist ein Graph mit mindestens einem Zyklus. Algorithmisch lassen sich Zyklen in einem Graphen durch modifizierte Tiefensuche finden, etwa durch modifizierte topologische Sortierung.

Zyklischer Graph mit Kreis (b,c,d,e,b)

DefinitionenBearbeiten

ZyklusBearbeiten

Ein nicht-leerer Graph   mit der Knotenmenge   und der Kantenmenge   mit   heißt Zyklus, wenn   und die Kanten   mit   paarweise verschieden sind. Auch ein Graph mit einer Knotenmenge   (d. h. mit einem Knoten) und einer leeren Kantenmenge wird meistens als Zyklus (der Länge 0) bezeichnet.

Oft wird ein Zyklus der Einfachheit halber durch die Folge seiner (unterschiedlichen!) Knoten   angegeben. Jede zyklische Permutation dieser Folge stellt denselben Zyklus dar, z. B.  .

Ist   ein Graph, dann heißt ein geschlossener Kantenzug   mit   für   und   für   Zyklus, wenn

 

gilt, d. h. wenn der aus den   und   gebildete Subgraph ein Zyklus im obigen Sinne ist.

Ein Zyklus in einem gerichteten Graphen heißt gerichteter Zyklus und in einem ungerichteten Graphen ungerichteter Zyklus.

KreisBearbeiten

Entsprechend dazu heißt ein Zyklus   in einem Graphen Kreis, wenn   ein Weg ist. Einen Kreis erhält man also dadurch, dass die Endknoten   und   eines Weges durch eine zusätzliche Kante   verbunden werden.[1] Ein Kreis ist damit ein Zyklus, bei dem nur Start- und Endknoten gleich sind, es gilt also zusätzlich

 

für   mit  . Ein Kreis in einem gerichteten Graphen heißt gerichteter Kreis und in einem ungerichteten Graphen ungerichteter Kreis. Eine Kante, die zwei Knoten eines Kreises verbindet, selbst jedoch nicht Teil des Kreises ist, heißt Sehne des Kreises.

LängeBearbeiten

In Graphen ohne Kantengewichte ist   die Länge eines Zyklus oder Kreises  . Anschaulich zählt man also die Anzahl zugehöriger Kanten   . In einem kantengewichteten Graphen ist die Länge eines Zyklus oder Kreises die Summe der Kantengewichte aller zugehörigen Kanten.

Spezielle GraphenBearbeiten

Zyklischer GraphBearbeiten

Ein Graph mit mindestens einem Zyklus heißt zyklisch. Graphen ohne Zyklen werden azyklisch oder Wald genannt. Ein Zyklus oder Kreis heißt trivial, wenn er weniger als drei Knoten enthält. Triviale Kreise oder Zyklen werden bei der Analyse von Graphen meist nicht betrachtet. Ein Kreis, der genau drei Knoten enthält, wird Dreieck genannt. Einen Graphen ohne Dreieck nennt man dann dreiecksfrei. Als Taillenweite eines Graphen bezeichnet man die Länge eines kürzesten nicht trivialen Kreises. Falls der Graph keinen Kreis besitzt, so setzt man die Taillenweite auf unendlich. Die einfachsten zyklischen Graphen sind die Kreisgraphen.

Panzyklischer GraphBearbeiten

Ein Graph heißt kantenpanzyklisch, falls jede Kante auf einem Kreis der Länge   für alle   liegt. Ein Graph heißt knotenpanzyklisch, wenn jeder Knoten auf einem Kreis der Länge   für alle   liegt. Ein Graph heißt panzyklisch, wenn er für alle   einen Kreis der Länge   besitzt. Kantenpanzyklische Graphen sind damit auch knotenpanzyklisch und knotenpanzyklische Graphen auch panzyklisch. Panzyklische Graphen sind insbesondere hamiltonsch.

ZyklenraumBearbeiten

Zu einer beliebig vorgegebenen Nummerierung der Kanten   heißt ein Element   Inzidenzvektor zur Kantenmenge  , falls

 

gilt. Haben die Kanten zudem ein nichtnegatives Gewicht, werden die Einträge des Vektors mit diesem Gewicht multipliziert. Die Menge aller so beschriebenen Kreise bilden den Zyklenraum, einen Untervektorraum des  . Eine Basis des Zyklenraums sind die Fundamentalkreise. Jeder Fundamentalkreis entsteht durch Hinzufügen einer Kante zu einem aufspannenden Baum.

Der Kozyklenraum ist der Vektorraum aller durch Schnitte erzeugten Inzidenzvektoren. Er ist ebenfalls ein Untervektorraum des   und ergibt in direkter Summe mit dem Zyklenraum den ganzen Raum. Eine Basis des Kozyklenraums sind die Fundamentalschnitte. Jeder Fundamentalschnitt entsteht durch Weglassen einer Kante eines aufspannenden Baums als Zusammenhangskomponente.

AlgorithmusBearbeiten

Für jeden Knoten v: visited(v) = false, finished(v) = false
Für jeden Knoten v:
  DFS(v)
DFS(v):
  if finished(v)
    return
  if visited(v)
    "Zyklus gefunden" und Abbruch
  visited(v) = true
  für jeden Nachfolger w
    DFS(w)
  finished(v) = true

Nachfolger bedeutet sowohl für gerichtete als auch ungerichtete Graphen alle mit v verbundenen Knoten, bis auf den, der DFS(v) aufgerufen hat. Dies verhindert, dass der Algorithmus auch die trivialen Zyklen erfasst, was in jedem ungerichteten Graphen mit nichtleerer Kantenmenge stets der Fall ist.

ProgrammierungBearbeiten

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung eines ungerichteten Graphen mit Adjazenzlisten. Der ungerichtete Graph wird als Klasse UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode Main verwendet, die – falls vorhanden – die kürzesten nicht trivialen Zyklen des Graphen auf der Konsole ausgibt.[2]

using System;
using System.Collections.Generic;

// Deklariert die Klasse für die Knoten des Graphen
class Node
{
	public int index;
	public string value;
	public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Menge der Nachbarknoten
}

// Deklariert die Klasse für den ungerichteten Graphen
class UndirectedGraph
{
	public HashSet<Node> nodes = new HashSet<Node>();
	
	// Diese Methode verbindet die Knoten node1 und node2 miteinander.
	public void ConnectNodes(Node node1, Node node2)
	{
		node1.adjacentNodes.Add(node2);
		node2.adjacentNodes.Add(node1);
	}
}

class Program
{
	// Diese Methode gibt den Zyklus in der Form A, B, C, ... als Text zurück.
	public static string ToString(List<Node> cycle)
	{
		string text = "";
		for (int i = 0; i < cycle.Count; i++) // for-Schleife, die die Knoten durchläuft
		{
			text += cycle[i].value + ", ";
		}
		text = text.Substring(0, text.Length - 2);
		return text;
	}
	
	// Hauptmethode, die das Programm ausführt
	public static void Main(string[] args)
	{
		// Deklariert und initialisiert 5 Knoten
		Node node1 = new Node{index = 0, value = "A"};
		Node node2 = new Node{index = 1, value = "B"};
		Node node3 = new Node{index = 2, value = "C"};
		Node node4 = new Node{index = 3, value = "D"};
		// Deklariert und initialisiert ein Array mit den Knoten
		Node[] nodes = {node1, node2, node3, node4};
		// Erzeugt einen ungerichteten Graphen
		UndirectedGraph undirectedGraph = new UndirectedGraph();
		int numberOfNodes = nodes.Length;
		for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft
		{
			undirectedGraph.nodes.Add(nodes[i]); // Fügt die Knoten dem Graphen hinzu
		}
		// Verbindet Knoten des Graphen miteinander
		undirectedGraph.ConnectNodes(node1, node1);
		undirectedGraph.ConnectNodes(node1, node2);
		undirectedGraph.ConnectNodes(node2, node3);
		undirectedGraph.ConnectNodes(node3, node1);
		undirectedGraph.ConnectNodes(node3, node4);
		undirectedGraph.ConnectNodes(node4, node1);
		
		HashSet<Node> newNodes = new HashSet<Node>(nodes); // Menge der neu durchlaufenen Knoten
		HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Die Menge der aktuellen Pfade
		for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten des Graphen durchläuft
		{
			Node node = nodes[i];
			newNodes.Add(node); // Fügt den Knoten der Menge der neu durchlaufenen Knoten hinzu
			List<Node> path = new List<Node>();
			path.Add(node);
			paths.Add(path); // Fügt der Menge Pfade mit jedem Knoten als Anfangsknoten hinzu
		}
		HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Die Menge der kürzesten Zyklen
		int lengthOfCycles = 0; // Die Länge der kürzesten Zyklen
		bool cyclesAreFound = false; // Gibt an, ob Zyklen gefunden wurden
		while (!cyclesAreFound && newNodes.Count > 0) // So lange neue Knoten durchlaufen wurden
		{
			newNodes.Clear(); // Leert die Menge der neu durchlaufenen Knoten
			HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Die Menge der neu gefundenen Pfade
			foreach (List<Node> path in paths) // foreach-Schleife, die alle aktuellen Pfade durchläuft
			{
				Node lastNode = path[path.Count - 1];
				newNodes.Add(lastNode); // Fügt den letzten Knoten des Pfads der Menge der neu durchlaufenen Knoten hinzu
				foreach (Node nextNode in lastNode.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des letzten Knotens durchläuft
				{
					if (path.Count >= 3 && path[0] == nextNode) // Wenn ein Zyklus mit Länge größer gleich 3 gefunden wurde
					{
						cyclesAreFound = true;
						shortestCycles.Add(path); // Fügt den Pfad der Menge der Zyklen hinzu
						lengthOfCycles = path.Count;
					}
					if (!path.Contains(nextNode)) // Wenn der Pfad den benachbarten Knoten nicht enthält
					{
						newNodes.Add(nextNode); // Fügt den benachbarten Knoten der Menge der neu durchlaufenen Knoten hinzu
						// Erzeugt einen neuen Pfad
						List<Node> newPath = new List<Node>();
						newPath.AddRange(path); // Fügt die Knoten des aktuellen Pfads dem neuen Pfad in der richtigen Reihenfolge hinzu
						newPath.Add(nextNode); // Fügt den benachbarten Knoten dem neuen Pfad hinzu
						newPaths.Add(newPath); // Fügt den neuen Pfad der Menge der neu gefundenen Pfade hinzu
					}
				}
			}
			paths = newPaths; // Aktualisiert die Menge der aktuellen Pfade
		}
		if (shortestCycles.Count > 0) // Wenn Zyklen gefunden wurden
		{
			Console.WriteLine("Der Graph enthält " + shortestCycles.Count + " Zyklen der Länge " + lengthOfCycles + "."); // Ausgabe auf der Konsole
			foreach (List<Node> cycle in shortestCycles) // foreach-Schleife, die alle gefundenen Zyklen durchläuft
			{
				Console.WriteLine(ToString(cycle)); // Ausgabe auf der Konsole
			}
		}
		else
		{
			Console.WriteLine("Der Graph enthält keine Zyklen."); // Ausgabe auf der Konsole
		}
		
		Console.ReadLine();
	}
}

LiteraturBearbeiten

EinzelnachweiseBearbeiten

  1. Reinhard Diestel: Graphentheorie, 3., neu bearb. und erw. Auflage, Springer, Berlin, 2006, ISBN 3-540-21391-0, S. 7ff.
  2. GeeksforGeeks: Shortest cycle in an undirected unweighted graph