Конспект: минимальные остовные деревья

Понятия

Остовное дерево - подграф, который связывает все V вершин и не содержит циклов; в нём всегда V − 1 ребро. Минимальное остовное дерево (МОД) - остовное дерево наименьшего суммарного веса.

Разрез - разбиение вершин на две непустые части; рёбра разреза идут из одной части в другую.

Свойство разреза - самое лёгкое ребро через любой разрез входит в некоторое МОД.

Свойство цикла - самое тяжёлое ребро любого цикла можно не брать: МОД без него существует.

Что унести

свойство разреза, доказательство обменом:
  взяли МОД T без ребра e (лёгкое через разрез)
  добавили e         ->  появился ровно один цикл
  в цикле есть f     ->  тоже через этот разрез, w(f) >= w(e)
  выбросили f        ->  снова дерево, вес не больше  =>  T' - тоже МОД

Все три алгоритма - это свойство разреза, применённое к разным разрезам:

Крускалу нужен union-find: вопрос «концы уже связаны?» задаётся E раз, и обходом он стоил бы O(V + E) каждый. Борувка делает не больше log₂ V фаз - за фазу каждая компонента присоединяется хотя бы к одной другой, значит их число падает минимум вдвое.

МОД - не дерево кратчайших путей. Разница в одном слагаемом приоритета: best[u] = wt[j] даёт Прима, best[u] = best[v] + wt[j] даёт Дейкстру. Звезда с дорогим центром и дешёвой цепочкой разводит эти два дерева далеко.

При различных весах МОД единственно: неравенство w(f) >= w(e) в обмене становится строгим, и лёгкое ребро через любой разрез обязано входить в КАЖДОЕ МОД. При равных весах деревьев может быть несколько, но их суммарный вес один и тот же - и Борувке тогда нужно единое правило разрыва ничьих, иначе две компоненты выберут друг друга и появится цикл.

Бонусы остова: путь в МОД минимизирует самое тяжёлое ребро на пути (а МАКСИМАЛЬНЫЙ остов - максимизирует самое лёгкое: минимальный минимизирует максимум, максимальный максимизирует минимум); выбросив k − 1 самых тяжёлых рёбер, получим k кластеров (кластеризация одиночной связи); обход МОД даёт маршрут коммивояжёра не хуже двукратного оптимума в метрическом случае.

Тихие ошибки: считать, что МОД существует у несвязного графа (там остовный ЛЕС - по дереву на компоненту, и Крускал возьмёт меньше V − 1 ребра); не проверять в Крускале связность концов; разрывать ничьи в Борувке как попало; путать свойство цикла со свойством разреза.

Куда это ведёт

Следующая глава - конспект раздела, а дальше поток и паросочетания: там тоже «жадный шаг плюс доказательство, что он не портит оптимум», но уже с возможностью откатить сделанный выбор.