Starke Zusammenhangskomponente

nach meiner Meinung muß nicht jeder Zyklus stark zusammenhängend sein. So kann 1-2-3-4 ein Zyklus sein, aber wenn 2 mit 4 nicht direkt verbunden ist - fehlt schon der starke Zusammenhalt.

Jeder Knoten ist für sich eine starke Zusammenhangskomponente

Gruß!
Sigi

Öhm, was ist das Problem bei 1.6?

Laut Musterlösung geben <1,2,3,4,5,6> eine starke Zusamenhangskomponente, gerade weil sie zum Zyklus <1,3,2,6,5,4,1> gehören. Wie es auch der Definition entspricht,von jedem der genannten Knoten lassen sich die anderen erreichen.

Und ein Zyklus ist dadurch definiert, daß es ein Zyklus ist, also ein Kreis, keine Reihe, daher ist auch <1,2,3,4< kein Zyklus, sondern erst <1,2,3,4,1> und jeder Zyklus ist damit auch stark zusammenhängend.

Störend finde ich nur daß jeder einzelne (Rest)-Knoten für sich noch mal eine starke Zusammengehörigkeitskomponente sein soll.

In Übungsaufgabe 1.6 gibt es verschiedene Zyklen,aber nur einer ist eine starke Zusammenhangskomponente (Zhk).
Man bezeichnet nur den größten Zyklus als starke Zhk.Die kleineren Zyklen sind
Teil dieser größten Einheit und bilden keine starken Zhkn.Da Knoten 7 nicht
zu diesem Zyklus gehört bildet er für sich eine andere starke Zhk.
Also ist z.B. der Zyklus 1,2,1 keine starke Zhk.

Der gleiche Zyklus 1,2,1 bildet aber in Beispiel 1.13 sehr wohl eine starke Zhk,
da dieser Zyklus nicht Teil eines größeren Systems ist.Andersfalls wäre eben dieses System die starke Zhk.
Und hier in Beispiel 1.13 sind die Knoten 3 bzw Knoten 4 auch für sich starke Zhkn.
Knoten 5 bzw Knoten 6 bzw Knoten 7 bzw Knoten 8 sind für sich eben keine starken Zhkn.
Und auch Knoten 1 bzw Knoten 2 sind keine starken Zhk.

Hi
Ich habe noch eine Ergänzung/Berichtigung.Wenn man sich die Lösung zu Übungsaufgabe 1.6.
auf Seite 117 genau durch liest,dann stellt man fest,daß der UNTERDIGRAPH,der durch die
Knoten 1,.....,6 fest gelegt ist,die starke Zusammenhangskomponente ist und nicht der Zyklus
1,3,2,6,5,4,1
Das ist ein wichtiger Unterschied,denn zum Unterdigraphen gehören dann auch die Pfeile 1,2
und 2,1 und auch 5,3 dazu.Zum bezeichneten Zyklus gehören sie aber nicht dazu!

Wenn man also starke Zusammenhangskomponenten sucht,dann sucht man den größtmöglichen
Unterdigraphen,innerhalb dessen sich jeder Knoten von jedem anderen Knoten erreichen läßt.
Im äußersten Fall ist der größtmögliche "Unterdigrph" der ganze Digraph.

Das wiederum ist nur eine Umsortierung des Zyklus. Wenn ein Zyklus andere einschließt, dann sind dessen Knoten eine starke Zusamenhangskomponente.
Wie die im Zyklus stehen, ob nun 132, oder 123 ist irrelevant. für die Zusammenhangskomponente aufgezählt werden einfach alle Knoten der Reihe nach..
Und für den Zyklus wiederum wählt man einen beliebigen Weg. Ich kann Dir Zusammenhangskomponente 123456 genauso gut mit der Kante 2,1 1,2 und 5,3 basteln: <6,5,3,2,1,2,6,5,4,1,2,6>.

Der Zyklus muß nicht jeden Knoten nur einmal enthalten.

Blockhaun
Doch,ein Zyklus enthält jeden Knoten nur einmal.
Siehe KE 1,Seite 11:
"...eine geschlossene Pfeilfolge...mit lauter verschiedenen Zwischenknoten...wird Zyklus genannt."

Der Zyklus 1,3,2,6,5,4,1 ist somt nicht die gesuchte starke Zusammenhangskomponente.
Es ist der Unterdigraph,der aus den Knoten 1 bis 6 besteht UND aus ALLEN zwischen
diesen Knoten befindlichen Pfeilen.
Der Zyklus 1,3,2,6,5,4,1 enthält weniger Pfeile als dieser Unterdigraph.

Hm, überlesen.
Nehme alles zurück und widme mich wieder lustigen Sensitivitätsanalysen.