Ślad macierzy grafu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Ślad macierzy grafu

Post autor: mol_ksiazkowy »

Udowodnić, że w grafie prostym \(\displaystyle{ 6c = tr(A^3)}\), gdzie \(\displaystyle{ c}\) jest liczbą trójkątów (\(\displaystyle{ 3}\) cykli) w grafie, zaś \(\displaystyle{ A}\) jest macierzą sąsiedztwa grafu.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Ślad macierzy grafu

Post autor: arek1357 »

No tak tu możemy posłużyć się grafem prostym przerobionym na graf skierowany w którym każda krawędź ma dwa kierunki i nie ma pętelek...

Oczywiście elementy macierzy \(\displaystyle{ a_{i,j}, A^3}\) to ilość dróg od wierzchołka \(\displaystyle{ i}\) do wierzchołka \(\displaystyle{ j}\) o długości trzy...

Co oznacza, że ilość dróg o długości trzy od wierzchołka i do i to elementy na głównej przekątnej a więc ślad macierzy...

Oczywiście każdy taki trójkąt zawiera trzy wierzchołki a ścieżki to nie do końca trójkąty bo w takim trójkącie jest \(\displaystyle{ 6}\) ścieżek

Od każdego punktu jest dwie ścieżki: lewo, prawo,

Punktów jest trzy więc: \(\displaystyle{ 3 \cdot 2=6}\) tyle jest więc w trójkącie ścieżek więc dlatego dzielimy przez sześć bo nas interesują nie ścieżki a trójkąty więc teraz już jest oczywiste, że:

\(\displaystyle{ 6c=tr\left( A^3\right) }\)

gdzie:

\(\displaystyle{ c}\) - ilość trójkątów
ODPOWIEDZ