Матрица степеней

В математической области алгебраической теории графов неориентированного матрица степеней графа представляет собой диагональную матрицу , содержащую информацию о степени каждой вершины , то есть о количестве ребер, присоединенных к каждой вершине. Он используется вместе с матрицей смежности для построения матрицы Лапласа графа: матрица Лапласа представляет собой разность матрицы степеней и матрицы смежности.

Определение

Учитывая график $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.$

где степень $\deg(v_{i})$ вершины подсчитывает, сколько раз ребро заканчивалось в этой вершине. В неориентированном графе это означает, что каждый цикл увеличивает степень вершины на два. В ориентированном графе термин степень может относиться либо к степени входа (количество входящих ребер в каждой вершине), либо к степени выхода (количество исходящих ребер в каждой вершине).

Пример

Следующий неориентированный граф имеет матрицу степеней 6x6 со значениями:

Граф с метками вершин	Матрица степеней
	${\begin{pmatrix}4&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}}$

Обратите внимание, что в случае неориентированных графов ребро, которое начинается и заканчивается в одном и том же узле, увеличивает соответствующее значение степени на 2 (т. е. оно учитывается дважды).

Свойства

Матрица степеней k-регулярного графа имеет постоянную диагональ $k$.

Согласно формуле суммы степеней , след матрицы степеней в два раза превышает количество ребер рассматриваемого графа.