Macierz sąsiedztwa

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Macierz sąsiedztwa (multi)grafu macierz kwadratowa, w której oznacza liczbę krawędzi pomiędzy wierzchołkami i 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:

6n-graf.svg

macierz sąsiedztwa jest następująca:

Właściwości[edytuj | edytuj kod]

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 jest macierzą sąsiedztwa grafu skierowanego to macierz (-ta potęga macierzy ) ma następującą interpretację: oznacza liczbę ścieżek długości z wierzchołka do wierzchołka

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

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