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

Aus VoWi
Zur Navigation springen Zur Suche springen

Man bestimme im Graphen G_5 die Anzahl der Zyklen der Länge 3, auf denen der Knoten 4 liegt.

Nützliches[Bearbeiten]

Wikipedia Zyklus

Lösungsvorschlag[Bearbeiten]

Zyklen können nur innerhalb einer starken Zusammenhangskomponente auftreten, deshalb braucht man nur den rechten Teil des Graphen (mit den Knoten 3,4,5,6,7) betrachten.

Wenn man sich jetzt einen "Baum" aufzeichnet, wo man beginnend mit Knoten 4 immer alle Knoten einträgt die vom Vorgängerknoten erreicht werden können, sieht man schnell welche Zyklen (=die Pfade die wieder zu 4 zurückführen) es gibt.

4 --> 6 +-> 7 --> 3 --> 4    Länge = 4
        |
        +-> 3 --> 4          Länge = 3
        |
        +-> 5 +-> 3 --> 4    Länge = 4
              |
              +-> 4          Länge = 3

--> Es gibt also 2 Zyklen der Länge 3 mit dem Knoten 4.

--W wallner