🗊Презентация Деревья. Связность. Дерево и его виды

Категория: Математика
Нажмите для полного просмотра!
Деревья. Связность. Дерево и его виды, слайд №1Деревья. Связность. Дерево и его виды, слайд №2Деревья. Связность. Дерево и его виды, слайд №3Деревья. Связность. Дерево и его виды, слайд №4Деревья. Связность. Дерево и его виды, слайд №5Деревья. Связность. Дерево и его виды, слайд №6Деревья. Связность. Дерево и его виды, слайд №7Деревья. Связность. Дерево и его виды, слайд №8Деревья. Связность. Дерево и его виды, слайд №9Деревья. Связность. Дерево и его виды, слайд №10Деревья. Связность. Дерево и его виды, слайд №11Деревья. Связность. Дерево и его виды, слайд №12Деревья. Связность. Дерево и его виды, слайд №13Деревья. Связность. Дерево и его виды, слайд №14Деревья. Связность. Дерево и его виды, слайд №15Деревья. Связность. Дерево и его виды, слайд №16Деревья. Связность. Дерево и его виды, слайд №17Деревья. Связность. Дерево и его виды, слайд №18Деревья. Связность. Дерево и его виды, слайд №19Деревья. Связность. Дерево и его виды, слайд №20Деревья. Связность. Дерево и его виды, слайд №21Деревья. Связность. Дерево и его виды, слайд №22Деревья. Связность. Дерево и его виды, слайд №23Деревья. Связность. Дерево и его виды, слайд №24Деревья. Связность. Дерево и его виды, слайд №25Деревья. Связность. Дерево и его виды, слайд №26Деревья. Связность. Дерево и его виды, слайд №27Деревья. Связность. Дерево и его виды, слайд №28Деревья. Связность. Дерево и его виды, слайд №29Деревья. Связность. Дерево и его виды, слайд №30Деревья. Связность. Дерево и его виды, слайд №31Деревья. Связность. Дерево и его виды, слайд №32Деревья. Связность. Дерево и его виды, слайд №33Деревья. Связность. Дерево и его виды, слайд №34Деревья. Связность. Дерево и его виды, слайд №35Деревья. Связность. Дерево и его виды, слайд №36Деревья. Связность. Дерево и его виды, слайд №37Деревья. Связность. Дерево и его виды, слайд №38Деревья. Связность. Дерево и его виды, слайд №39Деревья. Связность. Дерево и его виды, слайд №40Деревья. Связность. Дерево и его виды, слайд №41
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Деревья. Связность. Дерево и его виды. Доклад-сообщение содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


ЛЕКЦИЯ 11. ДЕРЕВЬЯ
Описание слайда:
ЛЕКЦИЯ 11. ДЕРЕВЬЯ

Слайд 2


Связность. Дерево и его виды
Описание слайда:
Связность. Дерево и его виды

Слайд 3


Например, все компьютеры, включённые Например, все компьютеры, включённые в Интернет, образуют связный граф. Два конкретных компьютера могут быть не соединёнными напрямую, но от каждого информацию можно передать на любой другой.
Описание слайда:
Например, все компьютеры, включённые Например, все компьютеры, включённые в Интернет, образуют связный граф. Два конкретных компьютера могут быть не соединёнными напрямую, но от каждого информацию можно передать на любой другой.

Слайд 4


Деревья. Связность. Дерево и его виды, слайд №4
Описание слайда:

Слайд 5


Последовательность v1 , е1 , v2 , е2 , …, vk , еk , vk+1 Последовательность v1 , е1 , v2 , е2 , …, vk , еk , vk+1 вершин и неповторяющихся рёбер (дуг) графа такая, что е1 =(vi ;vi+1 ), i=1, …, k, v1 =vk+1 называется циклом.
Описание слайда:
Последовательность v1 , е1 , v2 , е2 , …, vk , еk , vk+1 Последовательность v1 , е1 , v2 , е2 , …, vk , еk , vk+1 вершин и неповторяющихся рёбер (дуг) графа такая, что е1 =(vi ;vi+1 ), i=1, …, k, v1 =vk+1 называется циклом.

Слайд 6


Деревья. Связность. Дерево и его виды, слайд №6
Описание слайда:

Слайд 7


