Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса

Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса

Содержание

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

Основные понятия теории графов Остовное связное дерево

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

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

Основные понятия теории графов Цикломатическое число

Цикломатическое число γ показывает, сколько ребер нужно удалить из графа, чтобы в нем не осталось циклов

γ = m – n + 1 ,

m - количество ребер

n - количество вершин

Задача 1

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

12

7

11

3

6

5

Задача 1

Построим граф, моделирующий дороги, соединяющие деревни.

Малаховка

Чернеевка

10

Кошкино

Мышкино

Ступино

Задача 1

Задача сводится к построению остовного связного дерева минимального веса.

Рассчитаем цикломатическое число.

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

11

12

3

7

6

5

11

3

6

5

Задача 1

Решим задачу по алгоритму Прима.

Переопределим вершины графа.

4

5

Малаховка

Чернеевка

10

10

2

1

Кошкино

Мышкино

3

Ступино

(переходы по щелчку)

12

7

11

3

6

5

Задача 1

Представим граф в виде матрицы смежности.

4

5

1

1

0

2

2

10

3

10

3

11

11

4

4

0

5

5

6

6

3

3

7

0

7

0

0

5

5

0

0

0

0

0

12

12

0

3

10

3

1

2

3

Найдем минимальный элемент.

Он равен 3

(переходы по щелчку)

Задача 1

Вычеркнем 2-ю и 3-ю строки таблицы. А столбцы 2 и 3 выделим.

1

1

1

1

1

1

0

0

0

2

2

2

2

2

2

10

3

3

10

3

3

3

10

10

3

11

11

11

11

0

4

4

4

4

4

4

3

6

6

5

3

6

3

6

3

5

6

6

5

5

5

5

7

7

0

7

7

7

7

0

0

0

0

5

0

0

0

0

5

5

5

0

0

0

0

0

0

0

12

12

12

12

12

12

0

0

0

5

Найдем минимальный элемент в выделенных столбцах.

Он равен 5

(переходы по щелчку)

Задача 1

Вычеркнем 5-ю строку таблицы. А столбец 5 выделим.

1

1

1

1

0

0

2

2

2

2

3

10

3

3

3

10

11

11

4

4

4

4

6

6

5

6

3

5

6

5

5

3

7

7

7

0

0

0

5

0

5

0

0

0

12

12

12

0

7

5

Найдем минимальный элемент в выделенных столбцах.

Он равен 7

(переходы по щелчку)

Задача 1

Вычеркнем 1-ю строку таблицы. А столбец 1 выделим.

1

1

2

2

3

3

4

4

5

3

5

6

7

0

0

5

0

12

1

1

0

2

2

3

10

3

11

4

4

6

3

5

6

5

7

0

5

0

0

12

6

5

Найдем минимальный элемент в выделенных столбцах.

Он равен 6

(переходы по щелчку)

13

Задача 1

Вычеркнем 4-ю строку таблицы. А столбец 4 выделим.

1

1

2

2

3

3

4

4

5

5

3

6

7

0

5

0

0

12

1

1

2

2

3

3

4

4

5

3

6

5

7

5

(переходы по щелчку)

12

7

11

3

6

5

Задача 1

Получаем связное остовное дерево минимальное веса.

4

5

1

1

2

2

3

3

4

4

5

3

5

6

7

5

10

2

1

3

(переходы по щелчку)

7

7

3

6

3

5

6

5

Задача 1

Ответ: газопровод с минимальными затратами необходимо прокладывать так:

4

5

Малаховка

Чернеевка

2

1

Кошкино

Мышкино

3

Ступино

Протяженность газопровода – 21 км .

25

18

15

12

20

23

21

26

Задача 2

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

2

1

6

5

3

19

4

Задача 2

Задача сводится к построению остовного связного дерева минимального веса.

Рассчитаем цикломатическое число.

m (количество ребер) равно 9

n ( количество вершин ) рано 6

γ = 9 – 6 + 1 = 4

Т.е. четыре дороги, соединяющие города, не будут включены в туристический маршрут.

(переходы по щелчку)

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

• Удалить все ребра и получить остовной подграф с изолированными вершинами.
• Отсортировать ребра по возрастанию.
• Ребра последовательно, по возрастанию их весов, включаются в остовное дерево. Возможны случаи:

а) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество;

б) одна из вершин принадлежит связному под-множеству, другая нет, тогда включаем вторую в подмножество, которому принадлежит первая;

в) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества;

г) обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.

• а) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество; б) одна из вершин принадлежит связному под-множеству, другая нет, тогда включаем вторую в подмножество, которому принадлежит первая; в) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества; г) обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.

• Алгоритм завершается, когда все вершины будут объединены в одно множество.
• Алгоритм завершается, когда все вершины будут объединены в одно множество.

25

18

15

12

20

23

21

26

Задача 2

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

2

1

6

5

3

19

4

25

18

15

12

20

23

21

26

Задача 2

Построим остовной подграф, содержащий только изолированные вершины.

Получаем шесть одноэлементных подмножеств.

2

1

6

5

3

пуск

19

4

25

18

15

12

20

23

21

26

Задача 2

Найдем ребро минимального веса и добавим его в остовной подграф.

Образуется связное подмножество вершин {V 5 , V 6 } .

2

1

6

5

3

пуск

19

4

25

18

15

12

20

23

21

26

Задача 2

Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.

Добавляем в подмножество вершин еще одну {V 5 ,V 6 ,V 1 } .

2

1

6

5

3

пуск

19

4

25

18

15

12

20

23

21

26

Задача 2

Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.

Добавляем в подмножество вершин еще одну {V 5 ,V 6 ,V 1 ,V 2 } .

2

1

6

5

3

пуск

19

4

25

18

15

12

20

23

21

26

Задача 2

Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.

Образуется два подмножества {V 5 ,V 6 ,V 1 ,V 2 } и {V 3 ,V 4 } .

2

1

6

5

3

пуск

19

4

25

18

15

12

20

23

21

26

Задача 2

Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф.

Подмножества объединяются в единое связное множество {V 1 ,V 2 ,V 6 ,V 5 , V 3 ,V 4 } .

Но обе вершины принадлежат одному подмножеству {V 5 ,V 6 ,V 1 ,V 2 } . Значит это ребро исключаем.

2

пуск (2)

1

6

5

3

19

4

25

18

15

12

20

23

21

26

Задача 2

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

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

2

1

6

5

3

19

4

Вопросы

Построенный граф (в задачах 1 и 2) является

• остовным

В граф включены все вершины

• связным

Все вершины в графе можно

соединить маршрутами

• деревом

В графе отсутствуют циклы

• с минимальным весом

Ответ можно увидеть, щелкнув «мышью» по выделенным словам

В граф последовательно включались ребра,

отсортированные по возрастанию весов

Задача 3

260

210

180

100

210

100

100

100

150

200

150

200

170

380

170

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

2

2

1

1

3

3

240

6

6

5

5

4

4

Надпись «Ответ» - это триггер для отображения ответа задачи

7

7

Каким образом провести телефонные линии, чтобы их общая длина была минимальной?

Общая длина телефонной линии равна 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

выход