0 Daumen
68 Aufrufe

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

von

Wie kommst du auf den Tag "Turingmaschnine" ?

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

2 Antworten

0 Daumen

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

von 1,9 k
0 Daumen

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

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community