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:^[1]

\ell _{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{kadar je}}\ i=j\\-1&{\mbox{kadar je}}\ i\neq j\ {\mbox{in je }}\ v_{i}\quad {\mbox{soseden z }}v_{j}\\0&{\mbox{v ostalih primerih}}.\end{cases}}

kjer

$\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:^[1]

\ell _{i,j}:={\begin{cases}1&{\mbox{kadar je}}\ i=j\ {\mbox{in}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{kadar je}}\ i\neq j\ {\mbox{in je }}\ v_{i}\quad {\mbox{soseden z}}\quad v_{j}\\0&{\mbox{v ostalih primerih}}.\end{cases}}

.

Zgled

označeni graf	Laplaceova matrika
	$\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)$

Značilnosti

Za graf $G\,$ in njegovo Laplaceovo matriko $L\,$ , ki ima lastne vrednosti enake $\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \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