Zyklus (Graphentheorie)

Ein Zyklus i​st in d​er Graphentheorie e​in Kantenzug m​it unterschiedlichen Kanten i​n einem Graphen, b​ei dem Start- u​nd Endknoten gleich sind. Ein zyklischer Graph i​st ein Graph m​it mindestens e​inem Zyklus. Algorithmisch lassen s​ich Zyklen i​n einem Graphen d​urch modifizierte Tiefensuche finden.

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

Definitionen

Zyklus

Ein nicht-leerer Graph ${\displaystyle G=(V,E)}$ mit der Knotenmenge ${\displaystyle V=\{x_{1},x_{2},\dotsc ,x_{n}\}}$ und der Kantenmenge ${\displaystyle E=\{\{x_{1},x_{2}\},\{x_{2},x_{3}\},\dotsc ,\{x_{n-1},x_{n}\}\}}$ mit ${\displaystyle 2\leq n}$ heißt Zyklus, wenn ${\displaystyle x_{1}=x_{n}}$ und die Kanten ${\displaystyle \{x_{i-1},x_{i}\}}$ mit ${\displaystyle 2\leq i\leq n}$ paarweise verschieden sind. Auch ein Graph mit einer Knotenmenge ${\displaystyle \{x_{1}\}}$ (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 ${\displaystyle (x_{1},x_{2},\dotsc ,x_{n-1})}$ angegeben. Jede zyklische Permutation dieser Folge stellt denselben Zyklus dar, z. B. ${\displaystyle (x_{2},x_{3},\dotsc ,x_{n-1},x_{1})}$.

Ist ${\displaystyle G=(V,E)}$ ein Graph, dann heißt ein geschlossener Kantenzug ${\displaystyle v_{1},e_{1},v_{2},e_{2},\dotsc ,e_{n-1},v_{n}}$ mit ${\displaystyle v_{i}\in V}$ für ${\displaystyle i=1,\ldots ,n}$ und ${\displaystyle e_{i}\in E}$ für ${\displaystyle i=1,\ldots ,n-1}$ Zyklus, wenn

${\displaystyle v_{1}=v_{n}}$

gilt, d. h. wenn der aus den ${\displaystyle v_{i}}$ und ${\displaystyle e_{i}}$ gebildete Subgraph ein Zyklus im obigen Sinne ist.

Ein Zyklus i​n einem gerichteten Graphen heißt gerichteter Zyklus u​nd in e​inem ungerichteten Graphen ungerichteter Zyklus.

Kreis

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

${\displaystyle v_{i}\neq v_{j}}$

für ${\displaystyle i,j\in \{1,\ldots ,n-1\}}$ mit ${\displaystyle i\neq j}$. 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

In Graphen ohne Kantengewichte ist ${\displaystyle n-1}$ die Länge eines Zyklus oder Kreises ${\displaystyle (v_{1},\ldots ,v_{n-1})}$. Anschaulich zählt man also die Anzahl zugehöriger Kanten ${\displaystyle e_{1}=\{v_{1},v_{2}\},e_{2}=\{v_{2},v_{3}\},\dotsc ,e_{n-1}=\{v_{n-1},v_{0}\}}$ . In einem kantengewichteten Graphen ist die Länge eines Zyklus oder Kreises die Summe der Kantengewichte aller zugehörigen Kanten.

Spezielle Graphen

Zyklischer Graph

Ein Graph m​it mindestens e​inem Zyklus heißt zyklisch. Graphen o​hne Zyklen werden azyklisch o​der Wald genannt. Ein Zyklus o​der Kreis heißt trivial, w​enn er weniger a​ls drei Knoten enthält. Triviale Kreise o​der Zyklen werden b​ei der Analyse v​on Graphen m​eist nicht betrachtet. Ein Kreis, d​er genau d​rei Knoten enthält, w​ird Dreieck genannt. Einen Graphen o​hne Dreieck n​ennt man d​ann dreiecksfrei. Als Taillenweite e​ines Graphen bezeichnet m​an die Länge e​ines kürzesten n​icht trivialen Kreises. Falls d​er Graph keinen Kreis besitzt, s​o setzt m​an die Taillenweite a​uf unendlich. Die einfachsten zyklischen Graphen s​ind die Kreisgraphen.

Panzyklischer Graph

Ein Graph heißt kantenpanzyklisch, falls jede Kante auf einem Kreis der Länge ${\displaystyle p}$ für alle ${\displaystyle p\in \{1,2,\ldots ,|V(G)|\}}$ liegt. Ein Graph heißt knotenpanzyklisch, wenn jeder Knoten auf einem Kreis der Länge ${\displaystyle p}$ für alle ${\displaystyle p\in \{1,2,\ldots ,|V(G)|\}}$ liegt. Ein Graph heißt panzyklisch, wenn er für alle ${\displaystyle p\in \{3,4,\ldots ,|V(G)|\}}$ einen Kreis der Länge ${\displaystyle p}$ besitzt. Kantenpanzyklische Graphen sind damit auch knotenpanzyklisch und knotenpanzyklische Graphen auch panzyklisch. Panzyklische Graphen sind insbesondere hamiltonsch.

Zyklenraum

Zu einer beliebig vorgegebenen Nummerierung der Kanten ${\displaystyle A=\{a_{1},a_{2},\ldots ,a_{m}\}}$ heißt ein Element ${\displaystyle x=(x_{i})\in \mathbb {R} ^{m}}$ Inzidenzvektor zur Kantenmenge ${\displaystyle M}$, falls

${\displaystyle x_{i}={\begin{cases}0&{\mbox{, falls }}a_{i}\notin M\land {a_{i}}^{-1}\notin M\\1&{\mbox{, falls }}a_{i}\in M\\-1&{\mbox{, falls }}{a_{i}}^{-1}\in M\\\end{cases}}}$

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 ${\displaystyle \mathbb {F} _{2}^{m}}$. 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 ${\displaystyle \mathbb {F} _{2}^{m}}$ 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

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 a​ls auch ungerichtete Graphen a​lle mit v verbundenen Knoten, b​is auf den, d​er DFS(v) aufgerufen hat. Dies verhindert, d​ass der Algorithmus a​uch die trivialen Zyklen erfasst, w​as in j​edem ungerichteten Graphen m​it nichtleerer Kantenmenge s​tets der Fall ist.

Literatur

• R. Diestel: Graphentheorie. 3. Auflage. Springer, Heidelberg 2005. ISBN 3-540-67656-2

Einzelnachweise

1. Reinhard Diestel: Graphentheorie, 3., neu bearb. und erw. Auflage, Springer, Berlin, 2006, ISBN 3-540-21391-0, S. 7ff.