Strona 1 z 1
Ślad macierzy grafu
: 12 cze 2021, o 17:35
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.
Re: Ślad macierzy grafu
: 13 cze 2021, o 20:24
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