Kreise der Länge 4 in einem Graphen

09.07.2013, 18:16	Yakmiras	Auf diesen Beitrag antworten »
Kreise der Länge 4 in einem Graphen Moin, es sei $\begin{eqnarray} G=(V,E) \end{eqnarray}$ ein Graph mit Adjazenzmatrix $\begin{eqnarray} A_G \end{eqnarray}$ . Zeigen Sie, dass die Anzahl der (unmarkierten) Kreise der Länge 4 in $\begin{eqnarray} G \end{eqnarray}$ genau $\begin{eqnarray} \frac{1}{8}\left(\text{Spur}\left(A_{G}^{4}\right)-2\left\|E\right\|-4\sum\limits _{v\in V}\binom{\deg_{G}(v)}{2}\right) \end{eqnarray}$ ist. Meine Idee bis jetzt: Ich weiß, dass der $\begin{eqnarray} i \end{eqnarray}$ -te Diagonaleintrag der vierten Potenz der Adjazenzmatrix mir die Anzahl der Wege der Länge 4 von $\begin{eqnarray} i \end{eqnarray}$ nach $\begin{eqnarray} i \end{eqnarray}$ gibt. Nun versuche ich also $\begin{eqnarray} v \in V \end{eqnarray}$ festzuhalten und von dem entsprechenden Diagonaleintrag alle Wege abzuziehen, die keine Kreise sind, so dass nur noch zwei übrig bleiben. Dann würde jeder Kreis acht mal gezählt werden und aufsummieren und anschließendes Teilen durch 8 würde mit dem Handshake-Lemma vielleicht zu etwas führen. Da gibt es aber direkt ein Problem. Halte ich $\begin{eqnarray} v \in V \end{eqnarray}$ fest, so erhalte ich z.B. $\begin{eqnarray} \left(A_{G}^{4}\right)_{ii}-\deg_{G}(v)-2\binom{\deg_{G}(v)}{2} \end{eqnarray}$ (Ich ziehe von der Gesamtanzahl den Eckengrad ab, da ich für jede Kante durch "Oszillieren" einen Weg der Länge 4 enthalte und anschließend zwei mal den obigen Binomialkoeffizienten, denn für je zwei Ecken bekomme ich ebenfalls zwei Wege der Länge 4.) Das Problem hierbei ist leider, dass ich offenbar zu wenig abziehe, denn enthält $\begin{eqnarray} G \end{eqnarray}$ z.B. einen Kreis $\begin{eqnarray} (1,2,3,4,1) \end{eqnarray}$ , so berücksichtige ich z.B. den Weg $\begin{eqnarray} (1,4,3,4,1) \end{eqnarray}$ nicht. Wenn ich allerdings vier mal den Binomialkoeffizienten abziehe, bekomme ich in anderen Fällen ein Problem, z.B. ergibt der Ausdruck dann für so etwas: [attach]30894[/attach] etwas negatives. Wie komme ich da raus? Kann man diesen Ansatz retten? Edit opi: Bild angehängt, Link entfernt. Bilder bitte immer direkt im Board hochladen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »