Komplexität eins Algorithmus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:24 Do 28.05.2009 | | Autor: | tina2 |
| Aufgabe 1 | Gegeben sei ein ungerichteter Graph mit n Ecken
Skizzieren Sie einen Algorithmus mit einer Komplexität von O(n), 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.
|
| Aufgabe 2 | Falls der Graph als Adjazenzmatrix dargestellt ist - welche Komplexität hat ein darauf basierender Algorithmus, der den Graphen auf Kreisfreiheit testet?
|
Hi,
leider verstehe ich die Fragestellung gar nicht. Ich weiß gar nicht wie ich da überhaupt anfangen soll. Muss man da etwas zeichnen, Pseudocode verwenden oder wie ?
Ich freue mich über Tipps und Hinweise so dass ich selber die Aufgabe lösen kann.
Viele Grüße,
tina2
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Erstmal solltest du dir überlegen, wie du einfach feststellen kannst, ob ein Graph zyklisch ist oder nicht. Vielleicht kannst du ein Kriterium nennen? Dann finde ein Verfahren, wie man dieses Kriterium überprüft. Dieses Verfahren ist dann der gesuchte Algorithmus.
|
|
|
| |
|
Hallo tina2!
> Gegeben sei ein ungerichteter Graph mit n Ecken
>
> Skizzieren Sie einen Algorithmus mit einer Komplexität von
> O(n), 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.
>
> Falls der Graph als Adjazenzmatrix dargestellt ist - welche
> Komplexität hat ein darauf basierender Algorithmus, der den
> Graphen auf Kreisfreiheit testet?
>
>
> Hi,
> leider verstehe ich die Fragestellung gar nicht. Ich weiß
> gar nicht wie ich da überhaupt anfangen soll. Muss man da
> etwas zeichnen, Pseudocode verwenden oder wie ?
Ich denke, "skizzieren" ist hier nicht als "zeichnen" zu verstehen. Ich würde einen Pseudocode angeben.
> Ich freue mich über Tipps und Hinweise so dass ich selber
> die Aufgabe lösen kann.
Kannst du das jetzt?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
|
