Einseitig zusammen hängender Graph - oder nicht?

27/03/2012 - 15:25 von Georg Bauhaus | Report spam
Hallo,
beim semi-hobbyweisen Wiederholen von Stoff aus dem Regal
komme ich auf folgenden gerichteten Graphen und ins Stocken.

G = {(a, b), (a, c), (a, d)
(b, c),
(d, b), (d, c)}

Also

d -> c
\ ,'^
| |
v / \.
a -> b

Der Autor des Buches[1], mit dem ich ansonsten vergnügt arbeite,
behauptet, dass der Graph weder stark zusammenhàngend [o.K.],
noch einseitig zusammenhàngend [hier stocke ich], aber schwach
zusammenhàngend sei [o.K.]. Einseitig zusammenhàngend ist definiert,
"wenn für je zwei Ecken e, e' mindestens eine von der anderen
aus erreichbar ist." [S.53] Erreichbarkeit bedeutet einen Weg
der Lànge n >= 0.

Vielleicht sehe ich ja den Wald vor Bàumen nicht. Aber für alle
sechs (ungeordneten) Ecken-Paare,
(a b), (a c), (a d), (b c), (b d), (c d)
scheint mir zu gelten, dass mindestens eine Ecke von der anderen
aus erreichbar ist:

a -> b,
a -> c,
a -> d,
b -> c,
d -> b,
d -> c.

Demnach wàre G doch einseitig zusammenhàngend.
Was habe ich übersehen oder nicht verstanden?


Georg
__
[1] Goos, Vorlesungen über Informatik, Band 1, Springer, 3. Auflage.
 

Lesen sie die antworten

#1 Nicolas Berr
29/03/2012 - 09:52 | Warnen spam
Hi Georg,

ich würde nach dem was Du schreibst sagen, dass der beschriebene Graph
sowohl einseitig zusammenhàngend als auch schwach zusammenhàngend nicht
jedoch stark zusammenhàngend ist.

Würde man die Kante (b,c) entfernen wàre er nicht mehr einseitig
zusammenhàngend aber immer noch schwach zusammenhàngend.

Zumindest nach den Definitionen die ich dazu gefunden habe.

Viele Grüße,
Nicolas


Am 27.03.2012 15:25, schrieb Georg Bauhaus:
Hallo,
beim semi-hobbyweisen Wiederholen von Stoff aus dem Regal
komme ich auf folgenden gerichteten Graphen und ins Stocken.

G = {(a, b), (a, c), (a, d)
(b, c),
(d, b), (d, c)}

Also

d -> c
\ ,'^
| |
v / \.
a -> b

Der Autor des Buches[1], mit dem ich ansonsten vergnügt arbeite,
behauptet, dass der Graph weder stark zusammenhàngend [o.K.],
noch einseitig zusammenhàngend [hier stocke ich], aber schwach
zusammenhàngend sei [o.K.]. Einseitig zusammenhàngend ist definiert,
"wenn für je zwei Ecken e, e' mindestens eine von der anderen
aus erreichbar ist." [S.53] Erreichbarkeit bedeutet einen Weg
der Lànge n>= 0.

Vielleicht sehe ich ja den Wald vor Bàumen nicht. Aber für alle
sechs (ungeordneten) Ecken-Paare,
(a b), (a c), (a d), (b c), (b d), (c d)
scheint mir zu gelten, dass mindestens eine Ecke von der anderen
aus erreichbar ist:

a -> b,
a -> c,
a -> d,
b -> c,
d -> b,
d -> c.

Demnach wàre G doch einseitig zusammenhàngend.
Was habe ich übersehen oder nicht verstanden?


Georg
__
[1] Goos, Vorlesungen über Informatik, Band 1, Springer, 3. Auflage.

Ähnliche fragen