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 Spannbaume und zur Abschatzung der Expansivitat regularer Graphen benutzt Sie ist eine diskrete Version des Laplace Operators Laplace Matrizen und insbesondere ihre zu kleinen Eigenwerten gehorenden Eigenvektoren werden beim Spectral Clustering einem Verfahren der Clusteranalyse verwendet Inhaltsverzeichnis 1 Definition 2 Beispiel 3 Zusammenhang mit Inzidenzmatrix 4 EigenschaftenDefinition BearbeitenDie Laplace Matrix L displaystyle L nbsp eines Graphen mit der Knotenmenge V displaystyle V nbsp und der Kantenmenge E displaystyle E nbsp ist eine V V displaystyle V times V nbsp Matrix Sie ist definiert als L D A displaystyle L D A nbsp wobei D displaystyle D nbsp die Gradmatrix und A displaystyle A nbsp die Adjazenzmatrix des Graphen bezeichnet Der den Knoten v i displaystyle v i nbsp und v j displaystyle v j nbsp entsprechende Eintrag ist also L i j deg v i falls i j 1 falls i j und v i adjazent zu v j 0 sonst displaystyle L i j begin cases deg v i amp mbox falls i j 1 amp mbox falls i neq j mbox und v i mbox adjazent zu v j 0 amp mbox sonst end cases nbsp Die Grad Matrix ist eine Diagonalmatrix und hat im Eintrag D i i displaystyle D i i nbsp die Zahl der Kanten welche im Knoten i displaystyle i nbsp enden Insbesondere ist die Laplace Matrix eines d displaystyle d nbsp regularen Graphen L d I A displaystyle L d cdot I A nbsp mit der Einheitsmatrix I displaystyle I nbsp Beispiel BearbeitenNummerierung der Ecken Gradmatrix Adjazenzmatrix Laplace Matrix nbsp 2 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 1 displaystyle left begin array rrrrrr 2 amp 0 amp 0 amp 0 amp 0 amp 0 0 amp 3 amp 0 amp 0 amp 0 amp 0 0 amp 0 amp 2 amp 0 amp 0 amp 0 0 amp 0 amp 0 amp 3 amp 0 amp 0 0 amp 0 amp 0 amp 0 amp 3 amp 0 0 amp 0 amp 0 amp 0 amp 0 amp 1 end array right nbsp 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 displaystyle left begin array rrrrrr 0 amp 1 amp 0 amp 0 amp 1 amp 0 1 amp 0 amp 1 amp 0 amp 1 amp 0 0 amp 1 amp 0 amp 1 amp 0 amp 0 0 amp 0 amp 1 amp 0 amp 1 amp 1 1 amp 1 amp 0 amp 1 amp 0 amp 0 0 amp 0 amp 0 amp 1 amp 0 amp 0 end array right nbsp 2 1 0 0 1 0 1 3 1 0 1 0 0 1 2 1 0 0 0 0 1 3 1 1 1 1 0 1 3 0 0 0 0 1 0 1 displaystyle left begin array rrrrrr 2 amp 1 amp 0 amp 0 amp 1 amp 0 1 amp 3 amp 1 amp 0 amp 1 amp 0 0 amp 1 amp 2 amp 1 amp 0 amp 0 0 amp 0 amp 1 amp 3 amp 1 amp 1 1 amp 1 amp 0 amp 1 amp 3 amp 0 0 amp 0 amp 0 amp 1 amp 0 amp 1 end array right nbsp Zusammenhang mit Inzidenzmatrix BearbeitenDie Laplace Matrix kann auch durch die Inzidenzmatrix berechnet werden Sei B displaystyle B nbsp eine E V displaystyle E times V nbsp Inzidenzmatrix dann ist die Laplace Matrix gegeben durch L B B displaystyle L BB top nbsp Eigenschaften BearbeitenWir bezeichnen mit l 0 l 1 l n 1 displaystyle lambda 0 leq lambda 1 leq cdots leq lambda n 1 nbsp die Eigenwerte der Laplace Matrix siehe Spektrum Graphentheorie L displaystyle L nbsp ist symmetrisch L displaystyle L nbsp ist positiv semidefinit insbesondere also l i 0 displaystyle lambda i geq 0 nbsp fur alle i displaystyle i nbsp L displaystyle L nbsp ist eine M Matrix Die Spalten und Zeilensummen sind Null Insbesondere ist l 0 0 displaystyle lambda 0 0 nbsp mit Eigenvektor v 0 1 1 1 displaystyle mathbf v 0 1 1 dots 1 nbsp Die Vielfachheit des Eigenwertes 0 displaystyle 0 nbsp ist die Anzahl der Zusammenhangskomponenten des Graphen Abgerufen von https de wikipedia org w index php title Laplace Matrix amp oldid 237255983
