Цели урока: разобрать алгоритм Крускала для поиска в графе остовного связанного дерева минимального веса.
Тип урока: изучение нового материала.
Средства и оборудование: компьютер, презентация
ХОД УРОКА
1. Проверка домашнего задания в форме фронтального опроса (Приложение 1)
2. Изучение нового материала
– Сегодня на уроке мы разберем алгоритм,
предназначенный для поиска остовного связанного
дерева минимального веса, на примеры реальной
задачи.
Задача (Слайд 2).
Формализуем задачу, представим ее в виде графа G =
(V, R) – связанный взвешенный неориентированный
граф, где V – множество вершин, а R – множество
ребер (Слайд 3).
Вопрос: сколько ребер можно удалить из
этого графа, чтобы получить остовое связанное
дерево?
Ответ: Четыре ребра. Например, 2-3; 2-5; 6-7; 2-8 –
это ребра, которые образуют циклы.
Можно удалить и другие ребра. Но максимальное
количество удаляемых ребер величина постоянная
и зависит от количества вершин и ребер графа. Это
величина получила название цикломатического
числа.
Цикломатическое число показывает,
сколько ребер графа нужно удалить, чтобы в нем не
осталось ни одного цикла (Слайд 4).
Для нашего графа (Слайд 5):
В результате удаления части ребер мы можем получить различные связанные остовные деревья (Слайд 6).
Теперь рассмотрим нашу задачу с конкретными данными, т.е. введем длину дорог соединяющих различные города (Слайд 7).
Представим этот граф с помощью матрицы смежности, в которой между городами которые не соединены напрямую, введем бесконечно большое число, в условиях нашей задачи хватит 10000 (Слайд 8).
Для построения остовного связанного дерева минимального веса используется алгоритм Крускала.
- Первоначально из графа удаляются все ребра. Каждая вершина такого графа помещается в одноэлементное подмножество.
- Ребра сортируются по возрастанию весов.
- Ребра последовательно, по возрастанию их весов, включаются в остовное дерево.
- Алгоритм заканчивают работу, когда все вершины будут объединены в одно множество, при этом оставшиеся ребра не включаются в остовное дерево.
Реализация на компьютере.
Шаг 1. Все вершины графа помещаются в отдельный массив и перекрашиваются (нумеруются) в разные цвета (номера) (Слайд 9).
Шаг 2. В матрице смежности выбираем самое короткое ребро (Слайд 10).
Шаг 3. Если найденное ребро соединяет вершины разных цветов, добавляем его вес к весу остовного дерева и перекрашиваем вершины разного цвета в один цвет (Слайд 11, Слайд 12).
Шаг 4. Если не все вершины добавлены, переходим к Шагу 2.
Таким образом, на каждом шаге мы выбираем
наименьшее ребро, т.е. находим лучший для нас
результат. Алгоритмы с таким методом решения
называются жадные.
Для демонстрации работы алгоритма просматриваем
слайды презентации с 13 по 41, в автоматическом
режиме.
3. Домашняя работа прочитать по учебнику стр. 116-19, написать алгоритм Крускала на алгоритмическом языке или в виде псевдокода.
4. Итог урока в виде фронтального опроса
Вопрос: Зачем в матрице смежности графа
добавляются очень большие числа?
Ответ: Это нужно для того, чтобы можно было
найти минимальное ребро.
Вопрос: Какую роль играет вспомогательный
массив С(8)?
Ответ: В нем хранятся цвета вершин.
Вопрос: Какая общая идея лежит в алгоритме
Крускала?
Ответ: На каждом шаге мы находим минимальное
неиспользованное ребро.
Вопрос: Как называются алгоритмы,
использующие такую идею решения задач?
Ответ: Такие алгоритмы называются жадными.
Вопрос: Когда алгоритм закончит работу?
Ответ: Когда будут рассмотрены все вершины,
и они будут объединены в одно дерево, т.е. будут
иметь один цвет.
5. Выставление оценок