13.3 Die Adjazenzmatrix eines Graphen

Problemstellung Was ist eine gute Methode, um in einem gegebenen Graphen alle Wege einer fixierten Länge zu zählen? Wir werden dieses Problem mithilfe des Matrizenprodukts »lösen«. Je nachdem, wie groß der Graph ist, ist die Rechnung eventuell nicht ohne Weiteres durchführbar. Den Matrizenkalkül ins Spiel zu bringen ist aber jedenfalls eine Verbesserung.

Wir stellen durch die folgende Definition eine Verbindung zur linearen Algebra her, die zwar recht banal aussieht, aber dennoch sehr nützlich ist.

Definition 13.9

Sei $G = (\mathbb E, \mathbb K)$ ein Graph. Wir fixieren eine Identifizierung $\mathbb E = \{ 1,\dots , n\} $. Die Adjazenzmatrix (oder Nachbarschaftsmatrix) von $G$ ist die Matrix $A = (a_{ij})\in M_{n\times n}(\mathbb Q)$ mit

\[ a_{ij} = \begin{cases} 1 & i,j\ \text{sind durch eine Kante verbunden,}\\ 0 & \text{sonst.} \end{cases} \]

Beispiel 13.10

Die Adjazenzmatrix des Graphen in der nebenstehenden Abbildung ist

\[ \left( \begin{array}{cccccc} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{array} \right). \]
Die Adjazenzmatrix von $K_n$ ist die Matrix, deren Diagonaleinträge $0$ und deren andere Einträge alle $1$ sind.

$\includegraphics[width=4.9cm]{figures/graph2}$

Interessanterweise haben auch die Potenzen der Adjazenzmatrix eine graphentheoretische Interpretation. Sei $G$ ein Graph mit Eckenmenge $\{ 1, \dots , n\} $ und Adjazenzmatrix $A$. Ein Produkt der Form $a_{ij}a_{jk}$ ist genau dann $1$, wenn in $G$ ein »Weg« $i - j - k$ existiert, d.h. wenn sowohl $i$ und $j$ als auch $j$ und $k$ miteinander verbunden sind. Wir definieren

Definition 13.11

Sei $G$ ein Graph. Ein Weg (oder Pfad) in $G$ ist ein Tupel $(e_0, \dots , e_l)$ von Ecken in $G$, so dass für alle $i$ die Ecken $e_i$ und $e_{i+1}$ durch eine Kante verbunden sind. Wir sprechen auch von einem Weg von $e_0$ nach $e_l$.

Die Zahl $l$ heißt die Länge des Wegs.

Dann ist $\sum _{j=1}^n a_{ij}a_{jk}$ gerade die Anzahl der Wege der Länge $2$ von $i$ nach $k$.

Satz 13.12

Sei $G$ ein Graph mit Eckenmenge $\{ 1, \dots , n\} $ und Adjazenzmatrix $A$. Sei $l$ eine natürliche Zahl. Sei $B = (b_{ij})_{i,j} = A^l$. Dann ist $b_{ij}$ die Anzahl der Wege der Länge $l$ von $i$ nach $j$ in $G$.

Beweis

Wir führen Induktion nach $l$. Für $l = 1$ ist die Sache klar. (Und auch für $l=0$, wenn man möchte: Ein Weg der Länge $0$ ist nichts anderes als eine Ecke in $G$.)

Sei nun $l {\gt} 1$, und sei $B=(b_{ij})_{i,j} = A^{l-1}$. Ein Weg der Länge $l$ von $i$ nach $k$ lässt sich zerlegen als ein Weg von $i$ zu einer Ecke $j$ der Länge $l-1$ und dem letzten Schritt des Weges von $j$ nach $k$, d.h. $j$ muss mit $k$ benachbart sein. Die Anzahl der Wege der Länge $l$ ist daher die Summe aller $b_{ij}$ für diejenigen $j$, die mit $k$ benachbart sind – also die Summe $\sum _{j=1}^n b_{ij}a_{jk}$, und das ist gerade der Eintrag von $A^l$ an der Stelle $(i,j)$.

Wir können also Matrizenrechnung benutzen, um die Anzahl der Wege einer vorgegebenen Länge zwischen zwei Knoten in einem Graphen zu berechnen. Um zum Beispiel alle Wege der Länge $16$ zu zählen, muss man für die Adjazenzmatrix $A$ die $16$-te Potenz ausrechnen. Ähnlich wie in Beispiel 5.60 kann man das mit $4$ Matrixmultiplikationen machen ($A^2 = AA$, $A^4 = A^2A^2$, …). Das ist wesentlich effizienter, als direkt im Graphen »herumzuprobieren«.

Bemerkung 13.13

Offenbar ist ein Graph durch seine Adjazenzmatrix (bis auf Isomorphie, also bis auf die Benennung der Ecken) eindeutig bestimmt. Überlegen Sie sich zur Übung, welche Matrizen als Adjazenzmatrix eines Graphen auftreten.

Andererseits ist die Adjazenzmatrix eines Graphen erst dann eindeutig festgelegt, wenn wir eine Nummerierung der Ecken fixieren, denn wir müssen ja wissen, auf welche Ecke sich die Einträge der ersten Zeile beziehen, usw. Wenn wir die Ecken anders nummerieren, erhalten wir in aller Regel eine andere Matrix. Es ist aber leicht zu sehen, wie sich die beiden Matrizen voneinander unterscheiden: Wir müssen die Zeilen und die Spalten der ersten Matrix so vertauschen, wie es der Umnummerierung der Ecken entspricht. Das bedeutet, dass die Matrizen durch Konjugation mit einer Permutationsmatrix auseinander hervorgehen.

Das gleiche Argument können wir benutzen, um zu sehen, dass die Adjazenzmatrizen von zwei isomorphen Graphen zueinander konjugiert sind. Daraus ergibt sich eine Möglichkeit, um zu zeigen, dass zwei Graphen nicht isomorph sind: Nämlich zu zeigen, dass die zugehörigen Adjazenzmatrizen nicht zueinander konjugiert sind (zum Beispiel, weil sie nicht dieselben Eigenwerte haben).

Lineare Algebra I, WS 2020/21

Inhalt

13.3 Die Adjazenzmatrix eines Graphen