TheSlide.ru

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

Содержание

1. Дискретная математика
2. Определения дереваПусть G =(V, E) – н-граф.Деревом называется связный ациклический граф.
3. Определение лесаЛесом называется несвязный ациклический граф.
4. Теорема 1Граф будет дерево тогда и только
5. Терема 2Граф с n вершинами будет деревом
6. Бинарное деревоБинарным деревом называется ориентированное дерево с
7. Корень дереваЕсли дерево неориентированно, то его можно
8. Корень дереваУ всех вершин дерева локальные степени
9. Слайд 9
10. Вершины максимального типаДано неориентированное дерево Т.Концевые вершины
11. Вершины максимального типаУдалим из дерева Т ребра,
12. Вершины максимального типаУдалим из дерева Т1 концевые
13. Вершины максимального типаУтверждение 1В конечном дереве есть
14. Вершины максимального типаУтверждение 1В конечном дереве есть
15. Вершины максимального типаУтверждение 3 Центрами деревьев являются
16. Вершины максимального типаk=3 , центров два, длина диаметральной цепи 2k-1=5.
17. Ветвь дереваВетвью вершины а в дереве Т
18. Ветвь t
19. Скачать презентанцию

Определения дереваПусть G =(V, E) – н-граф.Деревом называется связный ациклический граф.

Главная
Разное
Дискретная математика

Слайды и текст этой презентации

Слайд 1Деревья
Дискретная математика

ДеревьяДискретная математика

Слайд 2Определения дерева
Пусть G =(V, E) – н-граф.
Деревом называется связный ациклический

граф.

Определения дереваПусть G =(V, E) – н-граф.Деревом называется связный ациклический граф.

Слайд 3Определение леса
Лесом называется несвязный ациклический граф.

Определение лесаЛесом называется несвязный ациклический граф.

Слайд 4Теорема 1
Граф будет дерево тогда и только тогда, когда любые

две его вершины связаны единственной простой цепью.
Связность дает
наличие

такой
цепи, ацикличность
– ее единственность.

Теорема 1Граф будет дерево тогда и только тогда, когда любые две его вершины связаны единственной простой цепью.

Слайд 5Терема 2
Граф с n вершинами будет деревом тогда и только

тогда, в нем ровно n-1 ребро.
Если ориентировать
дерево о выбранной

вершины (корня),
то в каждую вершину
будет входить 1 ребро,
а в корень – 0.

Терема 2Граф с n вершинами будет деревом тогда и только тогда, в нем ровно n-1 ребро.Если ориентировать

Слайд 6Бинарное дерево
Бинарным деревом называется ориентированное дерево с корнем, где каждая

вершина имеет локальную степень исхода, равную 2.

Бинарное деревоБинарным деревом называется ориентированное дерево с корнем, где каждая вершина имеет локальную степень исхода, равную 2.

Слайд 7Корень дерева
Если дерево неориентированно, то его можно ориентировать от корня.

Корень – это любая выделенная вершина.

Корень дереваЕсли дерево неориентированно, то его можно ориентировать от корня. Корень – это любая выделенная вершина.

Слайд 8Корень дерева
У всех вершин дерева локальные степени захода равны 1,

а у корня 0.
Вершины, степени исхода которых равны 0 называются

листьями
Высотой дерева называется наибольшее расстояние от корня до листа.

Корень дереваУ всех вершин дерева локальные степени захода равны 1, а у корня 0.Вершины, степени исхода которых

Слайд 9

Слайд 10Вершины максимального типа
Дано неориентированное дерево Т.
Концевые вершины дерева – вершины,

локальная степень которых равна 1.
Назовем их вершинами первого типа дерева

Т.

Вершины максимального типаДано неориентированное дерево Т.Концевые вершины дерева – вершины, локальная степень которых равна 1.Назовем их вершинами

Слайд 11Вершины максимального типа
Удалим из дерева Т ребра, инцидентные концевым вершинам

– концевые ребра. Получим дерево Т1.
Концевые вершины
дерева Т1 –

Вершины
типа 2.

Вершины максимального типаУдалим из дерева Т ребра, инцидентные концевым вершинам – концевые ребра. Получим дерево Т1. Концевые

Слайд 12Вершины максимального типа
Удалим из дерева Т1 концевые ребра. Получим дерево

Т2.
Концевые вершины
дерева Т2 –
Вершины
типа 3.

Вершины максимального типаУдалим из дерева Т1 концевые ребра. Получим дерево Т2. Концевые вершиныдерева Т2 – Вершинытипа 3.

Слайд 13Вершины максимального типа
Утверждение 1
В конечном дереве есть вершины только конечного

числа типов.
Утверждение 2
Вершин максимального типа k одна или две.

Вершины максимального типаУтверждение 1В конечном дереве есть вершины только конечного числа типов.Утверждение 2Вершин максимального типа k одна

Слайд 14Вершины максимального типа
Утверждение 1
В конечном дереве есть вершины только конечного

числа типов.
Утверждение 2
Вершин максимального типа k одна или две.

Вершины максимального типаУтверждение 1В конечном дереве есть вершины только конечного числа типов.Утверждение 2Вершин максимального типа k одна

Слайд 15Вершины максимального типа
Утверждение 3
Центрами деревьев являются вершины максимального типа

k и только они. Все диаметральные цепи проходят через центры.

Длина диаметральной цепи равна 2k-1, если центра два и 2k-2, если центр один.

Вершины максимального типаУтверждение 3 Центрами деревьев являются вершины максимального типа k и только они. Все диаметральные цепи

Слайд 16Вершины максимального типа
k=3 , центров два, длина диаметральной цепи 2k-1=5.

Вершины максимального типаk=3 , центров два, длина диаметральной цепи 2k-1=5.

Слайд 17Ветвь дерева
Ветвью вершины а в дереве Т с корнем а0

называется подграф, порожденный множеством вершин В(а) состоящим из вершин, связанных

с корнем цепь, проходящей через а.

Ветвь дереваВетвью вершины а в дереве Т с корнем а0 называется подграф, порожденный множеством вершин В(а) состоящим

Слайд 18Ветвь
t

Ветвь t

Скачать презентацию

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно хранить и делиться своими презентациями с другими пользователями.

Для правообладателей