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

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

Определение [ править ]

Для графа с , матрица степеней для является диагональной матрицей, определяемой как ^[1]${\ Displaystyle G = (V, E)}$${\ Displaystyle | V | = п}$ ${\ displaystyle D}$${\ displaystyle G}$${\ Displaystyle п \ раз п}$

${\displaystyle D_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{if}}\ i=j\\0&{\mbox{otherwise}}\end{matrix}}\right.}$

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

Пример [ править ]

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

Граф, помеченный вершинами	Матрица степеней
	${\displaystyle {\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-регулярного графа имеет постоянную диагональ .${\displaystyle k}$

Ссылки [ править ]