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.
Definitionen Bearbeiten
Zyklus Bearbeiten
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.
Kreis Bearbeiten
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. 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änge Bearbeiten
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 Graphen Bearbeiten
Zyklischer Graph Bearbeiten
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 Graph Bearbeiten
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.
Zyklenraum Bearbeiten
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.
Algorithmus Bearbeiten
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.
Literatur Bearbeiten
- R. Diestel: Graphentheorie. 3. Auflage. Springer, Heidelberg 2005. ISBN 3-540-67656-2
Einzelnachweise Bearbeiten
- Reinhard Diestel: Graphentheorie. 3., neu bearb. und erw Auflage. Springer, Berlin, 2006, ISBN 3-540-21391-0, S. 7 ff. (diestel-graph-theory.com).