Задача и алгоритм Прима

Август 2, 2022

Главная
Математика
Задача и алгоритм Прима

Содержание

2. МИНИМАЛЬНАЯ БАЗА РЕБЕР Содержательная постановка задачи: на связном взвешенном неориентированном графе G(X,U) выделить подмножество ребер таких,
3. ПРИМЕР 1 Исходный граф G(X,U) Граф G(X,U’) 1 2 3 4 5 1 3 5 2
4. Формальная постановка задачи 1 2 3 4 2 5 3 9 4
5. Алгоритм Прима Шаг 1. Выбирается произвольная i-я вершина. Шаг 2. Выбирается инцидентное выбранной вершине ребро (i,p)
6. Пример 2 3 2 5 5 1 1 2 3 4 1 3 2 5 5
7. Достоинства и недостатки алгоритма Прима Достоинства: Гарантия получения глобально оптимального решения. Число итераций равно │Х│- 1,
8. САМОСТОЯТЕЛЬНО: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
9. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
10. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
11. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
12. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
13. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
14. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
15. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
16. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
17. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
18. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
19. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
20. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
21. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
22. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
23. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
24. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
25. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
26. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
27. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
28. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
29. Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного матрицей М:
31. Скачать презентацию

Слайд 2

МИНИМАЛЬНАЯ БАЗА РЕБЕР
Содержательная постановка задачи: на связном взвешенном неориентированном графе G(X,U)

выделить подмножество ребер
таких, что:
1. Граф G(X,U’) является связным.
2. Суммарный вес ребер подмножестваU’
является минимальным.
Определение: связным называется граф, между любой парой вершин которого существует маршрут.

Слайд 3

ПРИМЕР 1
Исходный граф G(X,U)
Граф G(X,U’)
1
2
3
4
5

1 3 5 2

4 7

6
3

1 3 2

Слайд 4

Формальная постановка задачи
1
2
3
4
2
5 3 9
4

Слайд 5

Алгоритм Прима
Шаг 1. Выбирается произвольная i-я вершина.
Шаг 2. Выбирается инцидентное

выбранной вершине ребро
(i,p) с минимальным весом.

Шаг 3. Ребро (i,p) запоминается, а вершины i-я и p-я
«стягиваются» в одну вершину.
Шаг 4. Вес «стянутого» ребра добавляется к ранее
накопленной сумме.
Шаг 5. Если образовались параллельные ребра, то из
них остается то, вес которого минимален, а
остальные удаляются.
Шаг 6. Если все вершины графа стянуты в одну, то
перейти к шагу 7, в противном случае – к
шагу 1.
Шаг 7. Конец алгоритма. «Стянуты» искомые ребра.

Слайд 6

Пример 2
3 2 5
5
1
1
2
3
4
1
3 2 5
5
1
2
3
4
1, 4
2
3
3 2

А) граф G(X,U) . B) U’=(1,4); R(U’)=1. C) U’={(1,4),(1,3)}; R(U’)=3.

1, 3, 4

1, 2, 3, 4

3 2

D) U’={(1,4),(1,3),(1,2)}; R(U’)=6. E) Конец алгоритма. F) Граф G(X,U’)

Слайд 7

Достоинства и недостатки алгоритма Прима
Достоинства:
Гарантия получения глобально оптимального решения.
Число итераций равно

│Х│- 1, где Х – множество вершин.
Простота и наглядность.
Недостаток:
Алгоритм применим только к неориентированным графам.

Слайд 8

САМОСТОЯТЕЛЬНО:
Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного

матрицей М:

Слайд 9

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 10

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№3 №4

Слайд 11

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№5 №6

Слайд 12

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№7 №8

Слайд 13

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 14

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 15

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 16

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 17

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 18

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 19

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 20

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 21

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 22

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№1 №2

Слайд 23

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№9 №10

Слайд 24

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№11 №12

Слайд 25

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№13 №14

Слайд 26

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№15 №16

Слайд 27

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№17 №18

Слайд 28

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№19 №20

Слайд 29

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

графа G(X,U), заданного матрицей М:
№21 №22

Задача и алгоритм Прима

Содержание

МИНИМАЛЬНАЯ БАЗА РЕБЕРСодержательная постановка задачи: на связном взвешенном неориентированном графе G(X,U)

ПРИМЕР 1Исходный граф G(X,U) Граф G(X,U’) 1 2 3 4 5

Формальная постановка задачи1234 2 5 3 9 4

Алгоритм ПримаШаг 1. Выбирается произвольная i-я вершина. Шаг 2. Выбирается инцидентное

Пример 23 2 5 51123413 2 5 512341, 4233 2

Достоинства и недостатки алгоритма ПримаДостоинства:Гарантия получения глобально оптимального решения.Число итераций равно

САМОСТОЯТЕЛЬНО: Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе: Пользуясь алгоритмом Прима, определить минимальную базу ребер

Похожие презентации

МИНИМАЛЬНАЯ БАЗА РЕБЕР
Содержательная постановка задачи: на связном взвешенном неориентированном графе G(X,U)

ПРИМЕР 1
Исходный граф G(X,U)
Граф G(X,U’)
1
2
3
4
5

Формальная постановка задачи
1
2
3
4
2
5 3 9
4

Алгоритм Прима
Шаг 1. Выбирается произвольная i-я вершина.
Шаг 2. Выбирается инцидентное

Пример 2
3 2 5
5
1
1
2
3
4
1
3 2 5
5
1
2
3
4
1, 4
2
3
3 2

Достоинства и недостатки алгоритма Прима
Достоинства:
Гарантия получения глобально оптимального решения.
Число итераций равно

САМОСТОЯТЕЛЬНО:
Пользуясь алгоритмом Прима, определить минимальную базу ребер графа G(X,U), заданного

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер

Задания к контрольной работе:
Пользуясь алгоритмом Прима, определить минимальную базу ребер