Содержание
- 2. МИНИМАЛЬНАЯ БАЗА РЕБЕР Содержательная постановка задачи: на связном взвешенном неориентированном графе G(X,U) выделить подмножество ребер таких,
- 3. ПРИМЕР 1 Исходный граф G(X,U) Граф G(X,U’) 1 2 3 4 5 1 3 5 2
- 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,
- 9. Скачать презентацию