Diskussion:Zyklus (Graphentheorie)

Fragen zum Algorithmus "Zykluserkennung mittels Tiefensuche"

In der derzeitig genannten Version des Algorithmus Zykluserkennung mittels Tiefensuche findet sich in Schritt 4 die Anweisung:

für jeden Nachfolger w -> DFS(w)

Für einen gerichteten Graphen kann ich nachvollziehen, was man unter den Nachfolgern eines Knotens versteht. Was aber ist ein Nachfolger eines Knotens in einem ungerichteten Graph? --Abdull 23:00, 3. Aug. 2010 (CEST)

Simple Antwort, denn die Frage wird bei jeder Implementation sofort relevant: Alle Nachbarn, d.h. mit v verbundenen Knoten (abgehende Kanten im gerichteten Fall), bis auf dem der DFS(v) aufgerufen hat. Im gerichteten Fall sind Nachbarn und Nachfolger nur dann die selbe Menge, wenn es keine Hin-Rück Kanten gibt und dort braucht man dann auch keine unterscheidung zu machen. Habe es auch im Artikel hinzugefügt und begründet. Insbesondere, dass der Algorithmus stets anschlagen würde, wenn im ungerichteten Fall mindestens eine Kante vorhanden ist. (nicht signierter Beitrag von 79.242.154.239 (Diskussion) 17:55, 24. Sep. 2014 (CEST))

vollständig lautet der Algorithmus also

Für jeden Knoten v: visited(v) = false, finished(v) = false
Für jeden Knoten v:
  DFS(v,v)
  "kein Zyklus gefunden" und Ende

DFS(v,f):
  if finished(v)
    return
  if visited(v)
    x <- v
    "Zyklus gefunden" und Ende
  visited(v) = true
  für jeden Nachbarn w von v
    if w ungleich f
      DFS(w,v)
  finished(v) = true

Am Ende des Algorithmus stellen alle Knoten die als visited und nicht finished markiert sind eine Obermenge eines Zyklus dar. Den Zyklus selbst erhält man indem man den Knoten der zum positiven Abbruch führte (x) merkt und dann folgendes ausführt

Für jeden Knoten v:
  DFS_C(v,v)

DFS_C(v,f):
  if v = x Abbruch
  finished(v) = true
  für jeden Nachbarn w von v
    if w ungleich f
      DFS_C(w,v)

Jetzt ist die Menge aller Knoten die als visited und nicht finished markiert sind genau dem eines Zyklus (Nachweis über entsprechende Implementation) (nicht signierter Beitrag von Cdr McLovin (Diskussion | Beiträge) 23:28, 25. Sep. 2014 (CEST))

Frage zur Definition "Kreis"

Auf der Seite Weg (Graphentheorie) wird ein Pfad als ein Weg definiert, bei dem alle Knoten paarweise verschieden sind. Die Definition "Kreis" setzt voraus, dass $v_{1}=v_{n}$ gelten soll. Diese Bedingung kann ein Pfad aber aus den oben genannten Gründen nie erfüllen. --Sboerm (Diskussion) 17:54, 6. Jun. 2013 (CEST)

Habe die Definition korrigiert, danke für den Hinweis. Grüße, --Quartl (Diskussion) 21:18, 6. Jun. 2013 (CEST)

Wie soll diese einleitende Unterscheidung funktionieren, wenn, wie ich meine, ein "Weg" und ein "Pfad" in einem Graphen das gleiche sind? - "Ein Zyklus ist in der Graphentheorie ein Weg in einem Graphen, bei dem Start- und Endknoten gleich sind. Analog dazu ist ein Kreis ein Pfad in einem Graphen, bei dem Start- und Endknoten übereinstimmen." -- Theoprakt (Diskussion) 16:43, 30. Sep. 2013 (CEST)

(Die Pfade des Graphen sind unergründlich.) Darüber bin ich soeben auch gestolpert. Im ersten Satz verweist „Weg“ auf „Weg (Graphentheorie)“; im zweiten Satz verweist „Pfad“ zwar auf „Pfad (Graphentheorie)“, aber das leitet wiederum auf „Weg (Graphenthorie)“ weiter. Dort wird der Begriff „Pfad“ eher nebenbei erwähnt. Wenn ich den dortigen Absatz richtig interpretiere, gibt es durchaus in mancher Literatur unterschiedliche Definitionen für Pfad und Weg. In der engl. Literatur unterscheidet man wohl auch zwischen „simple path“ (Knoten paarweise verschieden) und „path“, oder zwischen „path“ und „walk“, wenn „path“ bereits einen „simple path“ impliziert. Verwirrend … :-) Möge jemand, der sich mit der Graphentheorie gut auskennt, die Verwirrung bitte aufheben. -- WoBra 178.203.5.28 22:32, 23. Okt. 2013 (CEST)

Konkretisierung/Korrekturen der Definitionen

Gem. Diestel ist ein Kreis (engl. "circle") ein um eine Kante erweiterter Weg (engl. "path"), die die beiden Enden des Weges verbindet. Laut Definition enthält ein Weg keine Knoten mehrfach, ein Kreis kann somit kein Weg sein (siehe auch Anmerkung von Sboerm).

Ein Zyklus (engl. "circuit") ist ein Kantenzug (engl. "walk"), der keine Kanten mehrfach enthält (engl. "trail"), und dessen Enknoten identisch mit seinem Startknoten ist. Somit ist ein Kreis immer ein Zyklus, aber ein Zyklus muss kein Kreis sein (er kann Knoten mehrfach enthalten). Ein Zyklus ist aber keinesfalls ein Weg!

Der Artikel sollte dementsprechend konkretisiert/korrigiert werden. --DerVanda (Diskussion) 19:49, 18. Apr. 2021 (CEST)

Eng damit zusammenhängend ist eine in sich widersprüchliche Definition des Zyklus im Artikel Graph (Graphentheorie). Siehe dort die Diskussion im Abschnitt "Teilgraphen, Wege und Zyklen". --Sigma^2 (Diskussion) 21:01, 19. Aug. 2021 (CEST)