Степенева матриця

Степенева матриця — в математичній теорії графів це діагональна матриця, яка містить інформацію про степінь кожної вершини. Використовується разом із матрицею суміжності для конструювання матриці Кірхгофа (матриці Лапласа) для графу.

Визначення

Нехай дано $G=(V,E)$ з $\|V\|=n$, тоді степінь матриці $D$ для $G$ це квадратна матриця $n\times n$, яка визначається як

$d_{i,j}:=\left\{{\begin{matrix}\deg(v_{i}),&\ i=j\\0,&\ i\neq j\end{matrix}}\right.$

Приклад

Граф	Степенева матриця
	${\begin{pmatrix}3&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{pmatrix}}$

Для неорієнтованого графу степінь вершини це число ребер, що є інцидентними для даної вершини. Це означає що кожна петля рахується двічі.

• Степенева матриця k-регулярного графу має сталу діагональ $k$.

Посилання

• Степенева матриця на WolframMathWorld

Див. також

• Матриця суміжності
• Матриця Кірхгофа (Матриця Лапласа)