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

Содержание

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

Слайд 1Алгоритмы Прима и Крускала построения остовного связного дерева минимального веса
Гуляева
Татьяна Викторовна
учитель

информатики и
математики МБОУ СОШ №9
с УИОП г.Павлово

2014 год

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

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

Крускаля
Вопросы и задания


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

Слайд 3Основные понятия теории графов


По горизонтали:
г р а ф
9.

Наглядное сред-ство представления состава и структуры системы.  


р е б р о

2. Ненаправленная линия (без стрелки), соединяющая вершины графа.  

п у т ь

ц и к л

п у с т о й

д у г а

д е р е в о

в е р ш и н а

в з в е ш е н н ы й

4. Последователь-ность рёбер и/или дуг, такая, что конец одной дуги (ребра) является началом другой дуги (реб-ра).  


5. Путь, в котором совпадают начальная и конечная верши-ны.  


6. Направленная ли-ния (со стрелкой), соединяющая верши-ны графа.  


7. Граф без ребер.  

10. Граф, в котором нет циклов.  





11. Элемент (точка) графа, обозначаю-щий объект любой природы, входящий в множество объек-тов, описываемое графом.  


12. Граф, ребрам (или дугам) или вершинам которого поставлены в соот-ветствие числовые величины.  

Перейдем к вопросам по вертикали  


Основные понятия теории графов По горизонтали: г р  а ф9. Наглядное сред-ство представления состава и структуры

Слайд 4Основные понятия теории графов


По вертикали:
г р а ф


р

е б р о

п у т ь

ц и к л

п у с т о й

д у г а

д е р е в о

в е р ш и н а

в з в е ш е н н ы й








1. Последовательность чередующихся вершин и ребер графа при перемещении.  

м
а

ш
р

т

с
м

ж

ы




8. Вершины, прилега-ющие к одному и тому же ребру.  

3. Граф, в котором вершины соединены дугами.  

о

н
ы


4. Граф, в котором каждые две вершины смежные.  

Перейдем к изучению новых понятий


Основные понятия теории графов По вертикали: г р  а фр  е  б  р

Слайд 5Основные понятия теории графов Остовное связное дерево
Остовной связный подграф – подграф

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

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



Основные понятия теории графов Остовное связное дерево Остовной связный подграф – подграф графа G, который содержит все

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

в нем не осталось циклов

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


γ = m – n + 1,
m - количество ребер
n - количество вершин


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

Слайд 7Задача 1
В некотором районе было решено провести газопровод между пятью деревнями.

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


Задача 1В некотором районе было решено провести газопровод между пятью деревнями. От Кошкино до Мышкино идти 10

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

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

Слайд 9Задача 1
Задача сводится к построению остовного связного дерева минимального веса.
Рассчитаем цикломатическое

число.

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

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

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

Задача 1Задача сводится к построению остовного связного дерева минимального веса.Рассчитаем цикломатическое число.m (количество ребер) равно 7 n

Слайд 10Алгоритм Прима
Пусть дан взвешенный неориентированный граф.
Для построения минимального остовного дерева необходимо:
1.

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

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

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

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

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

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

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

Алгоритм ПримаПусть дан взвешенный неориентированный граф.Для построения минимального остовного дерева необходимо:1. Представить граф в виде матрицы смежности2.

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

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

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

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

Слайд 13Задача 1
Вычеркнем 2-ю и 3-ю строки таблицы. А столбцы 2 и

3 выделим.

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

Он равен 5


5

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

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

Слайд 14Задача 1
Вычеркнем 5-ю строку таблицы. А столбец 5 выделим.
Найдем минимальный элемент

в выделенных столбцах.

Он равен 7


5


7

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

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

Слайд 15Задача 1
Вычеркнем 1-ю строку таблицы. А столбец 1 выделим.
Найдем минимальный элемент

в выделенных столбцах.

Он равен 6


5

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

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

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

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

Слайд 17Задача 1
Получаем связное остовное дерево минимальное веса.
12
7
10
11
3
6
5
5
1
2
3
4
(переходы по щелчку)

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

Слайд 18Задача 1
Ответ: газопровод с минимальными затратами необходимо прокладывать так:


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

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

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

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


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

