Презентация "Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса" 11 класс
Подписи к слайдам:
Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса
- Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса
- Гуляева
- Татьяна Викторовна
- учитель информатики и
- математики МБОУ СОШ №9
- с УИОП г.Павлово
- 2014 год
- Повторение основных понятий теории графов
- Понятие остовного связного дерева
- Понятие цикломатического числа
- Алгоритм Прима
- Алгоритм Крускаля
- Вопросы и задания
- Основные понятия теории графов
- По горизонтали:
- г р а ф
- 9. Наглядное сред-ство представления состава и структуры системы.
- р е б р о
- 2. Ненаправленная линия (без стрелки), соединяющая вершины графа.
- п у т ь
- ц и к л
- п у с т о й
- д у г а
- д е р е в о
- в е р ш и н а
- в з в е ш е н н ы й
- 4. Последователь-ность рёбер и/или дуг, такая, что конец одной дуги (ребра) является началом другой дуги (реб-ра).
- 5. Путь, в котором совпадают начальная и конечная верши-ны.
- 6. Направленная ли-ния (со стрелкой), соединяющая верши-ны графа.
- 7. Граф без ребер.
- 10. Граф, в котором нет циклов.
- 11. Элемент (точка) графа, обозначаю-щий объект любой природы, входящий в множество объек-тов, описываемое графом.
- 12. Граф, ребрам (или дугам) или вершинам которого поставлены в соот-ветствие числовые величины.
- Перейдем к вопросам по вертикали
- Основные понятия теории графов
- По вертикали:
- г р а ф
- р е б р о
- п у т ь
- ц и к л
- п у с т о й
- д у г а
- д е р е в о
- в е р ш и н а
- в з в е ш е н н ы й
- 1. Последовательность чередующихся вершин и ребер графа при перемещении.
- м
- а
- ш
- р
- т
- с
- м
- ж
- ы
- р
- е
- н
- и
- о
- а
- н
- н
- й
- 8. Вершины, прилега-ющие к одному и тому же ребру.
- 3. Граф, в котором вершины соединены дугами.
- о
- н
- ы
- 4. Граф, в котором каждые две вершины смежные.
- Перейдем к изучению новых понятий
- Остовной связный подграф – подграф графа G, который содержит все его вершины и каждая вершина достижима из любой другой.
- Остовное связное дерево – подграф, включающий вершины исходного графа G, не содержащего циклы, каждая вершина которого достижима из любой другой.
- Цикломатическое число γ показывает, сколько ребер нужно удалить из графа, чтобы в нем не осталось циклов
- γ = m – n + 1,
- m - количество ребер
- n - количество вершин
- В некотором районе было решено провести газопровод между пятью деревнями. От Кошкино до Мышкино идти 10 км, от Мышкино до Ступино – 3 км, от Кошкино до Малаховки – 6 км, от Малаховки до Черняевки – 12 км, от Кошкино до Ступино – 11 км, от Мышкино до Чернеевки – 5 км, от Кошкино до Чернеевки – 7 км. Как необходимо провести трубу, чтобы она соединяла все пять деревень, и затраты при этом были минимальными?
- Построим граф, моделирующий дороги, соединяющие деревни.
- Чернеевка
- Мышкино
- Ступино
- Кошкино
- Малаховка
- 12
- 7
- 10
- 11
- 3
- 6
- 5
- Задача сводится к построению остовного связного дерева минимального веса.
- Рассчитаем цикломатическое число.
- m (количество ребер) равно 7
- n (количество вершин) рано 5
- γ = 7 – 5 + 1 = 3
- Т.е. три деревни напрямую соединены газовой трубой не будут.
- (переходы по щелчку)
- Пусть дан взвешенный неориентированный граф.
- Для построения минимального остовного дерева необходимо:
- 1. Представить граф в виде матрицы смежности
- 2. Найти в матрице наименьший элемент, соответству-ющий ребру, соединяющему i-ю и j-ю вершины графа
- 3. Вычеркнуть элементы i-й и j-й строки матрицы
- 4. Пометить i-й и j-й столбцы матрицы
- 5. В помеченных столбцах i и j найти наименьший элемент, отличный от уже найденного
- 6. Повторять пункты 3-5 до тех пор, пока не будут задействованы все вершины графа
- (переходы по щелчку)
- Решим задачу по алгоритму Прима.
- Переопределим вершины графа.
- Чернеевка
- Мышкино
- Ступино
- Кошкино
- Малаховка
- 12
- 7
- 10
- 11
- 3
- 6
- 5
- 12
- 7
- 10
- 11
- 3
- 6
- 5
- 5
- 2
- 1
- 3
- 4
- (переходы по щелчку)
- 12
- 7
- 10
- 11
- 3
- 6
- 5
- 5
- 2
- 1
- 3
- 4
- Представим граф в виде матрицы смежности.
- Найдем минимальный элемент.
- Он равен 3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- 3
- 3
- (переходы по щелчку)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
- Вычеркнем 2-ю и 3-ю строки таблицы. А столбцы 2 и 3 выделим.
- Найдем минимальный элемент в выделенных столбцах.
- Он равен 5
- 5
- (переходы по щелчку)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|||||
|
|
|
|
|
|
|
|
- Вычеркнем 5-ю строку таблицы. А столбец 5 выделим.
- Найдем минимальный элемент в выделенных столбцах.
- Он равен 7
- 5
- 7
- (переходы по щелчку)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
||||
|
|||||
|
|
|
|
|
|
|
|
- Вычеркнем 1-ю строку таблицы. А столбец 1 выделим.
- Найдем минимальный элемент в выделенных столбцах.
- Он равен 6
- 5
- 6
- (переходы по щелчку)
|
|
|
|
|
|
|
|
|
|||
|
|
||||
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
||||
|
|||||
|
|
||||
|
|
- Вычеркнем 4-ю строку таблицы. А столбец 4 выделим.
- (переходы по щелчку)
- Получаем связное остовное дерево минимальное веса.
|
|
|
|
|
|
|
|
|
|||
|
|
||||
|
|||||
|
|
||||
|
|
- 12
- 7
- 10
- 11
- 3
- 6
- 5
- 5
- 1
- 2
- 3
- 4
- (переходы по щелчку)
- Ответ: газопровод с минимальными затратами необходимо прокладывать так:
- 3
- 6
- 5
- 5
- 1
- 2
- 3
- 4
- 7
- 3
- 6
- 5
- Чернеевка
- Мышкино
- Ступино
- Кошкино
- Малаховка
- 7
- Протяженность газопровода – 21 км.
- Даны города, часть которых соединена между собой дорогами. Необходимо проложить туристический маршрут минимальной длины, проходящий через все города.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Задача сводится к построению остовного связного дерева минимального веса.
- Рассчитаем цикломатическое число.
- m (количество ребер) равно 9
- n (количество вершин) рано 6
- γ = 9 – 6 + 1 = 4
- Т.е. четыре дороги, соединяющие города, не будут включены в туристический маршрут.
- (переходы по щелчку)
- Удалить все ребра и получить остовной подграф с изолированными вершинами.
- Отсортировать ребра по возрастанию.
- Ребра последовательно, по возрастанию их весов, включаются в остовное дерево. Возможны случаи:
- а) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество;
- б) одна из вершин принадлежит связному под-множеству, другая нет, тогда включаем вторую в подмножество, которому принадлежит первая;
- в) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества;
- г) обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.
- Алгоритм завершается, когда все вершины будут объединены в одно множество.
- Для определения туристического маршрута минимальной длины воспользуемся алгоритмом Крускала.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Построим остовной подграф, содержащий только изолированные вершины.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Получаем шесть одноэлементных подмножеств.
- пуск
- Найдем ребро минимального веса и добавим его в остовной подграф.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Образуется связное подмножество вершин {V5, V6}.
- пуск
- Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Добавляем в подмножество вершин еще одну {V5,V6,V1}.
- пуск
- Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Добавляем в подмножество вершин еще одну {V5,V6,V1,V2}.
- пуск
- Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Образуется два подмножества {V5,V6,V1,V2} и {V3,V4} .
- пуск
- Но обе вершины принадлежат одному подмножеству {V5,V6,V1,V2}. Значит это ребро исключаем.
- Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Подмножества объединяются в единое связное множество {V1,V2,V6,V5,V3,V4} .
- пуск (2)
- Остальные ребра включать в граф не надо, т.к. все их вершины уже принадлежат одному связному множеству.
- 1
- 6
- 5
- 2
- 3
- 4
- 25
- 18
- 15
- 12
- 20
- 23
- 21
- 19
- 26
- Получили остовное связное дерево минимального веса, равного 85.
- Построенный граф (в задачах 1 и 2) является
- В граф включены все вершины
- Все вершины в графе можно
- соединить маршрутами
- В графе отсутствуют циклы
- В граф последовательно включались ребра,
- отсортированные по возрастанию весов
- остовным
- связным
- деревом
- с минимальным весом
- На строительном участке необходимо создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефонные линии не мешали строительству, их решили проводить вдоль дорог. Схема участка изображена на рисунке.
- Каким образом провести телефонные линии, чтобы их общая длина была минимальной?
- 260
- 240
- 180
- 210
- 100
- 100
- 150
- 200
- 380
- 1
- 6
- 5
- 2
- 3
- 4
- 7
- 170
- 210
- 100
- 100
- 150
- 200
- 1
- 6
- 5
- 2
- 3
- 4
- 7
- 170
- Общая длина телефонной линии равна 930 метров
- Кроссворд создан на сайте и расположен по адресу http://puzzlecup.com/?guess=3C2D4A01E0522AAU
- Информатика и ИКТ. Профильный уровень: учебник для 11 класса / Н.Д.Угринович. – М.: Бином. Лаборатория знаний, 2010.
- Алгоритм Прима-Крускала (видео) http://www.youtube.com/watch?v=vm_9-vnV7PE
- Занимательные задачи по теории графов: Учеб.-метод. пособие/ О.И.Мельников. – Изд-е 2-е, стереотип. – Мн.: «ТетраСистемс», 2001
- Изображение деревенского дома http://www.diorama.com.ua/images/product_images/popup_images/2074_1.jpg
- Изображение связных деревьев http://xreferat.ru/image/54/1306491707_19.png
- выход
Информатика - еще материалы к урокам:
- Презентация "Относительные, абсолютные и смешанные ссылки в электронных таблицах" 9 класс
- Презентация "Создание простейшей веб-страницы. Работа в редакторе Блокнот"
- Презентация "Школа фиксиков. Информатика" 5 класс
- Презентация "Строки в Pascal" 9 класс
- Презентация "Информационные системы" 11 класс
- Презентация "Устройства ввода и вывода информации" 8 класс