Ślad macierzy grafu
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Ślad macierzy grafu
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.
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Ślad macierzy grafu
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
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