Übungsaufgaben: B0103 b)

Wie müssen die starken Zusammenhangskomponenten eines schwach zusammenhängenden Digraphen G aussehen, damit G topologisch sortierbar ist?
(Begründung!)

Antwort: Ein topologisch sortierbarer Digraph G muss zyklenfrei sein, d. h. jede starke Zusammenhangskomponente von G besteht aus genau einem Knoten von G .

Bei vier Knoten würde das dann ja beispielsweise so aussehen:

O--->O--->O O

allerdings hätte ich gedacht, dass "schwach zusammenhängend" gerade dadurch definiert ist, dass jeder Knoten mit genau einem anderen Knoten durch einen Pfeil verbunden ist, was ja bei einer Komponente aus gerade einem Knoten doch eigentlich nicht mehr der Fall ist, oder?

schwach zusammenhängend fordert erst mal nur einen Semi-weg. Also wäre
O <-- O --> O schwach zusammenhängend, definitv aber nicht stark

"stark zusammenhängend": wenn i von j und j von i aus erreichbar ist => für i=j: jeder Knoten ist von sich selbst aus erreichbar => ein Knoten allein bildet eine starke Zusammenhangskomponente.

Wäre eine starke Zusammenhangskomp. einesDigraphen größer als ein Knoten allein, gäbe es einen Zyklus und er wäre nicht mehr toplogisch sortierbar.

Vielen Dank. - Das bedeutet aber dann auch, dass die Vonsichselbstauserreichbarkeit eines Knotens nur dann zum Tragen kommt, wenn er alleine steht, ansonsten gebe es ja in O<-- O -->O alleine schon drei starke Zusammenhangskomponenten, oder?

sehe ich auch so, wenn in diesem Graphen nach starken Zshngskpntn gefragt würde, müßte man die 3 Knoten "an sich" nennen. das wären aber auch schon alle. Und der komplette Graph wäre eine schwache Zshngskmpnte. weil alle 3 Knoten durch einen Semi-pfeilfolge erreicht werden.