Следующие утверждения эквивалентны: Следующие утверждения эквивалентны: G – дерево. G – связный неорграф и в нём число ребер m на единицу меньше числа вершин n: m = n - 1. 3. Любые две вершины дерева соединяет единственный путь. G – неорграф без циклов и если любую пару несмежных вершин соединить ребром, то G будет содержать единственный цикл.
Описание слайда:
Следующие утверждения эквивалентны: Следующие утверждения эквивалентны: G – дерево. G – связный неорграф и в нём число ребер m на единицу меньше числа вершин n: m = n - 1. 3. Любые две вершины дерева соединяет единственный путь. G – неорграф без циклов и если любую пару несмежных вершин соединить ребром, то G будет содержать единственный цикл.

Слайд 8


Изобразите все деревья (неизоморфные), Изобразите все деревья (неизоморфные), которые можно построить на 6 вершинах (деревья образуют лес).
Описание слайда:
Изобразите все деревья (неизоморфные), Изобразите все деревья (неизоморфные), которые можно построить на 6 вершинах (деревья образуют лес).

Слайд 9


Как правило, дерево-граф выглядит как Как правило, дерево-граф выглядит как дерево «вверх ногами». Корневым называется дерево с выделенной по каким-либо соображениям вершиной. Тогда любые две вершины находятся в отношении «предок (верхняя) – потомок (нижняя)». Корень не имеет предков. Вершина без потомков называется листом.
Описание слайда:
Как правило, дерево-граф выглядит как Как правило, дерево-граф выглядит как дерево «вверх ногами». Корневым называется дерево с выделенной по каким-либо соображениям вершиной. Тогда любые две вершины находятся в отношении «предок (верхняя) – потомок (нижняя)». Корень не имеет предков. Вершина без потомков называется листом.

Слайд 10


Ориентированным деревом называется орграф Ориентированным деревом называется орграф без циклов и петель, у которого: - есть ровно одна вершина (корень), в которую не входит ни одна дуга (степень входа d+ корня равна нулю); - в каждую вершину, кроме корня, входит ровно одна дуга (то есть степень входа d+ вершин кроме корня равна единице); - из корня в каждую вершину идёт ровно один путь (рис. 9).
Описание слайда:
Ориентированным деревом называется орграф Ориентированным деревом называется орграф без циклов и петель, у которого: - есть ровно одна вершина (корень), в которую не входит ни одна дуга (степень входа d+ корня равна нулю); - в каждую вершину, кроме корня, входит ровно одна дуга (то есть степень входа d+ вершин кроме корня равна единице); - из корня в каждую вершину идёт ровно один путь (рис. 9).

Слайд 11


Двоичным называется дерево Двоичным называется дерево – неориентированное со степенями вершин не больше 3 (рис. 8); – ориентированное со степенями выхода вершин не больше 2 (рис. 9).
Описание слайда:
Двоичным называется дерево Двоичным называется дерево – неориентированное со степенями вершин не больше 3 (рис. 8); – ориентированное со степенями выхода вершин не больше 2 (рис. 9).

Слайд 12


Остовы
Описание слайда:
Остовы

Слайд 13


Пример. Найти число различных остовов Пример. Найти число различных остовов графа G (рис. 10).
Описание слайда:
Пример. Найти число различных остовов Пример. Найти число различных остовов графа G (рис. 10).

Слайд 14


Деревья. Связность. Дерево и его виды, слайд №14
Описание слайда:

Слайд 15


Деревья. Связность. Дерево и его виды, слайд №15
Описание слайда:

Слайд 16


Деревья. Связность. Дерево и его виды, слайд №16
Описание слайда:

Слайд 17


Деревья. Связность. Дерево и его виды, слайд №17
Описание слайда:

Слайд 18


Деревья. Связность. Дерево и его виды, слайд №18
Описание слайда:

Слайд 19


Значит, данный граф имеет 11 различных Значит, данный граф имеет 11 различных остовов.
Описание слайда:
Значит, данный граф имеет 11 различных Значит, данный граф имеет 11 различных остовов.

Слайд 20


Теорема 2. Число рёбер неорграфа G, Теорема 2. Число рёбер неорграфа G, которые нужно удалить для получения остова, не зависит от порядка их удаления и равно ν(G) = m – n + k, где m – число рёбер, n – число вершин, k – число компонент cвязности графа G. ν (G) = m – n + k = m - (n - k) Ясно, что ν(G) + ν(G) = m . Для графа на рис. 12 ν (G) = 9 – 7 + 2 = 4, ν(G) = 7 – 2 = 5.
Описание слайда:
Теорема 2. Число рёбер неорграфа G, Теорема 2. Число рёбер неорграфа G, которые нужно удалить для получения остова, не зависит от порядка их удаления и равно ν(G) = m – n + k, где m – число рёбер, n – число вершин, k – число компонент cвязности графа G. ν (G) = m – n + k = m - (n - k) Ясно, что ν(G) + ν(G) = m . Для графа на рис. 12 ν (G) = 9 – 7 + 2 = 4, ν(G) = 7 – 2 = 5.

