Diskussion:Zyklus (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Fragen zum Algorithmus "Zykluserkennung mittels Tiefensuche"[Quelltext bearbeiten]

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"[Quelltext bearbeiten]

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 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)