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.
Definition
Die Laplace-Matrix
L
{\displaystyle L}
eines Graphen mit der Knotenmenge
V
{\displaystyle V}
und der Kantenmenge
E
{\displaystyle E}
ist eine
|
V
|
×
|
V
|
{\displaystyle |V|\times |V|}
Matrix. Sie ist definiert als
L
:=
D
−
A
{\displaystyle L:=D-A}
, wobei
D
{\displaystyle D}
die Gradmatrix und
A
{\displaystyle A}
die Adjazenzmatrix des Graphen bezeichnet.
Der den Knoten
v
i
{\displaystyle v_{i}}
und
v
j
{\displaystyle v_{j}}
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})&{\mbox{falls}}\ i=j\\-1&{\mbox{falls}}\ i\neq j\ {\mbox{und}}\ v_{i}{\mbox{ adjazent zu }}v_{j}\\0&{\mbox{sonst}}\end{cases}}}
Insbesondere ist die Laplace-Matrix eines
d
{\displaystyle d}
-regulären Graphen
L
=
d
⋅
I
−
A
{\displaystyle L=d\cdot I-A}
mit der Einheitsmatrix
I
{\displaystyle I}
.
Beispiel
Nummerierung der Ecken
Gradmatrix
Adjazenzmatrix
Laplace-Matrix
(
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&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\\\end{array}}\right)}
(
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&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\\\end{array}}\right)}
(
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&-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\\\end{array}}\right)}
Zusammenhang mit Inzidenzmatrix
Die Laplace-Matrix kann auch durch die Inzidenzmatrix berechnet werden. Sei
B
{\displaystyle B}
eine
|
E
|
×
|
V
|
{\displaystyle |E|\times |V|}
Inzidenzmatrix, dann ist die Laplace-Matrix gegeben durch
L
=
B
⊤
B
{\displaystyle L=B^{\top }B}
Eigenschaften
Wir bezeichnen mit
λ
0
≤
λ
1
≤
⋯
≤
λ
n
−
1
{\displaystyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}
die Eigenwerte der Laplace-Matrix, siehe Spektrum (Graphentheorie) .
L
{\displaystyle L}
ist symmetrisch .
L
{\displaystyle L}
ist positiv-semidefinit , insbesondere also
λ
i
≥
0
{\displaystyle \lambda _{i}\geq 0}
für alle
i
{\displaystyle i}
.
L
{\displaystyle L}
ist eine M-Matrix .
Die Spalten- und Zeilensummen sind Null. Insbesondere ist
λ
0
=
0
{\displaystyle \lambda _{0}=0}
mit Eigenvektor
v
0
=
(
1
,
1
,
…
,
1
)
{\displaystyle \mathbf {v} _{0}=(1,1,\dots ,1)}
.
Die Vielfachheit des Eigenwertes
0
{\displaystyle 0}
ist die Anzahl der Zusammenhangskomponenten des Graphen.