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

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

Визначення

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

$d_{i,j}:=\left\{ \begin{matrix} \deg(v_i) & \mbox{if}\ i = j \\ 0 & \mbox{otherwise} \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

Дивіться також

• Матриця суміжності
• Матриця Лапласа