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

Sei ${\tilde {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})={\begin{pmatrix}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{pmatrix}}$

$A({\tilde {G_{5}}})={\begin{pmatrix}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{pmatrix}}$

$A^{2}({\tilde {G_{5}}})={\begin{pmatrix}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{pmatrix}}$

$A^{3}({\tilde {G_{5}}})={\begin{pmatrix}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{pmatrix}}$

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