Zyklus (Graphentheorie) - LinkFang.de





Zyklus (Graphentheorie)


Ein Zyklus ist in der Graphentheorie ein Weg in einem Graphen, bei dem Start- und Endknoten gleich sind. Ein zyklischer Graph ist ein Graph mit mindestens einem Zyklus. Algorithmen zum Auffinden von Zyklen in einem Graphen sind eine modifizierte topologische Sortierung oder eine modifizierte Tiefensuche.

Definitionen

Zyklus

Ist [math]G = (V, E)[/math] ein Graph, dann heißt ein Weg [math](v_1, \ldots, v_n)[/math] mit [math]v_i \in V[/math] für [math]i=1, \ldots , n[/math] Zyklus, wenn

[math]v_1 = v_n[/math]

gilt. In einem Zyklus müssen also Start- und Endknoten des Weges übereinstimmen. Ein Zyklus in einem gerichteten Graph heißt gerichteter Zyklus und in einem ungerichteten Graph ungerichteter Zyklus.

Kreis

Entsprechend dazu heißt ein Zyklus [math](v_1, \ldots, v_n)[/math] in einem Graphen Kreis, wenn [math](v_1, \ldots, v_{n-1})[/math] ein Pfad ist. Ein Kreis ist damit ein Zyklus, bei dem nur Start- und Endknoten gleich sind, es gilt also zusätzlich

[math]v_i \neq v_j[/math]

für [math]i, j \in \{ 1, \ldots , n-1 \}[/math] mit [math]i \neq j[/math]. 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 [math]n-1[/math] die Länge eines Zyklus oder Kreises [math](v_1, \ldots, v_n)[/math]. 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

Zyklischer Graph

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

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

Zyklenraum

Zu einer beliebig vorgegebenen Nummerierung der Knoten [math]A=\{a_1,a_2, \ldots, a_m\}[/math] heißt ein Element [math]x=(x_i) \in \mathbb{R}^m[/math] Inzidenzvektor zur Kantenmenge [math]M[/math], falls

[math]x_i= \begin{cases} 0& \mbox{, falls } a_i \notin M \and {a_i}^{-1} \notin M \\ 1& \mbox{, falls } a_i \in M\\ -1& \mbox{, falls } {a_i}^{-1} \in M\\ \end{cases} [/math]

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 [math]\mathbb{R}^m[/math]. 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 [math]\mathbb{R}^m[/math] 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.

Zykluserkennung mittels Tiefensuche

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


Kategorien: Grundbegriff (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Zyklus (Graphentheorie) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.