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

From VoWi
Jump to navigation Jump to search

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

Bsp175 1.png

Nützliches[edit]

Adjazenzmatrix
Wikipedia Erreichbarkeitsmatrix
Multiplizieren von Matrizen

Lösungsvorschlag von W wallner[edit]

Adjazenzmatrix des Graphen

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 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{pmatrix}

Adjazenzmatrix multipliziert mit sich selbst:

A^2_{G_5} = \begin{pmatrix}
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{pmatrix}

Adjazenzmatrix hoch 3:

A^3_{G_5} = \begin{pmatrix}
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{pmatrix}

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^2_{G_5} und A^3_{G_5} 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^2_{G_5} für das Feld (1,1) der Matrize ja schon 2 rauskommen.

Lösungsvorschlag von der Lerngruppe vom 26.12.2005[edit]

(Dank an Sarah!)

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 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{pmatrix}


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

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