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

1. Дискретная математика

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

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

Пусть G =(V, E) – н-граф.
Локальной степенью
вершины v V называется
число ρ v равное числу ребер,
инцидентных вершине v. При
этом вклад петли в степень
вершины равен 2.

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

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

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

ρ(a)=4
ρ(b)=2
ρ(c)=3
ρ(d)=0
Вектор
степеней
(4, 3, 2, 0)

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

Замечание 1: векторы степеней
изоморфных графов одинаковы.
ρ=(4,3,2,0)

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

Замечание 2: Сумма всех
локальных степеней вершин
н-графа равна удвоенному
количеству ребер.
n
vi 2 e
i 1
e - число ребер н-графа.

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

Теорема (о числе вершин
нечетной степени):
Число вершин нечетной
степени – четно.

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

Доказательство:
vi 2 e
Сумма в левой части равенства – четна.
Если убрать все четные слагаемые,
сумма останется четной.
Сумма нечетных слагаемых четна, если
их четное число.

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

Локально-конечным называется
н-граф, все локальные степени
которого конечны.
Рис. 7.
Локальноконечный,
бесконечный
однородный
граф степени 4.

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

Однородным степени k
называется н-граф, локальные
степени которого одинаковы и
равны k.
Для однородного графа степени k:
vi k v 2 e ,
k
e v , v число вершин
2

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

Пусть G = (V, E) – ор-граф.
Локальной степенью исхода
вершины v V называется
число ρ v , равное числу
--
ребер, выходящих из вершины v.

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

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

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

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

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

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

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

ρ a 3; ρ a 2;
ρ b 1; ρ b 1;
ρ c 1; ρ c 2;
ρ d 0; ρ d 0.
ρ 3,1,1, 0
ρ 2, 2,1, 0

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

Замечание 3: векторы
степеней исхода и степеней
захода изоморфных графов
одинаковы.

17.

ρ 3,1,1, 0 ρ 2, 2,1, 0

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

Замечание 4: Сумма всех
локальных степеней исхода
вершин и сумма всех локальных
степеней захода ор-графа равна
количеству ребер.
n
n
vi vi e
i 1
i 1

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

Локально-конечным называется
ор-граф, все локальные степени
исхода и захода которого конечны.
Рис. 7.
Локальноконечный,
бесконечный
однородный
граф степени 2.

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

Однородным степени k
называется ор-граф, локальные
степени исхода и степени захода
которого одинаковы и равны k.
Для однородного графа степени k:
vi vi k v e ,
e k v .