Eine zweidimensionale Darstellung eines endlichen Graphen, wobei der Eintrag (i,j) das Vorhandensein und gegebenenfalls das Gewicht einer Kante zwischen Knoten i und Knoten j angibt.

Prinzip

Diskrete Konnektivität in ein linearalgebraisches Objekt kodieren, sodass Graphoperationen als Matrixoperationen formuliert werden können.

Demonstration

Für einen ungerichteten einfachen Graphen mit Knoten {1,2,3,4} und Kanten {1–2,2–3,3–4} hat die Adjazenzmatrix A Nullen auf der Diagonale und Einsen an den Positionen (1,2),(2,1),(2,3),(3,2),(3,4),(4,3).

Fehlanwendung

Die gleiche Adjazenzmatrix ohne Anpassung zur Beschreibung eines Multigraphen zu verwenden, führt zum Verlust der Information über Kantenvielfachheit.

Konsequenz

Ermöglicht den Einsatz der Matrizenalgebra (Potenzbildung, Produkte, Indizes) zur Untersuchung von Wegen, Zusammenhang und kombinatorischen Eigenschaften des Graphen.

Umkehrung

Eine Inzidenzmatrix erfasst Knoten–Kanten-Inzidenzen statt direkter Knoten–Knoten-Verbindungen und verlagert damit den Fokus von Adjazenz zu Kantenmitgliedschaft.

Abgrenzung

Definiert für endliche Graphen; bei Hypergraphen, mehrschichtigen Netzwerken oder beschrifteten Kanten muss die einfache binäre Adjazenz erweitert oder ersetzt werden.

Semantische Spannung

Im Gegensatz zur gewichteten Adjazenz: Die unqualifizierte Adjazenzmatrix impliziert oft binäre Einträge, während viele Auswertungen reale Gewichtungen voraussetzen.

Synthese

Eine kompakte Matrix, deren Eintragsmuster eine direkte linearalgebraische Kodierung dessen darstellt, welche Knoten in einem endlichen Graphen verbunden sind und wie stark.