Bestimme mit der Adjazenzmatrix des Graphen die Anzahl der Wege der Länge 4 von u1 nach u3 .

Question

Aufgabe:

2. Gegeben ist der Graph

(a) Bestimme mit der Adjazenzmatrix des Graphen die Anzahl der Wege der Länge 4 von $u_{1}$ nach $u_{3}$.
(b) Gib alle diese Wege der Länge 4 von $u_{1}$ nach $u_{3}$ an.

Problem/Ansatz:

Wie berechnet man das? Bei mir kamen für Länge 4 von u1 -> u3, einfach 441 raus. Ich befürchte, dass das nicht stimmt zudem man bei b alle Wege deklarieren soll.

Answer 1

Die Adjazenzmatrix gibt die die Anzahl an Wegen von $u$ nach $v$ der Länge eins an (denn ein Eintrag ist ja genau dann eins, wenn eine Kante zwischen zwei Knoten existiert). Ich bezeichne die Einträge der Adjazenzmatrix jetzt mal mit $a_{i, j}$, wobei $a_{i, j}=1 \Longleftrightarrow$ es existiert eine Kante zwischen den Knoten $i$ und $j$. Möchtest du nun die Wege der Länge 2 zwischen zwei Knoten $i$ und $j$ bestimmen, so überprüfst du ja für jeden Nachbarn von $i$ ob er auch ein Nachbar von $j$ ist. Mithilfe der Einträge der Adjazenzmatrix ausgedrückt also
$a_{i, 1} \cdot a_{1, j}+a_{i, 2} \cdot a_{2, j}+\ldots+a_{i, n} \cdot a_{n, j}=\sum \limits_{k=1}^{n} a_{i, k} \cdot a_{k, j}$
wobei der Graph $n$ Knoten hat. Wenn du mit Matrixmultiplikation vertraut bist erkennst du diese in der obigen Summe wieder, wenn $\mathbf{A}$ also die Adjazenzmatrix ist dann zählt der Eintrag $(i, j)$ der Matrix $\mathbf{A}^{2}$ die Anzahl der Wege der Länge 2 von $i$ nach $j$. Man kann dann erkennen, dass der Eintrag $(i, j)$ der Matrix $\mathbf{A}^{r}$ die Anzahl der Wege der Länge $r$ von $i$ nach $j$ enthält. In deinem Fall musst du also $\mathbf{A}^{4}$ berechnen und dann den Eintrag $(1,3)$ ablesen.

Comments

Genau das hab ich gemacht, wäre hierfür die Lösung 441 denkbar? Oder ist das komplett außer Reichweite?

---

Für die Adjmatrix hab ich ->

0111

1001

1001

1110

rausbekommen.

---

Ja das ist nicht richtig, ich komme auf 9. Deine Adjazenzmatrix ist jedoch richtig

---

$\mathbf{A}^4 = \left(\begin{array}{rrrr}15 & 9 & 9 & 14 \\ 9 & 10 & 10 & 9 \\ 9 & 10 & 10 & 9 \\ 14 & 9 & 9 & 15\end{array}\right)$

---

Stimmt, danke hab A² * A² gerechnet und dabei gedacht ich bin bei A³