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ą 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:

Plik:6n-graf.svg

macierz sąsiedztwa jest następująca:

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 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