Laplaceova matrika

Laplaceova matrika (tudi Kirchoffova matrika) je matrika s katero se predstavi graf. Skupaj s Kirchoffovim zakonom se lahko uporabi za izračunavanje števila vpetih dreves za dani graf. Razen tega se lahko Laplaceovo matriko uporabi za določanje mnogih značilnosti grafov.

Definicija

Za dani enostavni graf $G$ z $n$ točkami], so elementi Laplaceove matrike $l_{i,j}$ dani kot:

${\ell }_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i)& \text{kadar je}i=j\\ -1& \text{kadar je}i\ne j\text{in je }{v}_i\text{soseden z }{v}_j\\ 0& \text{v ostalih primerih}.\end{array}$

kjer

• $\mathrm{deg}(v_i)$ pomeni stopnjo v točki $i$

To pomeni, da je Laplaceova matrika razlika med matriko stopenj in matriko sosednosti istega grafa.

Normalizirana oblika je:

${\ell }_{i,j}:=\{\begin{array}{cc}1& \text{kadar je}i=j\text{in}\mathrm{deg}(v_i)\ne 0\\ -\frac{1}{\sqrt{\mathrm{deg}(v_i)\mathrm{deg}(v_j)}}& \text{kadar je}i\ne j\text{in je }{v}_i\text{soseden z}{v}_j\\ 0& \text{v ostalih primerih}.\end{array}$.

Zgled

označeni graf	Laplaceova matrika
	$\left(\begin{array}{cccccc}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)$

Značilnosti

Za graf $G$ in njegovo Laplaceovo matriko $L$, ki ima lastne vrednosti enake ${\lambda }_0\le {\lambda }_1\le \cdots \le {\lambda }_{n-1}$:

• matrika $L$ je pozitivno semidefinitna
• število pojavov vrednosti 0 med lastnimi vrednostmi v Laplaceovi matriki je enako številu povezanih komponent v grafu
• ${\lambda }_0$ je vedno enaka 0
• ${\lambda }_1$ se imenuje algebrska povezljivost
• najmanjša neničelna lastna vrednost se imenuje spektralna vrzel ali Fiedlerjeva vrednost

Glej tudi

• seznam vrst matrik

Zunanje povezave

• Predloga:MathWorld
• Laplaceova matrika Predloga:Ikona en
• Laplaceova matrika Predloga:Webarchive na PlanetMath Predloga:Ikona en
• Laplaceova matrika Predloga:Webarchive Predloga:Ikona en