Sei G = (V, E) ein Graph über der Knotenmenge V = {1, . . . , n} mit Kantenrelation E ⊆ V × V. Die
Adjazenzmatrix A = (ai j)
n
i,j=1
von G ist ist wie folgt definiert
ai j =
¨
1, wenn (i, j) ∈ E
0, sonst
.
Zeigen Sie, dass
α(m)i j = pm(i, j)
für alle m ∈ N und i, j = 1, . . . , n, wobei
A
m = (α(m)i j)
n
i,j=1
und pm(i, j) = “die Anzahl der Pfade von i nach j der Länge m”.
Bemerkung: Ein Pfad der Länge n von u ∈ V nach w ∈ V ist eine Folge (vi
)
n
i=0
von Knoten in G, sodass
v0 = u, vn = w und (vi
, vi+1
) ∈ E für i = 0, . . . , n − 1
