Algorithmus Graphen

[GuStaV%%]

Hallo zusammen,

Ich bin gerade dabei Graphen und Bäume am Üben.

Ich habe hier nun folgende Aufgabe:

"Wir erinnern an die Definition eines Graphen: Ein endlicher Graph ist ein Zweitupel (V, E), wobei V eine endliche Menge und E (Teilmenge oder gleich) V x V ist. Ein Kreis in einem Graphen ist eine Folge von Kanten (v1, v2), (v2, v3) .... (vn-1, vn) n >_4 (>_: steht für größer oder gleich), so dass v1 = vn gilt. Geben Sie einen Algorithmus an, der ermittelt, ob ein Graph einen Kreis enthält und erläutern Sie, wieso der Algorithmus korrekt ist."

Leider fehlt mir hier schon irgendwie der Ansatzpunkt und die Fantasie. Kann mir bei der Aufgabe jemand helfen?

Vielen Dank im Voraus.

 

[mihe7]

Naja, Du führst eine Tiefensuche durch und markierst dabei die besuchten Knoten. Wird ein markierter Knoten besucht, hast Du einen Zyklus gefunden.

 

[GuStaV%%]

hmm könntest du mich da vielleicht ein bisschen mit Code unterstützen oder kennst du gute Tutorials oder Links von Erklärungen für das? weil mir fehlt hier sogar gerade der Ansatz.....

 

[kneitzel]

Wie wäre es ggf. mit https://de.wikipedia.org/wiki/Tiefensuche? Das könnte schon fast reichen ...

 

[fhoffmann]

Naja, Du führst eine Tiefensuche durch und markierst dabei die besuchten Knoten. Wird ein markierter Knoten besucht, hast Du einen Zyklus gefunden.

Das funktioniert so leider nicht. Ein Gegenbeispiel:

V = {v1, v2}
E = {(v1, v2), (v2, v1)}

Dies ist kein Kreis (nach der Definition in der Aufgabenstellung).

Edit: Ich muss mich korrigieren. Zwar ist

(v1, v2), (v2, v1)

kein Kreis (im Sinne der Aufgabenstellung), jedoch:

(v1, v2), (v2, v1), (v1, v2), (v2, v1)

Hier ist die Definition in der Aufgabenstellung etwas unklar.

 

[mihe7]

Hier ist die Definition in der Aufgabenstellung etwas unklar.

Naja, man hat ja eine Kantenmenge, im Fall (v1, v2), (v2, v1), (v1, v2), (v2, v1) wäre E={(v1, v2), (v2, v1)} 🙂

 

[fhoffmann]

Ich frage mich, was die Bedingung "n >= 4" soll, wenn man nicht gleichzeitig fordert, dass v1, ... , vn-1 unterschiedlich sind.

 

[GuStaV%%]

hmmm könnte mir hier vielleicht jemand ein Beispiel mit Code angeben? Ich blick es nicht so richtig. Vielleicht mit Kommentare....

 

[LimDul]

Das funktioniert so leider nicht. Ein Gegenbeispiel:

V = {v1, v2}
E = {(v1, v2), (v2, v1)}

Dies ist kein Kreis (nach der Definition in der Aufgabenstellung).

Edit: Ich muss mich korrigieren. Zwar ist

(v1, v2), (v2, v1)

kein Kreis (im Sinne der Aufgabenstellung), jedoch:

(v1, v2), (v2, v1), (v1, v2), (v2, v1)

Hier ist die Definition in der Aufgabenstellung etwas unklar.

Ich vermute fast das es um ungerichtete Graphen gehen soll und damit die Kante (v1,v2) und die Kante (v2,v1) in Wirklichkeit eine Kante sind. In dem Augenblick würde die Bedingung mit n größer >=4 Sinn ergeben - weil in einem ungerichten Graphen braucht man drei (unterschiedliche) Kanten für die Definition eines Kreises. Aber ich bin bei dir - das geht aus der Aufgabenstellung nicht hervor.

 

[LimDul]

hmmm könnte mir hier vielleicht jemand ein Beispiel mit Code angeben? Ich blick es nicht so richtig. Vielleicht mit Kommentare....

hmmm könnte mir hier vielleicht jemand ein Beispiel mit Code angeben? Ich blick es nicht so richtig. Vielleicht mit Kommentare....

Tiefensuche – Wikipedia

de.wikipedia.org

 

[GuStaV%%]

hmm okay, ich versuch mich da jetzt mal übers Internet einzulesen. Vielen Dank an alle.