Laplaceova matrika

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

Definicija

Za dani enostavni graf $G \,$ z $n \,$ vozlišči, 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 vozlišču $i \,$

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

Normalizirana oblika pa 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 \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 algebraična povezljivost
• najmanjša neničelna lastna vrednost se imenuje spektralna vrzel ali Fiedlerjeva vrednost

Glej tudi

• seznam vrst matrik

Zunanje povezave

• Laplaceova matrika na MathWorld (v angleščini)
• Laplaceova matrika (v angleščini)
• Laplaceova matrika na PlanetMath (v angleščini)
• Laplaceova matrika (v angleščini)