gemischter Graph < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich bereite mich derzeit für eine Klausur im Sommer des Faches "Angewandte Graphentheorie" vor. Nun habe ich ein paar Übungsaufgaben und zu einer dieser eine Frage.
Es geht um die Berechnung des Speicherbedarfs eines gemischten Graphen, jeweils für die Gewichtsmatrix und beide Adjazenzlisten.
Kann mir jemand sagen, wie man den Speicherbedarf errechnet? Besonders für die Adjazenzlisten! Die Aufgabe findet ihr in Form eines GIF-Bildes auf http://www-stud.fh-fulda.de/~fdai2262/extern/graph.GIF
Die Gewichtsmatrix habe ich schon einmal erstellt. Sie sieht wiefolgt aus:
[mm] \infty \infty \infty \infty \infty [/mm] -6
2 [mm] \infty [/mm] 3 -6 4 [mm] \infty
[/mm]
-1 3 [mm] \infty [/mm] -5 [mm] \infty [/mm] 4
[mm] \infty [/mm] -6 -5 [mm] \infty [/mm] 3 [mm] \infty
[/mm]
[mm] \infty [/mm] 4 [mm] \infty [/mm] 3 [mm] \infty [/mm] 2
[mm] \infty \infty [/mm] 4 7 2 [mm] \infty
[/mm]
Ich denke, dass der Speicherbedarf hierbei n*n ist.
Vielen Dank für die Hilfe
[Dateianhang nicht öffentlich]
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Dateianhänge:
Anhang Nr. 1 (Typ: GIF) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:45 Mo 06.06.2005 | | Autor: | Marc |
Hallo dennis3484,
> ich bereite mich derzeit für eine Klausur im Sommer des
> Faches "Angewandte Graphentheorie" vor. Nun habe ich ein
> paar Übungsaufgaben und zu einer dieser eine Frage.
>
> Es geht um die Berechnung des Speicherbedarfs eines
> gemischten Graphen, jeweils für die Gewichtsmatrix und
> beide Adjazenzlisten.
>
> Kann mir jemand sagen, wie man den Speicherbedarf
> errechnet? Besonders für die Adjazenzlisten! Die Aufgabe
> findet ihr in Form eines GIF-Bildes auf
> http://www-stud.fh-fulda.de/~fdai2262/extern/graph.GIF
>
> Die Gewichtsmatrix habe ich schon einmal erstellt. Sie
> sieht wiefolgt aus:
>
> [mm]\infty \infty \infty \infty \infty[/mm] -6
> 2 [mm]\infty[/mm] 3 -6 4 [mm]\infty[/mm]
> -1 3 [mm]\infty[/mm] -5 [mm]\infty[/mm] 4
> [mm]\infty[/mm] -6 -5 [mm]\infty[/mm] 3 [mm]\infty[/mm]
> [mm]\infty[/mm] 4 [mm]\infty[/mm] 3 [mm]\infty[/mm] 2
> [mm]\infty \infty[/mm] 4 7 2 [mm]\infty[/mm]
Auf der Hauptdiagonalen hätte ich jetzt Nullen erwartet, aber möglicherweise macht es Sinn, dort auch ein Gewicht von [mm] $\infty$ [/mm] zuzuweisen.
> Ich denke, dass der Speicherbedarf hierbei n*n ist.
Ja, wenn man es sich bequem machen will und alles in ein zweidimensionales Feld packt.
Die Hauptdiagonale müßte aber eigentlich nicht gespeichert werden, wenn man sich vorher auf einen Eintrag einigt (0 oder [mm] $\infty$).
[/mm]
Der Speicherbedarf wäre dann "nur" $O(n*(n-1))$
Bei der Aufgabe ist aber schon der konkrete Wert gefragt, also $6*5=30$
> [Dateianhang nicht öffentlich]
Eine Adjazenzliste eines Knotens A ist ja (nehme ich mal an) eine Liste der Knoten B, so dass [mm] $\overrightarrow{AB}$ [/mm] eine Kante des Graphen ist.
Ich würde dann so rechnen:
Für jeden Knoten benötigen wir schon mal ein Speicherwort (für die "Verwaltungsdaten" der Adjazenzliste des Knotens).
Für jede Kante nun benötigen wir ein weiteres Speicherwort, denn es wird ja die Speicheradresse des Endknotens in die Adjazenzliste des Anfangsknotens geschrieben. Beachte, dass die Kanten gerichtet sind.
Es entsteht also so etwas:
[mm] $S_1=[S_6]$
[/mm]
[mm] $S_2=[S_1,S_3,S_4,S_5]$
[/mm]
[mm] $S_3=\ldots$
[/mm]
[mm] $\vdots$
[/mm]
Insgesamt benötigen wir folgenden Speicher: Anzahl Knoten + Anzahl Kanten = 6 + 16 = 22
Die Raumkomplexität wäre dann: [mm] $O(n+n^2)=O(n^2)$
[/mm]
Bei c) bin ich mir unsicher, was mit den zwei Varianten gemeint ist, da müßtest du nochmal in deine Vorlesung schauen.
Die erste Variante ist aber unsere Lösung mit der Gewichtsmatrix oben, wobei ich einer vorhandenen Kante das Gewicht 1 gebe und einer nicht vorhandenen Kante das Gewicht 0.
Die Raumkomplexität ist dieselbe wie in a).
Viele Grüße,
Marc
|
|
|
|
