Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Graphen 31.07.2008
Aufgabe 7a):
zwei kleine fragen:
Ist der Graph stark zusammenhängend? (die vorlesungsfolien interpretiere ich so, dass nur gerichtete Graphen stark zusammenhängend sein können)
Kann der Graph mit Hilfe der Tiefensuche vollständig traversiert werden?
Was heißt stark zusammenhängend? - jeder Knoten ist mit jedem anderen verbunden… Das ist doch offensichtlich nicht gegeben (jetzt mal unabhängig vom zusammenhängend).
Frage 2 kann man eigentlich umformen: ist der Graph (schwach) zusammenhängend? - ja! (sonst wären es gewissermaßen “zwei” Graphen)
EDIT: Fehler entfernt…
Stark zusammenhängend gibt es in beiden Grapharten, gerichtet wie ungerichtet. Ein ungerichteter Graph ist bspw. ein Baum, wenn er stark zusammenhängend ist, keine Schlingen enthält und es zwischen zwei verschiedenen Knoten genau einen Pfad gibt. (s. Vorlesungsfolie 16-10)
Stark zusammenhängend: Man kann von jedem Knoten aus, jeden anderen Knoten erreichen (es gibt einen Pfad).
Da der Graph in der Aufgabe ungerichtet ist und damit eben genau diese Eigenschaft erfüllt. => stark zusammenhängend.
Schwach zusammenhängend: Man hat einen gerichteten Graph und der zugehörige ungerichtete Graph ist (stark) zusammenhängend.
Aber wenn der Graph ungerichtet ist, kann man dann nicht auch sagen er kann gar nicht STARK zusammenhängend sein. Also hab ich bei 7a)2 nein angekreuzt…
sonst hab ich auch immer nein. nur bei 3. keine Ahnung. Kann mir bitte jemand erklären was mit traversieren überhaupt gemeint ist?
Bei der Aufgabe 10.b soll man die Adjazenzliste als Reihung darstellen. Nun hat ja der Knoten “A” aber keinen Nachfolger…was schreib ich nun in das erste Feld für eine Zahl?
Die Idee bei dieser Darstellung der Adjazenzliste ist, dass die ersten n Indizes jeweils für die n Knoten stehen und an dieser Stelle im Array der Index steht, an dem die Nachfolger für diesen Knoten im Array beginnen. Daraus kann man anhand des Werts der nächsten Stelle im Array (der Startindex der Nachfolger des nächsten Knotens) erschließen, wo die Nachfolger eines Knotens enden. In diesem Fall also:
[m] A, B, C, D, E, F, 6, 7, 8, 9, 10, 11, 12, 13[/m]
[m] 6, 6, 8, 10, 12, 14, A, E, A, B, B, C, D, F[/m]
D.h. keine Nachfolger erkennt man daran, dass der Beginn der Liste in dem die Knoten beschreibenden Bereich zwei gleiche Indizes aufeinanderfolgend enthält. Ich habe zur Vereinfachung im hinteren Bereich mal Buchstaben geschrieben, da würden dann natürlich die äquivalenten Zahlen stehen.
1 „Gefällt mir“
Hätte man solche Sonderfälle mal in der Vorlesung erklärt bekommen ^^
Da steht eine ganze Folie zu dem Thema „AdjaListe als Reihung“ drin xD