Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


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

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

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

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

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

Минимальные остовные деревьяЗадача: в процессе разработке электронных схем необходимо получит такую компоновку из n-1 проводов, которая использует минимальное количество провода. Дан некий связный неориентированный граф G=(V,E), где V- множество контактов, Е- множество возможных соединений
Минимальные остовные деревья. Алгоритмы Крускала и Прима.Работу выполнил Студент группы И-2-10Бекиров Алим Минимальные остовные деревьяЗадача: в процессе разработке электронных схем необходимо получит такую компоновку Минимальные остовные деревьяНеобходимо найти ациклическое подмножество T , которое соединяет все вершины Минимальные остовные деревья Алгоритм КрускалаАлгоритм Крускала предназначен для нахождения безопасного ребра для добавления в растущий Алгоритм Крускала Алгоритм Прима Аналогично алгоритму Крускала. Построение дерева начинается с произвольной корневой вершиной Алгоритм Прима Спасибо за внимание!
Слайды презентации

Слайд 2 Минимальные остовные деревья
Задача: в процессе разработке электронных схем

Минимальные остовные деревьяЗадача: в процессе разработке электронных схем необходимо получит такую

необходимо получит такую компоновку из n-1 проводов, которая использует

минимальное количество провода.
Дан некий связный неориентированный граф G=(V,E), где V- множество контактов, Е- множество возможных соединений между парами контактов, и для каждого ребра (u,v)ЭЕ задан вес w(u,v), определяющий стоимость ( количество необходимого провода)соединения u и v.


Слайд 3 Минимальные остовные деревья
Необходимо найти ациклическое подмножество T ,

Минимальные остовные деревьяНеобходимо найти ациклическое подмножество T , которое соединяет все

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

Остовным

деревом(spanning tree)- называется множество Т, которое ациклично и связывает все вершины, при этом данное дерево имеет минимальный вес.
Задачей поиска минимального остовного дерева (minimum spanning tree problem)называют задачей поиска дерева Т.

Слайд 4 Минимальные остовные деревья

Минимальные остовные деревья

Слайд 5 Алгоритм Крускала
Алгоритм Крускала предназначен для нахождения безопасного ребра

Алгоритм КрускалаАлгоритм Крускала предназначен для нахождения безопасного ребра для добавления в

для добавления в растущий лес путем поиска ребра (u,

v) с минимальным весом среди всех ребер, соединяющий два дерева в лесу.
Данный алгоритм является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимально возможным весом.
Время работы алгоритма O(E lg V).

Слайд 6 Алгоритм Крускала

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

Слайд 9 Алгоритм Прима
Аналогично алгоритму Крускала. Построение дерева начинается

Алгоритм Прима Аналогично алгоритму Крускала. Построение дерева начинается с произвольной корневой

с произвольной корневой вершиной r и растет до

тех пор пока не охватит все вершины в V. На каждом шаге к дереву А добавляется легкое ребро, соединяющие дерево и отдельную вершину из оставшейся части графа.
Время работы алгоритма O(E+ V lg V).

Слайд 10 Алгоритм Прима

Алгоритм Прима

  • Имя файла: minimalnye-ostovnye-derevya-algoritmy-kruskala-i-prima.pptx
  • Количество просмотров: 111
  • Количество скачиваний: 0