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

Man bestimme im Graphen $G_{5}$ die Anzahl der Zyklen der Länge 3, auf denen der Knoten 4 liegt.

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
}}

Nützliches

Wikipedia Zyklus

Lösungsvorschlag

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