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

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

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

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

Остовным

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

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

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

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

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