Zyklisch := {G | G ist gerichteter zyklischer Graph.} . Zeigen Sie Zyklisch ∈ P.

Question

Hallo alle zusammen :-)

Ich habe folgende Aufgabe:

Aufgabe 1)

Sei G = (V, E) ein gerichteter Graph. Eine Folge von Kanten ((u₁, v₁), . . . ,(ul, vl)) ∈ E^l für l ≥ 1 heißt Zyklus, falls für alle i = 1, . . . , l − 1 gilt vi = ui+1 und vl = u1. Ein Graph G heißt zyklisch, wenn mindestens ein Zyklus in G existiert. Sei nun 
                                                       Zyklisch := {G | G ist gerichteter zyklischer Graph.} 

Zeigen Sie Zyklisch ∈ P. 

Wie kann ich diese Aufgabe zeigen ?

Danke für jede Hilfe im Voraus :-)

Comments

Wie kommst du auf den Tag "Turingmaschnine" ?

Wenn so wichtig, warum nicht auch in der Überschrift?

Answer 1

Gib einen Algorithmus mit polynomieller Laufzeit an, mit überprüft werden kann, ob ein gerichteter Graph zyklisch ist.

Answer 2

Eine Möglichkeit zur Findung eines Zyklusses ist die Tiefensuche auch DFS genannt, diese hat eine Laufzeit von O(|V| + |E|)