TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 191

Man bestimme die Adjazenzmatrix $A(G_5)$ sowie (mit deren Hilfe) die Anzahl der gerichteten Kantenfolgen der Länge 3 von 4 nach 6!

Nützliches

Adjazenzmatrix
Wikipedia Erreichbarkeitsmatrix
Multiplizieren von Matrizen

Lösungsvorschlag von W wallner

Adjazenzmatrix des Graphen

$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\\ 1& 0& 0& 0& 0& 0& 0& 0\end{array}\right)$

Adjazenzmatrix multipliziert mit sich selbst:

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

Adjazenzmatrix hoch 3:

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

Man sieht in der 4. Zeile, 6. Spalte, dass es genau einen Weg der Länge 3 vom Punkt 4 zum Punkt 6 gibt ( 4 -> 6 -> 5 -> 6 ).

Frage von CG: Sicher dass die Potenzmatrizen $A_{G_5}^2$ und $A_{G_5}^3$ so stimmen? Ich sitze schon seit einer Ewigkeit und suche nach moeglichen Fehlern in meiner Version aber ich komme einfach nicht auf das selbe Ergebnis. Danke

---

Kann bestätigen das mit den Matrizen etwas nicht stimmen kann. Beim ersten hinschauen müsste bei $A_{G_5}^2$ für das Feld (1,1) der Matrize ja schon 2 rauskommen.

Lösungsvorschlag von der Lerngruppe vom 26.12.2005

(Dank an Sarah!)

$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\\ 1& 0& 0& 0& 0& 0& 0& 0\end{array}\right)$

Anzahl der gerichteten Kantenfolgen mit Länge 3 von 4 nach 6: 2

• $4\to 6\to 5\to 4$
• $4\to 3\to 6\to 4$

Anmerkung: Da es ein gerichteter Graph ist (man beachte die Pfeilrichtungen!), gibt es keine Verbindung von 4 nach 3!