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{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:

$\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

Glej tudi

• seznam vrst matrik

Zunanje povezave

• Weisstein, Eric Wolfgang. »Laplacian Matrix«. MathWorld.
• Laplaceova matrika (angleško)
• Laplaceova matrika Arhivirano 2009-12-12 na Wayback Machine. na PlanetMath (angleško)
• Laplaceova matrika Arhivirano 2012-08-13 na Wayback Machine. (angleško)