• Guten Start ins Wintersemester 2024/2025

Digraph: stark zusammenhängende Komponente

T

TomB

Unser Sponsor SAP 4 Students
Unser Sponsor
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.
 
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.
 
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.
Zum Vergrößern anklicken....

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
Zum Vergrößern anklicken....

Also: Nein
 
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.
 
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 ??
Zum Vergrößern anklicken....

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)
Zum Vergrößern anklicken....
Na, mit sich selber!
 
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.
 
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).
 
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.
 
Oben