TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 286
Man bestimme die starken Zusammenhangskomponenten und die Reduktion des Graphen .
{{Beispiel|1= Angabetext }}
oder
{{Beispiel| Angabetext }}
zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)
{{Beispiel|status=solved|1= Angabetext }}
Theoretische Grundlagen (von mnemetz)[Bearbeiten | Quelltext bearbeiten]
Ein ungerichteter Graph G heißt zusammenhängend, wenn jeder Knoten y von jedem Knoten x aus erreichbar ist.
In einem gerichteten Graph fasst man jene Knoten zu einer starken Zusammenhangskomponente zusammen, die selbst von jedem dieser Knoten erreichbar sind. Sollte ein Knoten nur in einer Richtung erreichbar sein, so wird er selbst zu einer starken Zusammenhangskomponente.
Bei der Reduktion eines Graphen werden die starken Zusammenhangskomponenten zu einem Punkt zusammengefasst und dann verbunden.
Innerhalb einer starken Zusammenhangskomponente ist jeder Knoten von einem anderen Knoten erreichbar. Wenn man die Komponente verlässt, gibt es keinen Weg zurück.
Lösungsvorschlag von mnemetz[Bearbeiten | Quelltext bearbeiten]
Bestimmung der starken Zusammenhangskomponenten[Bearbeiten | Quelltext bearbeiten]
Ein ungerichteter Graph G ist dann zusammenhängend, wenn es zwischen je zwei Knoten von G einen Weg gibt.
Ein starker Zusammenhang liegt dann vor, wenn es zu je 2 Knoten einen Weg von v nach w und einen Weg von w nach v gibt.
Schwach zusammenhängend ist ein Graph dann, wenn sein Schatten zusammenhängend ist. Der Schatten entsteht durch das Weglassen der Kantenorientierungen.
Die starken Zusammenhangskomponenten sind
- {1,7,6}
- {2,4,3}
- {5}