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)

Fehlt eine Kante in der Definition?

Eine Kleinigkeit, in der Definition steht: Der Graph mit "Knotenmenge $V=\{x_{1},x_{2},\dotsc ,x_{n}\}$ […] Kantenmenge $E=\{\{x_{1},x_{2}\},\{x_{2},x_{3}\},\dotsc ,\{x_{n-1},x_{n}\}\}$" […] "heißt Zyklus, wenn $x_{1}=x_{n}$". Ich glaube, da stimmt mit dem n etwas nicht. Wenn n die Anzahl der (verschiedenen) Knoten ist, kann nicht gelten $x_{1}=x_{n}$, denn dann gäbe es nur n-1 verschiedene Knoten. M.E. fehlt in E eine Kante, $\{x_{n},x_{1}\}$ bzw. $\{x_{n},x_{n+1}\}$ mit $x_{1}=x_{n+1}$. --man (Diskussion) 11:40, 3. Sep. 2024 (CEST)

Ergänzung: Die Mengenklammer bei der Definition von V hat mich zu der Annahme geführt, dass die $x_{i}$ alle verschieden sein sollen, was ja nicht sein muss. Wenn aber die $x_{i}$ in V nicht paarweise verschieden sind, wird es nicht besser. Dann hängt die Definition von der Schreibweise der Mengen ab:

1. Beispiel mit n=6: $x_{1}=a,x_{2}=x_{4}=b,x_{3}=x_{5}=c,x_{6}=a$, also $V=\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\}=\{a,b,c,b,c,a\}$, $E=\{\{a,b\},\{b,c\},\{c,b\},\{b,c\},\{c,a\}\}$. Ist das nun ein Zyklus? Es gilt auch hier $x_{n}=x_{1}$. aber die Kanten $\{x_{i},x_{j}\}$ sind nicht paarweise verschieden, wie hier in der Definition gefordert wird. Wählt man aber einfach eine andere Schreibweise desselben Graphen, nämlich um einige mehrfache Elemente bereinigte Mengenaufzählungen, erhält man plötzlich einen Zyklus, nämlich den $K_{3}$: $V=\{x_{1},x_{2},x_{3},x_{4}\}=\{a,b,c,a\}$, $E=\{\{a,b\},\{b,c\},\{c,a\}\}$
2. Beispiel mit n=4: $x_{i}=a$, also $V=\{x_{1},x_{2},x_{3},x_{4}\}=\{a,a,a,a\}$, $E=\{\{a,a\},\{a,a\},\{a,a\}\}$. Ist das nun ein Zyklus? Es gilt zwar $x_{n}=x_{1}$. Die Kanten $\{x_{i},x_{j}\}$ sind aber nicht paarweise verschieden.

Besser wäre doch, die Knotenmenge nur mit paarweise verschiedenen Knoten zu definieren, $V=\{x_{1},x_{2},\dotsc ,x_{n-1}\},x_{i}\neq x_{j},1\leq i,j\leq n-1$, und einfach zu schreiben „… mit der Kantenmenge $E=\{\{x_{1},x_{2}\},\{x_{2},x_{3}\},\dotsc ,\{x_{n-1},x_{1}\}\}$ mit $2\leq n$ heißt Zyklus.“ Außerdem sollte man noch den Fall von nur einem Knoten (n=2) und einer Schleife, also $E=\{\{x_{1},x_{n-1}\}\}=\{\{x_{1}\}\}$ ausdrücklich erwähnen.

Außerdem fragt sich, ob die Definition hier nicht redundant zu Kreisgraph ist.

--man (Diskussion) 14:07, 3. Sep. 2024 (CEST)

@DerVanda:: Vielleicht erinnerst du dich an Spezial:Diff/209212536/211091829. Hast du vielleicht eine Quelle, die einen Zyklus wie hier als speziellen Graphen (synonym zu Kreisgraph?) auffasst und nicht nur als Kantenzug? --man (Diskussion) 20:21, 3. Sep. 2024 (CEST)

erledigtErledigt, hoffe ich: Ich habe die Definition gem. Diestel angepasst, der tatsächlich einen Zyklus-Graphen definiert als einen Weg-Graphen, bei dem die Endknoten verbunden sind. Bei Diestel sind Kreise nur für Wege mit mindestens drei Knoten definiert. Dadurch wird das Problem von Mehrfachkanten und Schleifen vermieden. --man (Diskussion) 12:27, 15. Sep. 2024 (CEST)

Sorry für das Hin und Her. Nun war das die Definition eines „Kreises“ (dt. Ausgabe von Diestel). Ein „Zyklus“-Graph wird bei Diestel nicht definiert, ich habe auch keine passende von Kreisgraphen abweichende Definition gefunden. Ich habe darum diese Definition ganz herausgenommen und nur die über einen Kantenzug dringelassen. Jetzt sollte es m.E. wenigstens konsistent zu Weg_(Graphentheorie)#Zyklus,_Kreis,_Eulerzug] sein. --man (Diskussion) 13:06, 15. Sep. 2024 (CEST)