Локальные степени вершин н-графа

Пусть G =(V, E) – н-граф.

(Локальной) Степенью или (валентностью)   вершины v называется число ребер, инцидентных вершине v.

Если не оговаривается особо, то петля учитывается дважды при подсчете локальной степени вершины.

Граф называется правильным (с валентностью r) или r-валентным графом (регулярным, однородным), если степени всех его вершин равны.

Степень изолированной вершины равна 0.

Вектор степеней н-графа G = (V, E) – вектор размерности n, составленный из степеней вершин графа, расположенных по убыванию.

Локальные степени вершин орграфа

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

Вектор степеней исхода ор-графа G =(V, E) – вектор размерности n, составленный из степеней исхода вершин графа, расположенных по убыванию.

Вектор степеней захода ор-графа G =(V, E) – вектор размерности n, составленный из степеней захода вершин графа, расположенных по убыванию.

 

Пример 6.1.

Дан н-граф G (см. рис. 6.8). Построить матрицу инцидентности и матрицу смежности. Найти вектор степеней.

Рис. 6.8. Неориентированный граф

 

Матрица инцидентности

	a	b	c	d
1	1	0	0	0
2	1	0	1	0
3	1	0	1	0
4	1	1	0	0
5	0	1	1	0

 

Ребро 1 инцидентно только вершине а. Поэтому в первой строке только одна 1.

Ребро 2 инцидентно вершинам а и с, поэтому во второй строке в первом и третьем столбце стоят 1. И так далее.

По матрице видно, что ребро 1 – петля вокруг вершины а; что ребра 2 и 3 – кратные, так как строки 2 и 3 одинаковые; что вершина d – изолированная, так как в последнем столбце нет единиц.

Матрица смежности

	a	b	c	d
a	1	1	2	0
b	1	0	1	0
c	2	1	0	0
d	0	0	0	0

        

Вершина а с вершиной а связана одним ребром. Поэтому на месте (1,1) матрицы смежности стоит 1.

Вершина а с вершиной b связана одним ребром. Поэтому на месте (1,2) матрицы смежности стоит 1.

Вершина а с вершиной c связана двумя ребрами. Поэтому на месте (1,3) матрицы смежности стоит 2.

И так далее.

По матрице видно, что ребро 1 – петля вокруг вершины а, так как соответствующий диагональный элемент равен 1; что вершины а и с связаны парой кратных ребер; что вершина d – изолированная.

Найдем вектор локальных степеней.

Локальная степень вершины а – число ребер, инцидентных вершине а. Это ребра 1, 2, 3, 4. Но петля в локальной степени вершины считается дважды, поэтому .

Локальная степень вершины b – число ребер, инцидентных вершине b. Это ребра 4 и 5. Поэтому .

Аналогично, , .

Таким образом, искомый вектор степеней примет вид:

Заметим, что если степени некоторых вершин одинаковы, то при составлении вектора локальных степеней надо выписать по убыванию все повторяющиеся значения.

Пример 6.2.

Дан орграф G (см. рис. 6.9). Построить матрицу инцидентности и матрицу смежности. Найти вектор степеней исхода и вектор степеней захода орграфа.

 

Рис. 6.9. Ориентированный граф

Матрица инцидентности

	a	b	c	d
1	2	0	0	0
2	-1	0	1	0
3	-1	0	1	0
4	-1	1	0	0
5	0	-1	1	0
6	0	1	-1	0

 

Ребро 1 инцидентно только вершине а – это петля вокруг вершины а, поэтому в первой строке стоит число отличное от

 -1, 1, 0.

Ребро 2 выходит из вершины а и входит в вершину с, поэтому во второй строке в первом столбце стоит -1, а в третьем столбце стоит 1. И так далее.

По матрице видно, что ребро 1 – петля вокруг вершины а; что ребра 2 и 3 – кратные, так как строки 2 и 3 одинаковые; что ребра 5 и 6 – симметричные, так как там где на 5 строке стоит -1, там на 6 строке стоит 1, и наоборот; что вершина d – изолированная, так как в последнем столбце нет ничего, кроме 0.

Матрица смежности

	a	b	c	d
a	1	1	0	0
b	0	0	1	0
c	2	1	0	0
d	0	0	0	0

Из вершины а в вершину а ведет одно ребро. Поэтому на месте (1, 1) матрицы смежности стоит 1.

Из вершины а в вершину b ведет одно ребро. Поэтому на месте (1, 2) матрицы смежности стоит 1.

Из вершины а в вершины с и d не ведет ни одного ребра. Поэтому на местах (1, 3) и (1, 4) матрицы смежности стоят 0.

И так далее.

По матрице видно, что ребро 1 – петля вокруг вершины а, так как соответствующий диагональный элемент равен 1; что вершины а и с связаны парой кратных ребер, так как на месте (3, 1) стоит 2; что вершины b и с связаны парой симметричных ребер, так как элементы, стоящие на местах (2, 3) и (3, 2) – одинаковы; что вершина d – изолированная.

Найдем векторы локальных степеней.

Локальная степень исхода вершины а – число ребер, выходящих из вершины а. Это ребра 1, 4. Поэтому .

Локальная степень захода вершины а – число ребер, входящих в вершину а. Это ребра 1, 2, 3. Поэтому .

Аналогично,

, ;

, ;

, .

Таким образом, искомые векторы исхода и векторы захода примет вид: