Algorithmen und Graphen |
| 15.12.2004, 14:06 | jojo | Auf diesen Beitrag antworten » |
| Algorithmen und Graphen bräuchte bitte dringend Hilfe bei dieser Aufgabe, da leider keine Ahnung... Gegeben sei ein ungerichteter Graph mit n Ecken. a) Skizzieren Sie einen Algorithmus mit einer Komplexität von O(n) (im "Worst Case"), der den Graphen daraufhin testet, ob er azyklisch ist, also keine Kreise besitzt (Antwort: "ja" oder "nein"). Nehmen sie dabei an, dass der Graph durch Nachbarschaftslisten repräsentiert ist. b) Falls der Graph als Adjazenzmatrix dargestellt ist - welche Komplexität hat ein darauf basierender Algorithmus, der den Graphen auf Kreisfreiheit testet? Vielen Dank. |
||
| 17.12.2004, 12:32 | jojo | Auf diesen Beitrag antworten » |
Hallo nochmal, bin nu ein Stück weiter... aber gibt es denn hier niemanden, der mir helfen kann???? Hab zwar noch keinen Ansatz, aber schonmal ein paar Infos: Also, zu 1a) Ungerichtete Graphen sind irreflexive Relationen, d.h. sie haben nur Oen in der Hauptdiagonale bei Matrizendarstellung. Ein ungerichteter Graphen in Nachbarschaftslistendarstellung hat eine Komplexität von O(|E| + |K|). Da |E| der Betrag der Ecken ist, könnte man dann O(|n| + |K|) annehmen, weil n die Anzahl der Ecken ist? ja-nein-Fragen gehören der NP-Komplexitätsklasse an. meint worst case T(n) = O(n) wobei T die Anzahl der Eingabedaten ist?? zu 1b) Die Komplexität bei Darstellung als Adjazenzmatrix ist O(|E|²). Hat der Algorithmus dann die Komplxität T(n) = O(|n|²) ??? Tja, soweit bin ich bisher... bitte echt um Hilfe. WICHTIG AUFGABE!! |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
