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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Визначення[ред.ред. код]

Нехай дано 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.

Приклад[ред.ред. код]

Граф Степенева матриця
6n-graph2.svg \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}

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

Посилання[ред.ред. код]

Дивіться також[ред.ред. код]