Also was du wahrscheinlich in der Vorlesung gesehen haben solltest, ist, dass
\( \text{Anzahl Wege von \( v_{ i} \) nach \( v_{ j} \) der Länge \( k \)} = ( A^{ k})_{ ij} .\)
Damit kannst du dann a) direkt lösen. Hier noch wichtig: Es sind nicht notwendigerweise Kreise, denn ein Weg der Länge \( 4 \)
ist z.B. \( \{a, b, a, b, a \} \), und das ist natürlich nicht ein Kreis der Länge \( 4 \), da bei Kreisen
lediglich der Anfangsknoten doppelt vorkommen darf.
b) Das ein Weg der Länge \( 4 \) nicht automatisch ein Kreis der Länge \( 4 \) ist, führt hier also zu einem Korrektionsterm.
\( \text{Spur}( A^{ 4}) \) gibt die die Anzahl der Wege der Länge \( 4 \) an, welche beim gleichen Knoten anfangen und enden. Jetzt müssen
wir aber erstmal noch die Wege der Form \( \{ a, b, c, d, a\} \) wegsubtrahieren mit \( c = a \) oder \( d = b \) oder beidem, damit wir auch wirklich nur echte Kreise zählen.
(1) Wenn \( c = a \) und \( d \neq b \) ist, dann haben wir für \( b \) genau \( \text{deg}( a) \) Möglichkeiten und für
\( c \) genau \( \text{deg}( a) - 1 \).
(2) Wenn \( c \neq a \) und \( d = b \) ist, dann haben wir für \( b \) genau \( \text{deg}( a) \) Möglichkeiten und für
\( c \) genau \( \text{deg}( b) - 1 \).
(3) Wenn \( c = a \) und \( d = b \) ist, dann gibt es genau \( \text{deg}( a) \) Möglichkeiten.
Jetzt musst du das noch über alle Knoten des Graphen summieren, also (hier bezeichne \( N( v) \) alle benachbarten Knoten von \( v \)
und \( \mathbf{1}_{ X} ( y) = 1 \) genau dann wenn \( y \in X \), also die Indikatorfunktion der Menge \( X \)).
(1)
\(\begin{aligned} \sum_{ a \in V} \text{deg}( a) ( \text{deg}( a) - 1) . \end{aligned}\)
(2)
\(\begin{aligned} \sum_{ a \in V} \sum_{ b \in N( a) } ( \text{deg}( b) - 1) &= \sum_{ a \in V}\sum_{ b \in V} ( \text{deg}( b) - 1) \mathbf{1}_{ N( a) } ( b) \\ &= \sum_{ b \in V}( \text{deg}( b) - 1) \sum_{ a \in V} \mathbf{1}_{ N( a) } ( b) \\ &= \sum_{ b \in V} \text{deg}( b) ( \text{deg}( b) - 1) . \end{aligned}\)
(3)
\(\begin{aligned} \sum_{ a \in A} \text{deg}( a) = 2|E|. \end{aligned}\)
Alle obigen Terme zusammenaddiert müssen wir also von \( \text{Spur}( A^{ 4}) \) abziehen. Das ist aber noch nicht genug, denn
jetzt zählen wir zwar nur noch echte Kreise, aber wir zählen manche doppelt: Z.b. zählen wir
\( \{ a, b, c, d, a\} \) und \( \{ a, d, c, b, a\} \) als verschiedene Kreise, es jedoch die gleichen. Also schonmal durch \( 2 \) dividieren. Letztlich
zählen wir \( \{ a, b, c, d, a\}, \{ b, c, d, a, b\}, \{ c, d, a, b, c\} \) und \( \{ d, a, b, c, d\} \) als verschiedene Kreise,
also nochmal durch \( 4 \) dividieren. Wir kommen also auf
\(\begin{aligned} \frac{1}{ 8} ( \text{Spur}( A^{ 4})- 2|E|- 2 \sum_{ v \in V} \text{deg}( v) ( \text{deg}( v) - 1) ) \end{aligned}\)
(ich habe den Binomialköffizienten ausgeschrieben).
