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

Тип матрицы в алгебраической теории графов

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

Определение

Для данного графа с матрицей степеней является диагональная матрица, определяемая как ^[1] ${\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})&{\mbox{if}}\ i=j\\0&{\mbox{otherwise}}\end{matrix}}\right.}$

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

Пример

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

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

Характеристики

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

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

Ссылки

1. Chung, Fan ; Lu, Linyuan; Vu, Van (2003), "Спектры случайных графов с заданными ожидаемыми степенями", Труды Национальной академии наук Соединенных Штатов Америки , 100 (11): 6313–6318, Bibcode : 2003PNAS..100.6313C, doi : 10.1073/pnas.0937490100 , MR  1982145, PMC  164443 , PMID  12743375.
2. Mohar, Bojan (2004), «Лапласианы графов», в Beineke, Lowell W.; Wilson, Robin J. (ред.), Topics in algebraic graph theory, Encyclopedia of Mathematics and its Applications, т. 102, Cambridge University Press, Кембридж, стр. 113–136, ISBN 0-521-80197-4, МР  2125091.