№11. Решение задачи построения остовного дерева минимального веса с использованием алгоритмов Прима и Краскала

Цель: научить строить остовное дерево минимального веса.

Оборудование: практикум, тетрадь для лабораторных и практических работ.

Литература:

1. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1979. С. 11-28, 158-166.
2. Новиков Ф. А. Дискретная математика для программистов. - СПб.: Питер, 2000. С. 189-209, 255-259.
3. Таха, Хемди. Введение в исследование операций - М.: Издательский дом "Вильямс", 2005. С. 243-250.

Время выполнения: 2 часа.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Дайте определение графа, приведите примеры.
2. Дайте определение дерева, приведите примеры.
3. Дайте определение остовного дерева графа, приведите примеры.
4. Дайте определение минимального остовного дерева графа.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:

Граф называется деревом, если он является связным и не имеет циклов.

Остовом связного графа называется любой его подграф, содержащий все вершины графа и являющийся деревом.

Остовное дерево связного нагруженного графа с минимальной суммой длин содержащихся в нем ребер, называется минимальным остовным деревом графа.

Алгоритм Краскала

1) начать с несвязного графа Т, множество вершин которого идентично множеству вершин искомого графа G;

2) упорядочить ребра графа G в порядке неубывания их весов;

3) начав с первого ребра в списке, добавлять ребра в граф Т, причем добавление ребра не должно приводить к появлению циклов;

4) выполнять пункт 3 до тех пор пока в графе Т не останется изолированных вершин.

Полученный граф Т является минимальным остовным деревом графа G.

Алгоритм Прима

1) пусть минимальное остовное дерево Т состоит из одной произвольно выбранной вершины;

2) для каждой вершины у_i, не принадлежащей остовному дереву, найти смежную с ней вершину х_i, принадлежащую остовному дереву, вес ребра r_i до которой минимален, и приписать вершине у_iпометку (х_i, r_i). Если таких вершин х_i нет, то приписать вершине у_i пометку (0, ∞);

3) выбрать вершину у_i* с минимальной пометкой r_i, присоединить ее к минимальному остовному дереву через вершину х_i. Если все вершины графа G занесены в минимальное остовное дерево Т, то остановиться, иначе перейти к следующему шагу алгоритма;

4) для всех вершин у_i, смежных с вершиной у_i*, обновить пометки, если текущая пометка r_i больше расстояния с_i от у_i до у_i*. Новая пометка будет иметь вид (у_i*, с_i). Перейти к шагу 3.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

1. Построить для заданного графа минимальное остовное дерево, используя алгоритм Краскала

Решение.

2. Построить для заданного графа минимальное остовное дерево, используя алгоритм Прима

Решение.

СОДЕРЖАНИЕ РАБОТЫ:

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Дайте определение графа, приведите примеры.
2. Дайте определение дерева, приведите примеры.
3. Дайте определение остовного дерева графа, приведите примеры.
4. Дайте определение минимального остовного дерева графа.
5. Опишите алгоритм Краскала.
6. Опишите алгоритм Прима.

ДОМАШНЕЕ ЗАДАНИЕ:

Выучить алгоритм Краскала; алгоритм Прима.