Ungerichteter Graph/Adjazenzmatrix/Einführung/Textabschnitt

Aus Wikiversity


Definition  

Zu einem Graphen versteht man unter der Adjazenzmatrix diejenige -Matrix, deren Einträge durch

gegeben sind.

Die Adjazenzmatrix ist eine quadratische Matrix, und zwar eine -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 bis durchnummerieren und erhält dann eine -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 ist die Adjazenzmatrix gleich



Beispiel  

Zu einem kantenfreien Graphen ist die Adjazenzmatrix die Nullmatrix.



Beispiel  

Zum vollständigen bipartiten Graphen ist die Adjazenzmatrix eine Blockmatrix der Form

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




Lemma  

Die Adjazenzmatrix eines Graphen besitzt die folgenden Eigenschaften.

  1. Für Knotenpunkte ist
  2. ist symmetrisch.
  3. Die Diagonaleinträge von sind .
  4. Der Knotengrad zum Punkt ist die Summe der Einträge der -ten Zeile (oder Spalte) von .

Beweis  

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