TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 283

From VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Revision as of 17:46, 7 March 2019 by Gittenborg (talk | contribs) (Gittenborg verschob die Seite TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 283 nach TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 283 und überschrieb dabei eine Weiterleitung: versch…)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Man bestimme die starken Zusammenhangskomponenten und die Reduktion des Graphen .

(Achtung: die Richtung von 2 nach 6 ist falsch eingezeichnet!)

Bsp176 1.png

Theoretische Grundlagen (von mnemetz)[edit]

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ösungsvorschlag der Lerngruppe vom 26.12.2005[edit]

Starke Zusammenhangskomponenten[edit]

  • 1-2-5
  • 7-12-8-11
  • Einzelne Punkte 6, 13, 14, 3, 9, 4, 10

Frage: Warum nicht 7-12-11-6 ?

Graphentheoretische Reduktion[edit]

Bsp176 2.png