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{aligned}{\#\left({\text{ Weg von }}u{\text{ nach }}v{\text{ der Länge }}\ell +1\}\right)}&=\sum _{\{u,w\}\in E}{\#\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)}\\&={\left(A\cdot A^{\ell }\right)}_{(u,v)}\\&={\left(A^{\ell +1}\right)}_{(u,v)}\end{aligned}}$

Zur bewiesenen Aussage