Задача о минимальном покрывающем дереве
Пусть имеется связный неориентированный граф G=(V,E), в котором V – множество контактов, а E – множество их возможных попарных соединений. Для каждого ребра графа (u,v) задан неотрицательный вес w(u,v) (длина провода, необходимого для соединения u и v).
Задача состоит в нахождении подмножества T Ì E, связывающего все вершины, для которого суммарный вес минимален
Такое подмножество T можно считать деревом (в любом цикле один из проводов можно удалить, не нарушая связности).
Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим (остовным) деревом графа.
Пример графа
Покрывающее дерево графа
Почему задача о минимальном покрывающем дереве является упрощением реальной ситуации?
Алгоритмы Крускала и Прима решают задачу о минимальном покрывающем дереве различными способами.
Оба алгоритма следуют «жадной» стратегии: на каждом шаге выбирается «локально наилучший» вариант.
Доказано, что для данных алгоритмов жадный выбор приводит к оптимальному решению.