Azyklischer Graph, Komplexitätsklasse?

Neue Frage »

Malcang Auf diesen Beitrag antworten »
Azyklischer Graph, Komplexitätsklasse?
Hallo zusammen,

ich habe folgende Aufgabe vor mir:
[attach]56475[/attach]

Dabei ist .

Ich weiß leider nicht recht, wie ich an solche Aufgaben drangehe. Meine Vermutung ist, dass ich eine Turingmaschine angeben muss, die mit Platzverbrauch höchstens entscheidet, ob der Graph azyklisch ist. Also muss ich erstmal einen Algorithmus angeben. Ich habe also den Graphen mit und Nun könnte ich ja jeden beliebigen Pfad aufstellen und überprüfen, ob es ein Zykel ist.
Aber ich sehe auch wiederum den Zusammenhang zu nicht verwirrt

Könnt ihr mir weiterhelfen?

Edit: Muss ich vielleicht die Adjazenzmatrix übergeben? Dann hätte ich aber ja eine Tabelle mit Einträgen...verwirrt
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »