Digraph: stark zusammenhängende Komponente

TomB · 13 September 2016

bin gerade dabei an mir selber zu zweifeln.
Ein ähnliches Thema oder evtl sogar dieses wurde schon mal diskutiert, aber auch die Erklärungen dort habe ich nicht begriffen, also:

Definition:
Ein Digraph G heisst stark zusammenhängend, wenn für je zwei Knoten i,j von G:
i von j aus und j von i aus erreichbar sind.

Dann heisst es ja auch noch: Jeder Knoten ist von sich selbst aus erreichbar.

Jetzt verstehe ich nicht, warum im Skript S.14, Bsp 1.13, u.a. die Knoten 3 und 4 starke Zusammenhangskomponenten sind !!

Ich brauche doch mindestens 2 Knoten per Definition, oder nicht ?
Oder reicht auch einer, weil jeder Knoten von sich selbst erreichbar ist, aber das wäre ja Blödsinn, denn dann wären ja alle Knoten stark zusammenhängend. ?

Wäre nett wenn jemand was dazu sagen könnte.

RasmusX · 15 September 2016

Vielleicht hilft folgende Formulierung weiter: jeder Knoten a liegt in der von ihm erzeugten starken Zusammenhangskomponente; ein weitere Knoten b liegt nur darin, wenn a von b aus erreibar und b von a aus erreichbar ist.

Zu sagen ein Knoten a sei stark zusammenhängend ergibt keinen Sinn - höchstens dass seine starke Zusammenhangskomponente nur aus einem Knoten besteht; dies bedeutet dann, dass es keinen anderen Knoten b gibt, sodass a von b aus erreibar und b von a aus erreichbar ist.

Riff · 15 September 2016

die Definition ist so:

TomB schrieb:
Hallo zusammen,

Definition:
Ein Digraph G heisst stark zusammenhängend, wenn für je zwei Knoten i,j von G:
i von j aus und j von i aus erreichbar sind.

Dann heisst es ja auch noch: Jeder Knoten ist von sich selbst aus erreichbar.

Laut Definition ist der starke Zusammenhang auf eine Eigenschaft heruntergebrochen, die für ALLE Knotenpaare i und j des Graphen erfüllt sein muss (nämlich die Erreichbarkeit). Aber laut Definition ist die Menge der Knotenpaare nicht darauf beschränkt, dass die Knoten des Paares verschieden sind. Für alle Knoten k dess Graphen MUSS für den starken Zusammenhang des Graphen diese Eigenschaft ebenfalls erfüllt sein, d.h. k von k aus erreichbar sein, was nach Definiton auch immer der Fall ist (also keine Schwierigkeiten bereitet).

Daraus folgt, dass jeder Graph, der aus genau einem Knoten besteht, stark zusammenhängend ist.

TomB schrieb:
Ich brauche doch mindestens 2 Knoten per Definition

Also: Nein

TomB · 15 September 2016

Sorry,
ich habe es immer noch nicht :-(

Wenn ich mir im Skript S.14, Bsp 1.13 anschaue, dann

- gehen von Knoten 4 nur Pfeile aus, wird von keinem anderen erreicht und ist nicht isoliert. Wieso (bzw mit wem) soll der stark zusammenhängend sein ??
- Knoten 3 wird nur von Knoten 4 erreicht, kann diesen selbst aber nicht erreichen !! Wieso stark zusammenhängend ?

Erreichbarkeit ist doch nur über einen Weg gegeben ! Hat doch mit einer Semipfeilfolge nichts zu tun.

Riff · 16 September 2016

TomB schrieb:
- gehen von Knoten 4 nur Pfeile aus, wird von keinem anderen erreicht und ist nicht isoliert. Wieso (bzw mit wem) soll der stark zusammenhängend sein ??

JEDER Knoten eines Graphen bildet einen eigenen Untergraphen und der ist immer stark zusammenhängend, wie ich oben erklärt habe. Man kann auch sagen, dass JEDER Knoten eines Graphen für sich eine starke Zusammenhangskomponente bildet, denn: Für eine Zusammenhangskomponente, die nur aus einem Knoten besteht, ist jeder Knoten von jedem Knoten erreichbar (es gibt ja nur einen Knoten und nach Definition ist jeder Knoten von sich selbst aus erreichbar).

TomB schrieb:
(bzw mit wem)

Na, mit sich selber!

TomB · 16 September 2016

Das heisst:
ein Digraph mit

- 2 Knoten hat mindestens 2 starke Zusammenhangskomponenten,
a) 1 -> 2 ( 2 starke)
b) 1 <-> 2 ( 3 starke da jeder von jedem erreichbar)

- 3 Knoten
a) 1 -> 2 -> 3 ( 3 starke)
b) 1 -> 2 <-> 3 ( 4 starke, weil 2 und 3 sich gegenseitig ... )
usw.

Riff · 16 September 2016

nach der hier zugrundeliegenden Definition von starker Zusamhangskomponente ist das richtig. Aber der Vollständigkeit sei angemerkt, dass es auch andere Definitionen von starker Zusammhangskomponente gibt, z.B. folgende:

Ein induzierter Teilgraph G für eine Teilmenge U der Knotenmenge V eines Graphen G = G[V] heißt starke Zusammenhangskomponente von G, falls G stark zusammenhängend ist und nicht zu einem größeren stark zusammenhängenden Teilgraphen von G erweitert werden kann.

Nach dieser Definiton sieht das bei Deinen Beispilen so aus:

a) 1 -> 2 ( 2 starke)
b) 1 <-> 2 ( 1 starke da 1 und 2 für sich alleine zwar auch stark zusammenhängend sind, aber zu 1<->2 ebenfalls stark zusammenhängend erweitert werden können).

- 3 Knoten
a) 1 -> 2 -> 3 ( 3 starke)
b) 1 -> 2 <-> 3 ( 2 starke, da 2 und 3 für sich alleine zwar auch stark zusammenhängend sind, aber zu 2<->3 ebenfalls stark zusammenhängend erweitert werden können).

TomB · 16 September 2016

Riff,
danke Dir, jetzt habe ich es langsam, Danke 🙂

Der Knackpunkt was mich wohl zur Verzweiflung gebracht hat:
Ein Knoten kann stark zusammenhängend sein, obwohl (!!!) er nicht isoliert ist.
Man hätte in der Definition vllt auch schreiben können "... zwei nicht notwendigerweise unterschiedliche Knoten"
oder so ähnlich.

Riff · 16 September 2016

TomB schrieb:
Man hätte in der Definition vllt auch schreiben können "... zwei nicht notwendigerweise unterschiedliche Knoten"
oder so ähnlich.

Es wird oft andersherum gemacht. Wenn Unterschiedlichkeit gefordert ist, wird es hingeschrieben, z.B. "... i und j zwei Knoten und i =|= j ..."

Digraph: stark zusammenhängende Komponente

Thema 'Termine Modul 32831 Elemente der Finanzwirtschaft'

Thema 'Termine Modul 32791 Dienstleistungsmanagement – Kundenbeziehungsmanagement'

Thema 'Termine Modul 32781 Rechnungslegung'

Thema 'Termine Modul 32771 Internationale Finanzwissenschaft und Umweltökonomie'

Thema 'Termine Modul 32751 Konstruktion und Analyse ökonomischer Modelle'

TomB

RasmusX

Riff

TomB

Riff

TomB

Riff

TomB

Riff

Weiter lesen