Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
20 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
1.60 MB
Просмотров:
64
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Дискретная математика
Локальные степени вершин графа
№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.
№20 слайд
Содержание слайда: Локальные степени вершин ор-графа
Однородным степени k называется ор-граф, локальные степени исхода и степени захода которого одинаковы и равны k.
Для однородного графа степени k: