Похожие презентации:
Локальные степени вершин графа
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, 018. Локальные степени вершин н-графа
Замечание 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 .