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

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

а ф
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 км. Как необходимо провести трубу, чтобы она соединяла все пять деревень, и затраты при этом были минимальными?

минимального веса.
Рассчитаем цикломатическое число.
m (количество ребер) равно 7
n

(количество вершин) рано 5
γ = 7 – 5 + 1 = 3

Т.е. три деревни напрямую соединены газовой трубой не будут.

остовного дерева необходимо:
1. Представить граф в виде матрицы смежности
2.

Найти в матрице наименьший элемент, соответству-ющий ребру, соединяющему i-ю и j-ю вершины графа

3. Вычеркнуть элементы i-й и j-й строки матрицы

4. Пометить i-й и j-й столбцы матрицы

5. В помеченных столбцах i и j найти наименьший элемент, отличный от уже найденного

6. Повторять пункты 3-5 до тех пор, пока не будут задействованы все вершины графа

элемент.
Он равен 3
3
3

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

столбцах.

Он равен 5

5

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

минимальный элемент в выделенных столбцах.
Он равен 6
5
Задача 1

газопровода – 21 км.
Задача 1

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

все города.

минимального веса.
Рассчитаем цикломатическое число.
m (количество ребер) равно 9
n

(количество вершин) рано 6
γ = 9 – 6 + 1 = 4

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

с изолированными вершинами.
Отсортировать ребра по возрастанию.
Ребра последовательно, по возрастанию

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

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

1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 1
Получаем шесть одноэлементных подмножеств.
пуск

в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 2
Образуется связное подмножество вершин {V5,

V6}.

пуск

и добавим его в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 3
Добавляем в

подмножество вершин еще одну {V5,V6,V1}.

пуск

и добавим его в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 4
Добавляем в

подмножество вершин еще одну {V5,V6,V1,V2}.

пуск

и добавим его в остовной подграф.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 5
Образуется два

подмножества {V5,V6,V1,V2} и {V3,V4} .

пуск

это ребро исключаем.
Задача 2
Среди оставшихся ребер найдем ребро минимального

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

1

6

5

2

3

4

25

18

15

12

20

23

21

19

26

Шаг 6

Подмножества объединяются в единое связное множество {V1,V2,V6,V5,V3,V4} .

пуск (2)

т.к. все их вершины уже принадлежат одному связному множеству.

1

6

5

2

3

4

25

18

15

12

20

23

21

19

26

Итог

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

граф включены все вершины
Все вершины в графе можно
соединить

маршрутами

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

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

остовным

связным

деревом

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

соединяющую все бытовки. Для того, чтобы телефонные линии не

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

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

Ответ

Общая длина телефонной линии равна 930 метров