Матрица степеней - Degree matrix

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

Определение

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

{ displaystyle D_ {i, j}: = left {{ begin {matrix} deg (v_ {i}) & { mbox {if}} i = j 0 & { mbox {иначе} } 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 }} конец pmatrix$

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

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

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

Рекомендации

^ ^а ^б Чанг, Фань; Лу, Линьюань; Ву, Ван (2003), «Спектры случайных графов с заданными ожидаемыми степенями», Труды Национальной академии наук Соединенных Штатов Америки, 100 (11): 6313–6318, Дои:10.1073 / pnas.0937490100, МИСТЕР 1982145, ЧВК 164443, PMID 12743375.
^ Мохар, Боян (2004), «Графические лапласианы», в Beineke, Lowell W .; Уилсон, Робин Дж. (Ред.), Темы алгебраической теории графов, Энциклопедия математики и ее приложений, 102, Cambridge University Press, Кембридж, стр. 113–136, ISBN 0-521-80197-4, МИСТЕР 2125091.

[clv-1] а ^б Чанг, Фань; Лу, Линьюань; Ву, Ван (2003), «Спектры случайных графов с заданными ожидаемыми степенями», Труды Национальной академии наук Соединенных Штатов Америки, 100 (11): 6313–6318, Дои:10.1073 / pnas.0937490100, МИСТЕР 1982145, ЧВК 164443, PMID 12743375.

[mohar-2] Мохар, Боян (2004), «Графические лапласианы», в Beineke, Lowell W .; Уилсон, Робин Дж. (Ред.), Темы алгебраической теории графов, Энциклопедия математики и ее приложений, 102, Cambridge University Press, Кембридж, стр. 113–136, ISBN 0-521-80197-4, МИСТЕР 2125091.

[1]

[2]