Zeigen Sie, dass die Anzahl der (nicht notwendigerweise induzierten) Kreise der Länge 4 in G gleich

Question

Hallo liebe Community :) Ich habe ein Problem mit der folgenden Aufgabe:

Die Spur einer (n x n)-Matrix

$$A=\begin{pmatrix} a_{11} & a_{12} & ... & a_{1n} \\ a_{21}& a_{22} & ... & a_{2n} \\ ... &... & ... & ... \\ a_{n1} & a_{n2} & ... & a_{nn}\end{pmatrix}$$

ist definiert als die Summe der Hauptdiagonaleinträge, d.h.

$$Spur(A)=\sum \limits_{k=1}^{n}a_{kk}$$.

Sei G=(V,E) ein Graph und A seine Adjanzenzmatrix.

a) Welche Arten von Spaziergängen der Länge 4 in G gibt es, die bei einem Knoten v beginnen und auch bei diesem wieder enden?

b) Zeigen Sie, dass die Anzahl der (nicht notwendigerweise induzierten) Kreise der Länge 4 in G gleich

$$\frac{1}{8}(Spur(A^4)-2|E|-4\sum \limits_{vεV}^{}\begin{pmatrix} deg(v)\\2 \end{pmatrix})$$

ist.

Zu a): Ich glaube, ich verstehe schon allein die Frage nicht richtig. Es muss auf jeden Fall ein Kreis sein, der bis zu 3 Nachbarknoten einschließt. Es ist natürlich auch ein Kreis mit nur einem Nachbarknoten möglich; dann geht es halt hin her hin her.

Zu b): Hier habe ich leider keinen Ansatz. deg beschreibt den Knotengrad des Knotens.

Ich bin um jede Hilfe dankbar!

LG Nunu

Answer 1

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).

Comments

WOW, vielen lieben Dank für die Erklärungen! Jetzt ergibt das einen Sinn!