Not logged in. · Lost password · Register

peck
Member since Jul 2010
16 posts
Subject: 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?
Michi D.
Member since Oct 2008
975 posts
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...
This post was edited on 2010-07-29, 14:32 by Michi D..
tsch.aei
Member since Jul 2010
57 posts
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)
knix
Avatar
Member since Oct 2009
242 posts
In reply to post #2
Quote by Michi D. on 2010-07-28, 11:28:
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: 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.
just the BEST theorem: ec(G) = tᵤ(G) ∏(deg(v) - 1)!
This post was edited on 2010-08-03, 12:33 by knix.
ellewoods
Member since Nov 2011
45 posts
Quote by knix on 2010-08-03, 12:32:
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?
Blubbman
Member since Nov 2011
46 posts
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?
neverpanic
Member since Sep 2008
1458 posts
+1 Guanta
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:
A,  B,  C,  D,  E,  F,  6,  7,  8,  9, 10, 11, 12, 13
6,  6,  8, 10, 12, 14,  A,  E,  A,  B,  B,  C,  D,  F
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.
N.K.
Member since Nov 2011
87 posts
Quote by neverpanic on 2012-02-17, 22:33:
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:
A,  B,  C,  D,  E,  F,  6,  7,  8,  9, 10, 11, 12, 13
6,  6,  8, 10, 12, 14,  A,  E,  A,  B,  B,  C,  D,  F
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.

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
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen