Laplace-Matrix

Die Laplace-Matrix ist in der Graphentheorie eine Matrix, welche die Beziehungen der Knoten und Kanten eines Graphen beschreibt. Sie wird unter anderem zur Berechnung der Anzahl der Spannbäume und zur Abschätzung der Expansivität regulärer Graphen benutzt. Sie ist eine diskrete Version des Laplace-Operators.

Laplace-Matrizen und insbesondere ihre zu kleinen Eigenwerten gehörenden Eigenvektoren werden beim Spectral Clustering, einem Verfahren der Clusteranalyse, verwendet.

DefinitionBearbeiten

Die Laplace-Matrix   eines Graphen mit der Knotenmenge   und der Kantenmenge   ist eine   Matrix. Sie ist definiert als  , wobei   die Gradmatrix und   die Adjazenzmatrix des Graphen bezeichnet. Der den Knoten   und   entsprechende Eintrag ist also

 

Insbesondere ist die Laplace-Matrix eines  -regulären Graphen

 

mit der Einheitsmatrix  .

BeispielBearbeiten

Nummerierung der Ecken Gradmatrix Adjazenzmatrix Laplace-Matrix
       

Zusammenhang mit InzidenzmatrixBearbeiten

Die Laplace-Matrix kann auch durch die Inzidenzmatrix berechnet werden. Sei   eine   Inzidenzmatrix, dann ist die Laplace-Matrix gegeben durch

 

EigenschaftenBearbeiten

Wir bezeichnen mit   die Eigenwerte der Laplace-Matrix, siehe Spektrum (Graphentheorie).

  •   ist symmetrisch.
  •   ist positiv-semidefinit, insbesondere also   für alle  .
  •   ist eine M-Matrix.
  • Die Spalten- und Zeilensummen sind Null. Insbesondere ist   mit Eigenvektor  .
  • Die Vielfachheit des Eigenwertes   ist die Anzahl der Zusammenhangskomponenten des Graphen.