Matrika stopenj

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

Definicija

Za dani graf $G=(V,E)\,$$G=(V,E)\,$ je matrika stopenj kvadratna matrika z razsežnostjo $n\times n\,$$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.$$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})\,$$\deg(v_{i})\,$ stopnja točke $i\,$$i\,$.

Zgled

graf z označenimi točkami	matrika stopenj
	${\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}}$${\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 točko. To pomeni, da se zanke štejejo dvakrat (glej točko 1).

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

Glej tudi

• seznam vrst matrik

Zunanje povezave

• Uvod v uporabo graf-teoretičnih matrik v kemiji (v slovenščini)
• Weisstein, Eric Wolfgang. "DegreeMatrix" (angleščina). MathWorld.