TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 285

Man bestimme die starken Zusammenhangskomponenten und die Reduktion $G_{1R}$ des Graphen $G_{1}$.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{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)

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.

Lösungsvorschag (von der Lerngruppe vom 26.12.2005)

Starken Zusammenhangskomponenten

Starke Zusammenhangskomponenten sind:

• 3-2-1-4
• 2-1-4 (ist umstritten wg. obigem -- Anm. Benutzer:dlaxar lt. Definition 2.21 (4. Auflage Math.für.Inf) ist eine starke Zusammenhangskomponente maximal. würde 2-1-4 also nicht nehmen, da nicht maximal)
• 5
• 6
• 7

Reduktion