Слайд 21


Алгоритмы нахождения остова минимального веса
Описание слайда:
Алгоритмы нахождения остова минимального веса

Слайд 22


Другими словами, в задаче нужно Другими словами, в задаче нужно найти остов графа минимального веса.
Описание слайда:
Другими словами, в задаче нужно Другими словами, в задаче нужно найти остов графа минимального веса.

Слайд 23


Шаг 1. Присвоение начальных значений Шаг 1. Присвоение начальных значений Пусть (v1 – произвольная вершина), , Ø. Шаг 2. Обновление данных Найдём ребро (vi;vj) такое, что , , . Полагаем , , . Шаг 3. Проверка на завершение Если V = V, то G =( V, U ) – искомый остов. Иначе - переход к шагу 2.
Описание слайда:
Шаг 1. Присвоение начальных значений Шаг 1. Присвоение начальных значений Пусть (v1 – произвольная вершина), , Ø. Шаг 2. Обновление данных Найдём ребро (vi;vj) такое, что , , . Полагаем , , . Шаг 3. Проверка на завершение Если V = V, то G =( V, U ) – искомый остов. Иначе - переход к шагу 2.

Слайд 24


Деревья. Связность. Дерево и его виды, слайд №24
Описание слайда:

Слайд 25


Шаг 1. Пусть V = {v1}, тогда Шаг 1. Пусть V = {v1}, тогда V = {v2, v3, v4, v5, v6}, U = Ø. Первая итерация Шаг 2. . Включим, например, вершину v2 в V : , тогда Шаг 3. V  V, переход к шагу 2.
Описание слайда:
Шаг 1. Пусть V = {v1}, тогда Шаг 1. Пусть V = {v1}, тогда V = {v2, v3, v4, v5, v6}, U = Ø. Первая итерация Шаг 2. . Включим, например, вершину v2 в V : , тогда Шаг 3. V  V, переход к шагу 2.

Слайд 26


Деревья. Связность. Дерево и его виды, слайд №26
Описание слайда:

Слайд 27


Вторая итерация Вторая итерация Шаг 2. Шаг 3. V  V, переход к шагу 2.
Описание слайда:
Вторая итерация Вторая итерация Шаг 2. Шаг 3. V  V, переход к шагу 2.

Слайд 28


Деревья. Связность. Дерево и его виды, слайд №28
Описание слайда:

Слайд 29


Третья итерация Третья итерация Шаг 2. Шаг 3. V  V, переход к шагу 2.
Описание слайда:
Третья итерация Третья итерация Шаг 2. Шаг 3. V  V, переход к шагу 2.

Слайд 30


Деревья. Связность. Дерево и его виды, слайд №30
Описание слайда:

Слайд 31


Четвёртая итерация Четвёртая итерация Шаг 2. Шаг 3. V  V, переход к шагу 2.
Описание слайда:
Четвёртая итерация Четвёртая итерация Шаг 2. Шаг 3. V  V, переход к шагу 2.

Слайд 32


Деревья. Связность. Дерево и его виды, слайд №32
Описание слайда:

Слайд 33


Пятая итерация Пятая итерация Шаг 2. Шаг 3. V = V
Описание слайда:
Пятая итерация Пятая итерация Шаг 2. Шаг 3. V = V

Слайд 34


Деревья. Связность. Дерево и его виды, слайд №34
Описание слайда:

Слайд 35


Получен остов Получен остов минимального веса (рис. 14):
Описание слайда:
Получен остов Получен остов минимального веса (рис. 14):

Слайд 36


Деревья. Связность. Дерево и его виды, слайд №36
Описание слайда:

Слайд 37


Деревья. Связность. Дерево и его виды, слайд №37
Описание слайда:

Слайд 38


Деревья. Связность. Дерево и его виды, слайд №38
Описание слайда:

Слайд 39


Деревья. Связность. Дерево и его виды, слайд №39
Описание слайда:

Слайд 40


Деревья. Связность. Дерево и его виды, слайд №40
Описание слайда:

Слайд 41


Деревья. Связность. Дерево и его виды, слайд №41
Описание слайда:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию