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

Август 1, 2022

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

Содержание

2. Локальные степени вершин н-графа Пусть G =(V, E) – н-граф. Локальной степенью вершины называется число равное
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: Сумма всех локальных степеней вершин н-графа равна удвоенному количеству ребер.
7. Локальные степени вершин н-графа Теорема (о числе вершин нечетной степени): Число вершин нечетной степени – четно.
8. Локальные степени вершин н-графа Доказательство: Сумма в левой части равенства – четна. Если убрать все четные
9. Локальные степени вершин н-графа Локально-конечным называется н-граф, все локальные степени которого конечны. Рис. 7. Локально- конечный,
10. Локальные степени вершин н-графа Однородным степени k называется н-граф, локальные степени которого одинаковы и равны k.
11. Локальные степени вершин ор-графа Пусть G = (V, E) – ор-граф. Локальной степенью исхода вершины называется
12. Локальные степени вершин ор-графа Локальной степенью захода вершины называется число , равное числу ребер, выходящих из
13. Локальные степени вершин ор-графа Вектор степеней исхода ор-графа G =(V, E) – вектор размерности n, составленный
14. Локальные степени вершин ор-графа Вектор степеней захода ор-графа – вектор размерности n, составленный из степеней захода
15. Локальные степени вершин ор-графа
16. Локальные степени вершин ор-графа Замечание 3: векторы степеней исхода и степеней захода изоморфных графов одинаковы.
18. Локальные степени вершин н-графа Замечание 4: Сумма всех локальных степеней исхода вершин и сумма всех локальных
19. Локальные степени вершин ор-графа Локально-конечным называется ор-граф, все локальные степени исхода и захода которого конечны. Рис.
21. Скачать презентацию

Слайд 2

Локальные степени вершин н-графа
Пусть G =(V, E) – н-граф.
Локальной степенью вершины

называется число равное числу ребер, инцидентных вершине 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: Сумма всех локальных степеней вершин
н-графа

равна удвоенному количеству ребер.
- число ребер н-графа.

Слайд 7

Локальные степени вершин н-графа
Теорема (о числе вершин нечетной степени):
Число вершин нечетной

степени – четно.

Слайд 8

Локальные степени вершин н-графа
Доказательство:
Сумма в левой части равенства – четна.
Если убрать

все четные слагаемые, сумма останется четной.
Сумма нечетных слагаемых четна, если их четное число.

Слайд 9

Локальные степени вершин н-графа
Локально-конечным называется н-граф, все локальные степени которого конечны.

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

Слайд 10

Локальные степени вершин н-графа
Однородным степени k называется н-граф, локальные степени которого

одинаковы и равны k.
Для однородного графа степени k:

Слайд 11

Локальные степени вершин ор-графа
Пусть G = (V, E) – ор-граф.
Локальной степенью

исхода вершины называется число , равное числу ребер, выходящих из вершины v.

Слайд 12

Локальные степени вершин ор-графа
Локальной степенью захода вершины называется число , равное

числу ребер, выходящих из вершины v.

Слайд 13

Локальные степени вершин ор-графа
Вектор степеней исхода
ор-графа G =(V, E) –

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

Слайд 14

Локальные степени вершин ор-графа
Вектор степеней захода
ор-графа – вектор размерности n,

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

Слайд 15

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

Слайд 16

Локальные степени вершин ор-графа
Замечание 3: векторы степеней исхода и степеней захода

изоморфных графов одинаковы.

Слайд 17

Слайд 18

Локальные степени вершин н-графа
Замечание 4: Сумма всех локальных степеней исхода вершин

и сумма всех локальных степеней захода ор-графа равна количеству ребер.

Слайд 19

Локальные степени вершин ор-графа
Локально-конечным называется ор-граф, все локальные степени исхода и

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