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

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

Визначення

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

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

Приклад

Граф	Степенева матриця
	${\displaystyle {\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-регулярного графу має сталу діагональ ${\displaystyle k}$.

Посилання

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

Див. також

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