liczba cykli długości 4 w grafie G

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
JakubCh
Użytkownik
Użytkownik
Posty: 613
Rejestracja: 18 gru 2011, o 11:41
Płeć: Mężczyzna
Lokalizacja: Rzeszów/Kraków
Podziękował: 265 razy
Pomógł: 5 razy

liczba cykli długości 4 w grafie G

Post autor: JakubCh »

Udowodnić, że jest to wzór na liczbę cykli długości \(\displaystyle{ 4}\) w grafie \(\displaystyle{ G}\):
\(\displaystyle{ \frac{1}{8}\left( trA ^{4} _{G} - 2 \# E\left( G\right) - 4 \sum_{v \in V\left( G\right) } {deg _{G} \left( v\right) \choose 2} \right)}\)
ODPOWIEDZ