Ungerichteter Graph/Adjazenzmatrix/Einführung/Textabschnitt

Definition

Zu einem Graphen ${}G=(V,E)$ versteht man unter der Adjazenzmatrix diejenige ${}V\times V$-Matrix, deren Einträge durch

${}a_{u,v}={\begin{cases}1,\,{\text{falls }}\{u,v\}\in E,\\0\,{\text{ sonst}},\end{cases}}\,$

gegeben sind.

Die Adjazenzmatrix ist eine quadratische Matrix, und zwar eine ${}V\times V$-Matrix. Es ist sinnvoll, hier Matrizen zu beliebigen endlichen Indexmengen zuzulassen. Wenn man allerdings die Matrix tabellarisch aufschreiben möchte, so muss man die Indexmenge (also die Knotenmenge) mit ${}1$ bis ${}n$ durchnummerieren und erhält dann eine ${}n\times n$-Matrix. Wie bei jeder quadratischen Matrix kann man von der Adjazenzmatrix ihre Determinante, ihr charakteristisches Polynom, ihre Eigenwerte bestimmen, man kann ihre Potenzen ausrechnen, u.s.w., und sich überlegen, was diese Strukturen der linearen Algebra für den Ausgangsgraphen bedeuten.

Beispiel

Zum vollständigen Graphen ${}K_{n}$ ist die Adjazenzmatrix gleich

${\begin{pmatrix}0&1&\ldots &1&1\\1&0&1&\ldots &1\\\vdots &\ddots &\ddots &\ddots &\vdots \\1&\ldots &1&0&1\\1&1&\ldots &1&0\end{pmatrix}}.$

Beispiel

Zu einem kantenfreien Graphen ist die Adjazenzmatrix die Nullmatrix.

Beispiel

Zum vollständigen bipartiten Graphen ${}K_{r,s}$ ist die Adjazenzmatrix eine Blockmatrix der Form

${\begin{pmatrix}0&\ldots &0&1&\ldots &1\\\vdots &\ddots &\vdots &\vdots &\ddots &\vdots \\0&\ldots &0&1&\ldots &1\\1&\ldots &1&0&\ldots &0\\\vdots &\ddots &\vdots &\vdots &\ddots &\vdots \\1&\ldots &1&0&\ldots &0\end{pmatrix}},$

wobei die Blöcke aber nicht quadratisch sein müssen.

Lemma

Die Adjazenzmatrix ${}A$ eines Graphen ${}G=(V,E)$ besitzt die folgenden Eigenschaften.

1. Für Knotenpunkte ${}u,v\in V$ ist

   ${}{e_{u}^{\text{tr}}}Ae_{v}={\begin{cases}1,{\text{wenn }}\{u,v\}\in E\,,\\0{\text{ sonst}}\,.\end{cases}}\,$

2. ${}A$ ist symmetrisch.
3. Die Diagonaleinträge von ${}A$ sind ${}0$.
4. Der Knotengrad zum Punkt ${}v\in V$ ist die Summe der Einträge der ${}v$-ten Zeile (oder Spalte) von ${}A$.

Beweis

Diese Aussagen folgen alle unmittelbar aus der Definition der Adjazenzmatrix und dem Matrizenkalkül.

$\Box$