Macierz sąsiedztwa
Z Wikipedii
W teorii grafów macierz sąsiedztwa (multi)grafu G jest kwadratową macierzą w której aij oznacza liczbę krawędzi pomiędzy wierzchołkami i i j. W przypadku grafów prostych macierz sąsiedztwa jest macierzą zerojedynkową z zerami na głównej przekątnej. Dla grafów nieskierowanych macierz sąsiedztwa jest z definicji symetryczna.
Dla przykładowego grafu o sześciu wierzchołkach oraz siedmiu krawędziach:
macierz sąsiedztwa jest następująca:
![A=\left[ \begin{matrix} 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{matrix}\right]](../../../math/9/a/4/9a41d53d4469034adf9e19d38a316a0f.png)
[edytuj] Właściwości
Macierz sąsiedztwa dla grafów nieskierowanych jest z definicji symetryczna. W szczególności oznacza to że ma wszystkie wartości własne rzeczywiste, i pełen zbiór ortogonalnych wektorów własnych. Zbiór wartości własnych tej macierzy określa się jako widmo grafu.
Izomorfizmowi grafów odpowiada permutacja macierzy sąsiedztwa. Oznacza to że grafy izomorficzne mają ten sam wielomian charakterystyczny, zbiór wartości własnych, wyznacznik, oraz ślad. Odwrotna zależność nie jest prawdziwa - grafy z takim samym wielomianem charakterystycznym nie muszą być izomorficzne.
Jeśli A jest macierzą sąsiedztwa grafu skierowanego G, to macierz An (n-ta potęga macierzy A) ma następującą interpretację: aij oznacza liczbę ścieżek długości n z wierzchołka i do wierzchołka j.
Dla grafów skierowanych macierz I − A (gdzie I oznacza macierz jednostkową) jest odwracalna wtedy i tylko wtedy gdy graf G nie zawiera cykli. W takim przypadku (I − A)−1 ma następującą interpretację: aij oznacza liczbę wszystkich ścieżek z wierzchołka i do wierzchołka j (przy braku cykli ta liczba jest skończona). Wynika to z rozwinięcia tej odwrotności w szereg geometryczny dla macierzy:
- (I − A)−1 = I + A + A2 + A3 + ...
odpowiadający sumowaniu liczby ścieżek długości 0, długości 1, 2 itd.
