Adjazenzmatrix/Potenzen/Interpretation/Fakt/Beweis

Beweis

Wir beweisen die Aussage durch Induktion über $\ell$, wobei der Induktionsanfang für  $\ell =1$  unmittelbar aus der Definition der Adjazenzmatrix folgt, da ja die Kanten die einzigen Wege der Länge $1$ sind (bei $\ell =0$ stimmt die Aussage ebenfalls, da es nur die konstanten kantenleeren Wege der Länge $0$ gibt und die $0$-te Potenz der Matrix als Einheitsmatrix zu interpretieren ist). Ein Weg der Länge $\ell +1$ von $u$ nach $v$ startet mit einer Kante $\{u,w\}$ gefolgt von einem Weg von $w$ nach $v$ der Länge $\ell$. Es gilt also unter Verwendung der Induktionsvoraussetzung

$\begin{array}{cc}\mathrm{\#}(\text{ Weg von }u\text{ nach }v\text{ der Länge }\ell +1)& =\sum _{\{u,w\}\in E}\mathrm{\#}\left(\text{ Weg von }w\text{ nach }v\text{ der Länge }\ell \right)\\ & =\sum _{\{u,w\}\in E}{\left(A^{\ell }\right)}_{(w,v)}\\ & =\sum _{w\in V}{A}_{(u,w)}{\left(A^{\ell }\right)}_{(w,v)}\\ & ={(A\cdot A^{\ell })}_{(u,v)}\\ & ={\left(A^{\ell +1}\right)}_{(u,v)}.\end{array}$

Zur bewiesenen Aussage