Laplaceova matrika

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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[uredi | uredi kodo]

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

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

Normalizirana oblika pa 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[uredi | uredi kodo]

označeni graf Laplaceova matrika
6n-graf.svg \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[uredi | uredi kodo]

Za graf  G \, in njegovo Laplaceovo matriko  L \,, ki ima lastne vrednosti enake \lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}:

Glej tudi[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]