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 :-)
Wie kommst du auf den Tag "Turingmaschnine" ?
Wenn so wichtig, warum nicht auch in der Überschrift?
Gib einen Algorithmus mit polynomieller Laufzeit an, mit überprüft werden kann, ob ein gerichteter Graph zyklisch ist.
Eine Möglichkeit zur Findung eines Zyklusses ist die Tiefensuche auch DFS genannt, diese hat eine Laufzeit von O(|V| + |E|)
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos