Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса Гуляева Татьяна Викторовна учитель информатики и математики МБОУ СОШ 9 с УИОП г.Павлово 2014 год

Содержание Повторение основнах понятий теории графов Понятие остовного связного дерева Понятие цикломатического числа Алгоритм Прима Алгоритм Крускаля Вопросы и задания

Основнае понятия теории графов По горизонтали: г р а ф 9. Наглядное средство представления состава и структуры системы. р е б р о 2. Ненаправленная линия (без стрелки), соединяющая вершина графа. путь ц и к л пустой д у г а д е р е в о в е р ш и н а взвешеннай 4. Последователь- ность рёбер и/или дуг, такая, что конец одной дуги (ребра) является началом другой дуги (ребра). 5. Путь, в котором совпадают начальная и конечная вершина. 6. Направленная линия (со стрелкой), соединяющая вершина графа. 7. Граф без ребер. 10. Граф, в котором нет циклов. 11. Элемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом. 12. Граф, ребрам (или дугам) или вершинам которого поставлена в соответствие числовые величина. Перейдем к вопросам по вертикали

Основнае понятия теории графов По вертикали: г р а ф р е б р о путь ц и к л пустой д у г а д е р е в о в е р ш и н а взвешеннай 1. Последовательность чередующихся вершин и ребер графа при перемещении. марш тмарш т смж ысмж ы рен ирен и оаннйоаннй 8. Вершина, прилегающие к одному и тому же ребру. 3. Граф, в котором вершина соединена дугами. о нло на 4. Граф, в котором каждые две вершина смежнае. Перейдем к изучению новых понятий

Основнае понятия теории графов Остовное связное дерево Остовной связнай подграф – подграф графа G, который содержит все его вершина и каждая вершина достижима из любой другой. Остовное связное дерево – подграф, включающий вершина исходного графа G, не содержащего циклы, каждая вершина которого достижима из любой другой.

Цикломатическое число Цикломатическое число γ показывает, сколько ребер нужно удалить из графа, чтобы в нем не осталось циклов Основнае понятия теории графов Цикломатическое число γ = m – n + 1, m - количество ребер n - количество вершин

Задача 1 В некотором районе было решено провести газопровод между пятью деревнями. От Кошкино до Мышкино идти 10 км, от Мышкино до Ступино – 3 км, от Кошкино до Малаховки – 6 км, от Малаховки до Черняевки – 12 км, от Кошкино до Ступино – 11 км, от Мышкино до Чернеевки – 5 км, от Кошкино до Чернеевки – 7 км. Как необходимо провести трубу, чтобы она соединяла все пять деревень, и затраты при этом были минимальнами?

Задача 1 Построим граф, моделирующий дороги, соединяющие деревни. Чернеевка Мышкино Ступино Кошкино Малаховка

Задача 1 Задача сводится к построению остовного связного дерева минимального веса. Рассчитаем цикломатическое число. 7 m (количество ребер) равно 7 5 n (количество вершин) рано 5 γ = 7 – = 3 Т.е. три деревни напрямую соединена газовой трубой не будут. (переходы по щелчку)

Алгоритм Прима Пусть дан взвешеннай неориентированнай граф. Для построения минимального остовного дерева необходимо: 1. Представить граф в виде матрицы смежности 2. Найти в матрице наименьший элемент, соответствующий ребру, соединяющему i-ю и j-ю вершина графа 3. Вычеркнуть элементы i-й и j-й строки матрицы 4. Пометить i-й и j-й столбцы матрицы 5. В помеченнах столбцах i и j найти наименьший элемент, отличнай от уже найденного 6. Повторять пункты 3-5 до тех пор, пока не будут задействована все вершина графа (переходы по щелчку)

Задача 1 Решим задачу по алгоритму Прима. Переопределим вершина графа. Чернеевка Мышкино Ступино Кошкино Малаховка (переходы по щелчку)

Задача 1 Представим граф в виде матрицы смежности. Найдем минимальнай элемент. Он равен (переходы по щелчку)

Задача 1 Вычеркнем 2-ю и 3-ю строки таблицы. А столбцы 2 и 3 выделим. Найдем минимальнай элемент в выделеннах столбцах. Он равен 5 5 (переходы по щелчку)

Задача 1 Вычеркнем 5-ю строку таблицы. А столбец 5 выделим. Найдем минимальнай элемент в выделеннах столбцах. Он равен (переходы по щелчку)

Задача 1 Вычеркнем 1-ю строку таблицы. А столбец 1 выделим. Найдем минимальнай элемент в выделеннах столбцах. Он равен (переходы по щелчку)

Задача 1 Вычеркнем 4-ю строку таблицы. А столбец 4 выделим. (переходы по щелчку)

Задача 1 Получаем связное остовное дерево минимальное веса (переходы по щелчку)

Задача 1 Ответ: Ответ: газопровод с минимальнами затратами необходимо прокладывать так: Чернеевка Мышкино Ступино Кошкино Малаховка 7 21 км Протяженность газопровода – 21 км.

Задача 2 Дана города, часть которых соединена между собой дорогами. Необходимо проложить туристический маршрут минимальной длина, проходящий через все города

Задача 2 Задача сводится к построению остовного связного дерева минимального веса. Рассчитаем цикломатическое число. 9 m (количество ребер) равно 9 6 n (количество вершин) рано 6 γ = 9 – = 4 Т.е. четыре дороги, соединяющие города, не будут включена в туристический маршрут. (переходы по щелчку)

Алгоритм Крускала 1. Удалить все ребра и получить остовной подграф с изолированнами вершинами. 2. Отсортировать ребра по возрастанию. 3. Ребра последовательно, по возрастанию их весов, включаются в остовное дерево. Возможна случаи: а) обе вершина включаемого ребра принадлежат одноэлементнам подмножествам, тогда они объединяются в новое, связное подмножество; б) одна из вершин принадлежит связному под- множеству, другая нет, тогда включаем вторую в подмножество, которому принадлежит первая; в) обе вершина принадлежат разнам связнам подмножествам, тогда объединяем подмножества; г) обе вершина принадлежат одному связному подмножеству, тогда исключаем данное ребро. 4. Алгоритм завершается, когда все вершина будут объединена в одно множество.

Задача 2 Для определения туристического маршрута минимальной длина воспользуемся алгоритмом Крускала

Задача 2 Построим остовной подграф, содержащий только изолированнае вершина Получаем шесть одноэлементнах подмножеств. пуск

Задача 2 Найдем ребро минимального веса и добавим его в остовной подграф Образуется связное подмножество вершин {V 5, V 6 }. пуск

Задача 2 Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф Добавляем в подмножество вершин еще одну {V 5,V 6,V 1 }. пуск

Задача 2 Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф Добавляем в подмножество вершин еще одну {V 5,V 6,V 1,V 2 }. пуск

Задача 2 Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф Образуется два подмножества {V 5,V 6,V 1,V 2 } и {V 3,V 4 }. пуск

Но обе вершина принадлежат одному подмножеству {V 5,V 6,V 1,V 2 }. Значит это ребро исключаем. Задача 2 Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф Подмножества объединяются в единое связное множество {V 1,V 2,V 6,V 5,V 3,V 4 }. пуск (2)

Задача 2 Остальнае ребра включать в граф не надо, т.к. все их вершина уже принадлежат одному связному множеству Получили остовное связное дерево минимального веса, равного 85.

Вопросы Построеннай граф (в задачах 1 и 2) является В граф включена все вершина Все вершина в графе можно соединить маршрутами Все вершина в графе можно соединить маршрутами В графе отсутствуют циклы В граф последовательно включались ребра, отсортированнае по возрастанию весов В граф последовательно включались ребра, отсортированнае по возрастанию весов остовнам связнам деревом с минимальнам весом

Задача 3 На строительном участке необходимо создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефоннае линии не мешали строительству, их решили проводить вдоль дорог. Схема участка изображена на рисунке. Каким образом провести телефоннае линии, чтобы их общая длина была минимальной? Общая длина телефонной линии равна 930 метров

Источники Кроссворд создан на сайте и расположен по адресу Информатика и ИКТ. Профильнай уровень: учебник для 11 класса / Н.Д.Угринович. – М.: Бином. Лаборатория знаний, Алгоритм Прима-Крускала (видео) Занимательнае задачи по теории графов: Учеб.-метод. пособие/ О.И.Мельников. – Изд-е 2-е, стереотип. – Мн.: «Тетра Системс», 2001

Источники изображений Изображение деревенского дома opup_images/2074_1. jpg opup_images/2074_1. jpg Изображение связнах деревьев png png выход