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

Sei $\widetilde{G_5}$ jener Graph, der aus $G_5$ durch Umdrehen aller Kantenrichtungen entsteht. Man bestimme die Adjazenzmatrix $\tilde{A}(G_5)$, sowie (mit deren Hilfe) die Anzahl der gerichteten Kantenfolgen der Länge 3 von 4 nach 6. (Graph siehe Aufgabensammlung)

Hilfreiches

Aus einer Adjazentmatrix $A^k$ lässt sich die Anzahl von Kantenfolgen der Länge $k$ zwischen zwei je zwei Knoten $v,u\in V(G)$ ablesen.
https://de.wikipedia.org/wiki/Matrizenmultiplikation

Lösungsvorschlag von neo

$A(G_5)=\left(\begin{array}{cccccccc}0& 1& 0& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 0& 1\\ 0& 1& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 0& 1& 0\\ 0& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right)$

$A(\widetilde{G_5})=\left(\begin{array}{cccccccc}0& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 1& 0\\ 0& 0& 1& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 1& 1& 0& 0& 0& 0& 1& 0\end{array}\right)$

$A^2(\widetilde{G_5})=\left(\begin{array}{cccccccc}1& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 2& 0& 0\\ 0& 0& 0& 0& 1& 2& 1& 0\\ 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 1& 0& 0& 0\\ 1& 1& 1& 0& 0& 1& 0& 0\end{array}\right)$

$A^3(\widetilde{G_5})=\left(\begin{array}{cccccccc}0& 1& 0& 0& 1& 1& 1& 0\\ 1& 0& 1& 1& 1& 2& 0& 0\\ 0& 0& 1& 2& 3& 1& 0& 0\\ 0& 0& 0& 2& 2& 2& 0& 0\\ 0& 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 0& 2& 3& 2& 1& 0\\ 0& 0& 1& 0& 1& 1& 0& 0\\ 1& 1& 1& 2& 3& 1& 1& 0\end{array}\right)$

Es existieren 2 gerichtete Kantenfolgen der Länge 3 von 4 nach 6. (Bei $A^3(\widetilde{G_5})$ 4.Zeile, 6.Spalte ablesbar)