Matrika stopenj

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

Matrika stopenj je diagonalna matrika, ki vsebuje stopnje za vsako vozlišče. Uporablja se skupaj z matriko sosednosti za tvorjenje Laplaceove matrike.

Definicija[uredi | uredi kodo]

Za dani graf  G = (V, E) \, je matrika stopenj kvadratna matrika z razsežnostjo n \times n \,, ki ima elemente enake

d_{i,j} =\left\{
\begin{matrix} 
\deg(v_i) & \mbox{kadar je}\ i = j \\
0 & \mbox{v ostalih primerih}
\end{matrix}
\right.
.

kjer je

  •  \deg(v_i) \, stopnja vozlišča  i \,

Zgled[uredi | uredi kodo]

graf z označenimi vozlišči matrika stopenj
6n-graph2.svg \begin{bmatrix}
4 & 0 & 0 & 0 & 0 & 0\\
0 & 3 & 0 & 0 & 0 & 0\\
0 & 0 & 2 & 0 & 0 & 0\\
0 & 0 & 0 & 3 & 0 & 0\\
0 & 0 & 0 & 0 & 3 & 0\\
0 & 0 & 0 & 0 & 0 & 1\\
\end{bmatrix}

V neusmerjenem grafu je stopnja enaka številu povezav, ki so vezane na vozlišče. To pomeni, da se zanke štejejo dvakrat (glej vozlišče 1).

Matrika stopenj za k-regularni graf ima glavno diagonalo iz samih enakih vrednosti, ki so enake k.

Glej tudi[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]