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

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

Визначення

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

$d_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i),& i=j\\ 0,& i\ne j\end{array}$

Приклад

Граф	Степенева матриця
	$\left(\begin{array}{cccccc}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{array}\right)$

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

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

Посилання

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

Див. також

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