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

Man bestimme im Graphen $G_{9}$ mit Hilfe von $A_{G_{9}}^{3}$ die Anzahl der Dreiecke (d.h. die Anzahl der Kreise der Länge 3).

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

Lösungsvorschlag

$A_{G_{9}}^{3}$ ist die Adjazenzmatrix von $G_{9}$ zur dritten Potenz.

Lemma:

Sei $G$ ein gerichteter Graph mit Adjazenzmatrix $A$. Dann ist der $(i,j)$.Eintrag von $A^{x}$ gleich der Anzahl der verschiedenen Kantenzüge mit Startknoten i und Endknoten j,welche aus x Kanten bestehen.

Adjazenzmatrix $A_{G_{9}}={\begin{array}{cc}&{\begin{array}{cccc}1&2&3&4\end{array}}\\{\begin{array}{r}1\\2\\3\\4\end{array}}&\left({\begin{array}{cccc}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{array}}\right)\end{array}}$

Potenzieren von Matrizen:

Quadratische Matrizen können potenziert werden; $A^{3}=A\cdot A\cdot A$

(siehe auch Wikipedia)

Multiplizieren von Matrizen:

$c_{ij}=\sum _{k=1}^{m}a_{ik}\cdot b_{kj}$

(siehe auch Wikipedia)

Kubizierte Adjazenzmatrix: $A_{G_{9}}^{3}={\begin{array}{cc}&{\begin{array}{cccc}1&2&3&4\end{array}}\\{\begin{array}{r}1\\2\\3\\4\end{array}}&\left({\begin{array}{cccc}6&7&7&7\\7&6&7&7\\7&7&6&7\\7&7&7&6\end{array}}\right)\end{array}}$

Wir suchen nach Kreisen im Graphen, d.h. Kantenzüge mit gleichem Start- und Endknoten; das sind genau diejenigen, die die Hauptdiagonale der Adjazenzmatrix bilden.

Man kommt also auf 6 + 6 + 6 + 6 = 24 Kreise (der Länge 3).

Hier bilden aber etliche Kreise dasselbe Dreieck ab: (abc)=(acb)=(bac)=(bca)=(cab)=(cba), sprich alle Permutationen der drei jeweils beteiligten Knoten.

Um auf die Anzahl der Dreiecke zu kommen, sollte man also die Anzahl der Kreise durch die Anzahl der mögl. Permutationen dividieren:

${\frac {6+6+6+6}{3!}}=4$ Dreiecke.

--Zool 19:55, 23. Nov 2008 (CET)

Links

• f.thread:49410
• http://de.wikipedia.org/wiki/Matrix_(Mathematik)#Potenzieren_von_Matrizen
• http://de.wikipedia.org/wiki/Matrix_(Mathematik)#Matrizenmultiplikation