Локальные степени вершин н-графа
Пусть 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. Поэтому 
.
Аналогично,
, 
;
, 
;
, 
.
Таким образом, искомые векторы исхода и векторы захода примет вид:
Дата добавления: 2018-04-15; просмотров: 3295; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!