Azyklischer Graph, Komplexitätsklasse? |
05.12.2022, 21:05 | Malcang | Auf diesen Beitrag antworten » |
Azyklischer Graph, Komplexitätsklasse? 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 Könnt ihr mir weiterhelfen? Edit: Muss ich vielleicht die Adjazenzmatrix übergeben? Dann hätte ich aber ja eine Tabelle mit Einträgen... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |