Zum Inhalt springen

Laplace-Matrix

aus Wikipedia, der freien Enzyklopädie

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.

Die Laplace-Matrix L eines Graphen mit der Knotenmenge V und der Kantenmenge E ist eine |V|×|V| Matrix. Sie ist definiert als L:=D−A, wobei D die Gradmatrix und A die Adjazenzmatrix des Graphen bezeichnet. Der den Knoten vi und vj entsprechende Eintrag ist also

Li,j:={deg⁡(vi)falls i=j−1falls i≠j und vi adjazent zu vj0sonst.

Die Grad-Matrix ist eine Diagonalmatrix und hat im Eintrag Di,i die Zahl der Kanten, welche im Knoten i enden.

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

L=d⋅I−A

mit der Einheitsmatrix I.

Nummerierung der Ecken Gradmatrix Adjazenzmatrix Laplace-Matrix
Skizze (200000030000002000000300000030000001) (010010101010010100001011110100000100) (2−100−10−13−10−100−12−10000−13−1−1−1−10−130000−101)

Zusammenhang mit Inzidenzmatrix

[Bearbeiten | Quelltext bearbeiten]

Die Laplace-Matrix kann auch durch die Inzidenzmatrix berechnet werden. Sei B eine |E|×|V| Inzidenzmatrix, dann ist die Laplace-Matrix gegeben durch

L=BB⊤.

Wir bezeichnen mit λ0≤λ1≤⋯≤λn−1 die Eigenwerte der Laplace-Matrix, siehe Spektrum (Graphentheorie).