0 Daumen
2,7k Aufrufe

Beweise:

Sei \(G\) ein Graph und \(A\) seine Adjazenzmatrix.

Dann ist die Anzahl der Wege von Knoten \(u\) nach \(v\) der Länge \(k\) gleich gleich dem Eintrag \((u,v)\) in \(A^k\).


Problem/Ansatz:

Ich gehe davon aus dass man das über vollständige Induktion über alle \(k\) macht. Nur weiß ich leider nichtmal wie man anfängt.


Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

Der Einfachheit halber werden hier Gedanken zum Beweis für einfache Graphen (d.h. ohne Schleifen und Mehrfachkanten) mit n Knoten notiert, die Knoten werden von 1 bis n durchnummeriert.

Sei \(G=(V,E)\) ein Graph mit Knotenmenge \(V=\{1,2,...,n\}\) und zugehöriger Kantenmenge \(E\). Die \(n\times n\)- Adjazenzmatrix \(A=(a_{ij})\) mit $$a_{ij}=\begin{cases} 1, \ (i,j)\in E \\ 0, \ (i,j)\notin E \end{cases}$$ beschreibt nun die Adjazenz der Knoten \(i\) und \(j\).

Induktionsanfang. \(k=1\): Es existiert ein Weg der Länge \(1\) zwischen \(i\) und \(j\)  \(\Leftrightarrow\) \(\{i,j\}\in E\), bzw., \((i,j)\in E \) \(\Leftrightarrow a_{ij}=1\) als Eintrag von \(A^1=A\). Ansonsten gilt \(a_{ij}=0\) nach Definition der Adjazenzmatrix.

Induktionshypothese. Sei \(k\in \mathbb{N}\) fest und \(B=A^k\) mit \(B=(b_{ij})\). Dann entspricht \(b_{ij}\) der Anzahl der Wege der Länge \(k\) vom Knoten \(i\) zum Knoten \(j\).

Induktionsschritt. \(k\rightarrow k+1\). Sei \(A^{k+1} = (a_{ij}^{'})\) mit \(a_{ij}^{'}=\sum\limits_{r=1}^n a_{ir} \cdot b_{rj}\), wobei \(A^k=B=(b_{ij})\).

Angenommen \(a_{ir}=0\). Dann gilt \(\{i,r\}\notin E\), bzw., \((i,r)\notin E \), also gibt es keine Kante von \(i\) zu einem Zwischenknoten \(r\). Offenbar kann es nun auch keinen Weg von \(i\) nach \(j\) über \(r\) geben, da bereits keine Verbindung von \(i\) zu \(r\) besteht.

Angenommen \(a_{ir}=1\). Dann gilt \(\{i,r\}\in E\), bzw., \((i,r)\in E \), also gibt es eine Kante von \(i\) zu einem Zwischenknoten \(r\).

Nach Induktionshypothese gibt \(b_{rj}\) nun die Anzahl der Wege von \(r\) nach \(j\) der Länge \(k\) an. Mit der Kante \(\{i,r\}\), bzw., \((i,r)\) können die Wege von \(r\) nach \(j\) auf Wege von \(i\) nach \(j\) der Länge \(k+1\) erweitert werden.

Das ergibt also wieder \(b_{rj}\)-Wege. Mit der Summeniteration werden also nun alle Knoten einzeln als Zwischenknoten geprüft. Damit gibt \(a_{ij}^{'}\) die Anzahl der Wege der Länge \(k+1\) vom Knoten \(i\) zum Knoten \(j\) an.

Avatar von 2,9 k

Es sollte noch bedacht werden, dass dein Beweis auch für Graphen (auch für gerichtete!) funktioniert, welche Mehrfachkanten oder mit Schleifen enthalten, was aus deiner Fallunterscheidung im Induktionsschritt hervorgeht.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community