Слайд 20Задача 2
Задача сводится к построению остовного связного дерева минимального веса.
Рассчитаем цикломатическое

число.

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

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

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

Задача 2Задача сводится к построению остовного связного дерева минимального веса.Рассчитаем цикломатическое число.m (количество ребер) равно 9 n

Слайд 21Алгоритм Крускала
Удалить все ребра и получить остовной подграф с изолированными вершинами.
Отсортировать

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


Алгоритм КрускалаУдалить все ребра и получить остовной подграф с изолированными вершинами.Отсортировать ребра по возрастанию.Ребра последовательно, по возрастанию

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

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

Слайд 23Задача 2
Построим остовной подграф, содержащий только изолированные вершины.
1
6
5
2
3
4
25
18
15
12
20
23
21
19
26
Шаг 1
Получаем шесть

одноэлементных подмножеств.


пуск

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

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


1

6

5

2

3

4

25

18

15

12

20

23

21

19

26

Шаг 2

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


пуск

Задача 2Найдем ребро минимального веса и добавим его в остовной подграф. 165234251815122023211926Шаг 2Образуется связное подмножество вершин {V5,

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

в остовной подграф.

1

6

5

2

3

4

25

18

15

12

20

23

21

19

26

Шаг 3

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


пуск

Задача 2Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф. 165234251815122023211926Шаг 3Добавляем в

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

в остовной подграф.

1

6

5

2

3

4

25

18

15

12

20

23

21

19

26

Шаг 4

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


пуск

Задача 2Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф. 165234251815122023211926Шаг 4Добавляем в

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

в остовной подграф.

1

6

5

2

3

4

25

18

15

12

20

23

21

19

26

Шаг 5

Образуется два подмножества {V5,V6,V1,V2} и {V3,V4} .


пуск

Задача 2Среди оставшихся ребер найдем ребро минимального веса и добавим его в остовной подграф. 165234251815122023211926Шаг 5Образуется два

Слайд 28Но обе вершины принадлежат одному подмножеству {V5,V6,V1,V2}. Значит это ребро исключаем.
Задача

2

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

1

6

5

2

3

4

25

18

15

12

20

23

21

19

26

Шаг 6

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


пуск (2)

Но обе вершины принадлежат одному подмножеству {V5,V6,V1,V2}. Значит это ребро исключаем.Задача 2Среди оставшихся ребер найдем ребро минимального

Слайд 29Задача 2
Остальные ребра включать в граф не надо, т.к. все их

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

1

6

5

2

3

4

25

18

15

12

20

23

21

19

26

Итог


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


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

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


Почему?
В граф включены все

вершины

Все вершины в графе можно
соединить маршрутами

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

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

остовным

связным

деревом

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



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

Слайд 31Задача 3
На строительном участке необходимо создать телефонную сеть, соединяющую все бытовки.

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



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

Ответ

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

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

Слайд 32Источники
Кроссворд создан на сайте и расположен по адресу http://puzzlecup.com/?guess=3C2D4A01E0522AAU
Информатика и

ИКТ. Профильный уровень: учебник для 11 класса / Н.Д.Угринович. – М.: Бином. Лаборатория знаний, 2010.
Алгоритм Прима-Крускала (видео) http://www.youtube.com/watch?v=vm_9-vnV7PE
Занимательные задачи по теории графов: Учеб.-метод. пособие/ О.И.Мельников. – Изд-е 2-е, стереотип. – Мн.: «ТетраСистемс», 2001


ИсточникиКроссворд создан на сайте и расположен по адресу http://puzzlecup.com/?guess=3C2D4A01E0522AAU Информатика и ИКТ. Профильный уровень: учебник для 11

Слайд 33Источники изображений
Изображение деревенского дома http://www.diorama.com.ua/images/product_images/popup_images/2074_1.jpg
Изображение связных деревьев http://xreferat.ru/image/54/1306491707_19.png

выход

Источники изображенийИзображение деревенского дома http://www.diorama.com.ua/images/product_images/popup_images/2074_1.jpgИзображение связных деревьев http://xreferat.ru/image/54/1306491707_19.pngвыход

Что такое shareslide.ru?

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


Для правообладателей

Яндекс.Метрика

Обратная связь

Email: Нажмите что бы посмотреть