Adjazenzmatrix

Endliche Graphen kann man wie folgt durch eine Matrix beschreiben: Es sei G=(V,E) ein Graph mit und Dabei bezeichne m(v_i,v_j) die Anzahl der Kanten von v_i nach Bei ungerichteten Graphen werden Schlingen doppelt gezählt; bei gerichteten Graphen zählt man Schlingen einfach. Die Matrix A vom Typ (n,n) mit A=(m(v_i,v_j)) wird Adjazenzmatrix genannt. Ist der Graph zusätzlich schlicht, dann hat die Adjazenzmatrix die folgende Gestalt:

D.h. in der Matrix A steht in der i-ten Zeile und j-ten Spalte genau dann eine 1, wenn eine Kante von v_i nach v_j verläuft.
Für ungerichtete Graphen ist die Adjazenzmatrix symmetrisch.

Beispiel A

Neben der Abbildung ist die Adjazenzmatrix A(G₁) des gerichteten Graphen G₁ gezeigt.

Beispiel B

Neben der Abbildung ist die Adjazenzmatrix A(G₂) des ungerichteten schlichten Graphen G₂ gezeigt.