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

Danger dungeon quest

Game: Perform tasks and rest cool.11 people play!

Play game

Привет, сегодня поговорим про остовные деревья минимальной стоимости, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое остовные деревья минимальной стоимости , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Пусть G — (V, Е) — связный граф, в котором каждое ребро (v, w) помечено числом c(v, w), которое называется стоимостью ребра. Остовным деревом графа G называется свободное дерево, содержащее все вершины V графа G. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево. В этом разделе мы рассмотрим методы нахождения остовных деревьев минимальной стоимости.

Минимальное остовное дерево связного графа 
(ребра минимального остовного дерева отдельно выделены цветом)

Приведенное дерево не единственное: удалив ребро (b, с) и заменив его ребром (a, h), мы получим другое остовное дерево с тем же весом 37.

В этой главе мы рассмотрим два алгоритма решения задачи поиска минимального остовного дерева —алгоритм Крускала (Kruskal) и алгоритм Прима (Prim). Об этом говорит сайт https://intellect.icu . Каждый из них легко реализовать с помощью обычных бинарных пирамид, получив время работы О (E*lgV). При использовании фибоначчиевых пирамид алгоритм Прима можно ускорить до O (Е + V * lgV), что является весьма существенным ускорением при |V|<<|E|.

Оба эти алгоритма — жадные. На каждом шаге алгоритма мы выбираем один из возможных вариантов. Жадная стратегия предполагает выбор варианта, наилучшего в данный момент. В общем случае такая стратегия не гарантирует глобально оптимального решения задачи, однако для задачи поиска минимального остовного дерева можно доказать, что определенные жадные стратегии дают нам остовное дерево минимального веса.

На этом все! Теперь вы знаете все про остовные деревья минимальной стоимости, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое остовные деревья минимальной стоимости и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов