Macierz sąsiedztwa

Macierz sąsiedztwa (multi)grafu ${\displaystyle G}$ – macierz kwadratowa, w której ${\displaystyle a_{ij}}$ oznacza liczbę krawędzi pomiędzy wierzchołkami ${\displaystyle i}$ i ${\displaystyle j}$^[1]. W przypadku grafów prostych macierz sąsiedztwa jest macierzą zero-jedynkową 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:

${\displaystyle A={\begin{bmatrix}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{bmatrix}}.}$

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łny 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 ${\displaystyle A}$ jest macierzą sąsiedztwa grafu skierowanego ${\displaystyle G,}$ to macierz ${\displaystyle A^{n}}$ (${\displaystyle n}$-ta potęga macierzy ${\displaystyle A}$) ma następującą interpretację: ${\displaystyle a_{ij}}$ oznacza liczbę ścieżek długości ${\displaystyle n}$ z wierzchołka ${\displaystyle i}$ do wierzchołka ${\displaystyle j.}$

Dla grafów skierowanych macierz ${\displaystyle I-A}$ (gdzie ${\displaystyle I}$ oznacza macierz jednostkową) jest odwracalna wtedy i tylko wtedy, gdy graf ${\displaystyle G}$ nie zawiera cykli. W takim przypadku ${\displaystyle (I-A)^{-1}}$ ma następującą interpretację: ${\displaystyle a_{ij}}$ oznacza liczbę wszystkich ścieżek z wierzchołka ${\displaystyle i}$ do wierzchołka ${\displaystyle j}$ (przy braku cykli ta liczba jest skończona). Wynika to z rozwinięcia tej odwrotności w szereg geometryczny dla macierzy:

${\displaystyle (I-A)^{-1}=I+A+A^{2}+A^{3}+\dots }$

odpowiadający sumowaniu liczby ścieżek długości 0, długości 1, 2 itd.

Przypisy