Задача и алгоритм Прима - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Задача и алгоритм Прима. Доклад-сообщение содержит 8 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ЗАДАЧА И АЛГОРИТМ ПРИМА

Слайд 2

Описание слайда:

МИНИМАЛЬНАЯ БАЗА РЕБЕР Содержательная постановка задачи: на связном взвешенном неориентированном графе G(X,U) выделить подмножество ребер таких, что: 1. Граф G(X,U’) является связным. 2. Суммарный вес ребер подмножестваU’ является минимальным. Определение: связным называется граф, между любой парой вершин которого существует маршрут.

Слайд 3

Описание слайда:

ПРИМЕР 1 Исходный граф G(X,U)

Слайд 4

Описание слайда:

Формальная постановка задачи

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Пример 2

Слайд 7

Описание слайда:

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