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

в математический поле теория графов, то матрица степеней это диагональная матрица который содержит информацию о степень каждого вершина- то есть количество ребер, прикрепленных к каждой вершине.^[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}$.

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