In der Graphentheorie wird die Laplace-Matrix 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.
Definition
Die Laplace-Matrix eines Graphen ist definiert als , wobei die Gradmatrix und die Adjazenzmatrix des Graphen bezeichnet. Der den Ecken und entsprechende Eintrag ist also
- Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle L_{i,j}:= \begin{cases} \deg(e_i) & \mbox{falls}\ i = j \\ -1 & \mbox{falls}\ i \neq j\ \mbox{und}\ e_i \mbox{ adjazent zu } e_j \\ 0 & \mbox{sonst} \end{cases} }
Insbesondere ist die Laplace-Matrix eines -regulären Graphen
- .
Beispiel
| Numerierung der Ecken | d.Id | Adjazenzmatrix | Laplace-Matrix |
|---|---|---|---|
Eigenschaften
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.