Laplace-Matrix

Die Laplace-Matrix ${\displaystyle L}$  eines Graphen mit der Knotenmenge ${\displaystyle V}$  und der Kantenmenge ${\displaystyle E}$  ist eine ${\displaystyle |V|\times |V|}$  Matrix. Sie ist definiert als ${\displaystyle L:=D-A}$ , wobei ${\displaystyle D}$  die Gradmatrix und ${\displaystyle A}$  die Adjazenzmatrix des Graphen bezeichnet. Der den Knoten ${\displaystyle v_{i}}$  und ${\displaystyle v_{j}}$  entsprechende Eintrag ist also

${\displaystyle L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{falls}}\ i=j\\-1&{\mbox{falls}}\ i\neq j\ {\mbox{und}}\ v_{i}{\mbox{ adjazent zu }}v_{j}\\0&{\mbox{sonst}}\end{cases}}}$ .

Die Grad-Matrix ist eine Diagonalmatrix und hat im Eintrag ${\displaystyle D_{i,i}}$  die Zahl der Kanten, welche im Knoten ${\displaystyle i}$  enden.

Insbesondere ist die Laplace-Matrix eines ${\displaystyle d}$ -regulären Graphen

${\displaystyle L=d\cdot I-A}$ 

mit der Einheitsmatrix ${\displaystyle I}$ .

Die Laplace-Matrix kann auch durch die Inzidenzmatrix berechnet werden. Sei ${\displaystyle B}$  eine ${\displaystyle |E|\times |V|}$  Inzidenzmatrix, dann ist die Laplace-Matrix gegeben durch

${\displaystyle L=BB^{\top }}$ .

Wir bezeichnen mit ${\displaystyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}$  die Eigenwerte der Laplace-Matrix, siehe Spektrum (Graphentheorie).

• ${\displaystyle L}$  ist symmetrisch.
• ${\displaystyle L}$  ist positiv-semidefinit, insbesondere also ${\displaystyle \lambda _{i}\geq 0}$  für alle ${\displaystyle i}$ .
• ${\displaystyle L}$  ist eine M-Matrix.
• Die Spalten- und Zeilensummen sind Null. Insbesondere ist ${\displaystyle \lambda _{0}=0}$  mit Eigenvektor ${\displaystyle \mathbf {v} _{0}=(1,1,\dots ,1)}$ .
• Die Vielfachheit des Eigenwertes ${\displaystyle 0}$  ist die Anzahl der Zusammenhangskomponenten des Graphen.