Борувка, единственность и что ещё даёт остов

Коротко

Третий способ применить свойство разреза - алгоритм Борувки, исторически первый (1926 год): на каждой фазе КАЖДАЯ компонента одновременно выбирает своё самое лёгкое исходящее ребро, и все выбранные рёбра добавляются разом. Число компонент за фазу уменьшается минимум вдвое, значит фаз не больше log₂ V, а цена - O(E·log V). Главное его достоинство - независимые выборы, то есть естественная параллельность; на нём строят распределённые и GPU-реализации. Заодно в этом уроке закрываются два вопроса: когда МОД ЕДИНСТВЕННО (когда все веса различны) и что ещё из него вытаскивают - кластеризацию, приближение коммивояжёра и «самый тяжёлый участок» маршрута.

Если ты знаешь фазы Борувки и оценку log V, помнишь критерий единственности МОД и связь остова с кластеризацией, листай до «Теперь сам».

Как думаешь, можно ли выбирать рёбра одновременно

Прим и Крускал строго последовательны: каждое решение опирается на предыдущие. Прежде чем читать дальше, подумай: а нельзя ли позволить всем компонентам выбирать рёбра ОДНОВРЕМЕННО - и не получится ли при этом цикл?

На что это похоже

Разрозненные деревни, каждая из которых сама тянет дорогу к ближайшему соседу. Никто ни с кем не согласовывает - и всё равно получается связная сеть без лишних дорог. Раз каждая деревня подключилась хотя бы к одной другой, групп стало вдвое меньше; повторили - ещё вдвое. Через десяток раундов из тысячи деревень остаётся одна сеть.

Механизм: фазы Борувки

пока компонент больше одной:
    для КАЖДОЙ компоненты найти самое лёгкое исходящее ребро
    добавить все найденные рёбра разом
    пересчитать компоненты (union-find)

Каждое выбранное ребро законно по свойству разреза: разрез «эта компонента против всего остального», ребро - самое лёгкое из пересекающих.

Почему фаз не больше log₂ V. В каждой фазе каждая компонента присоединяется хотя бы к одной другой, значит компоненты сливаются группами не меньше двух: их число уменьшается минимум вдвое. От V до одной - не больше log₂ V шагов. Каждая фаза - проход по всем рёбрам, отсюда O(E·log V).

Ловушка равных весов. Если два ребра одного веса, две компоненты могут выбрать «друг друга» по-разному и создать цикл. Лечится правилом разрыва ничьих: рёбра нумеруют в том порядке, в котором они лежат во входных данных (номер ребра - это просто его индекс в списке edges), и сравнивают не вес, а ПАРУ (вес, номер). В Python это буквально if (w, i) < (best_w, best_i) - пары сравниваются по первому элементу, а при равенстве по второму. Правило одинаково для всех компонент, поэтому выбор согласован и циклов не возникает.

Единственность МОД. Если ВСЕ веса различны, минимальное остовное дерево единственно - это прямое следствие свойства разреза со строгим неравенством (мы доказали его в первом уроке этой главы). Если равные веса есть, деревьев может быть несколько, но их СУММАРНЫЙ ВЕС одинаков, и любой из алгоритмов даёт правильный ответ.

Правило

Борувка: пока компонент больше одной, каждая выбирает своё самое лёгкое исходящее ребро, и все выбранные добавляются одновременно; число компонент падает минимум вдвое за фазу, значит фаз <= log₂ V, а цена O(E·log V). Выборы независимы - алгоритм естественно параллелится. При равных весах нужно единое правило разрыва ничьих, иначе возможен цикл. Если все веса различны, МОД единственно; при равных весах деревьев может быть несколько, но суммарный вес у них одинаков.

Разбор: одна фаза Борувки

Граф: a-b = 1, c-d = 2, b-c = 3, a-d = 4.

Фаза 1. Каждая вершина - своя компонента, и каждая выбирает самое лёгкое своё ребро:

a: самое лёгкое a-b (1)
b: самое лёгкое a-b (1)     ← то же ребро, добавится один раз
c: самое лёгкое c-d (2)
d: самое лёгкое c-d (2)     ← то же ребро

Добавили a-b и c-d. Компонент стало две: {a, b} и {c, d} - было четыре, стало две, ровно вдвое меньше.

Фаза 2. Компонента {a, b} смотрит свои исходящие рёбра: b-c (3) и a-d (4) - выбирает b-c (3). Компонента {c, d} смотрит: b-c (3) и a-d (4) - выбирает то же b-c (3). Добавляем его один раз. Компонента одна - готово.

Итог: a-b, c-d, b-c, вес 1 + 2 + 3 = 6; ребро a-d (4) не вошло. Двух фаз хватило на четыре вершины - как и обещает log₂ 4 = 2.

Разбор: что ещё вытаскивают из остова

Кластеризация. Построй МОД и выброси k − 1 самых тяжёлых рёбер - граф распадётся на k кусков, и это в точности иерархическая кластеризация методом ОДИНОЧНОЙ СВЯЗИ. Метод такой: расстоянием между двумя группами объектов считают расстояние между их САМЫМИ БЛИЗКИМИ представителями (одна связь - отсюда название), и шаг за шагом сливают две ближайшие группы. Это в точности Крускал: он тоже каждым шагом соединяет два ближайших куска. Число кластеров k задаёшь ты сам - сколько рёбер выбросил, столько и получил частей; удобно смотреть на веса выброшенных рёбер: если очередное резко тяжелее предыдущих, на нём и стоит остановиться. Смысл понятен: МОД соединял всё самыми дешёвыми связями, а самые дорогие из них - как раз «мосты между далёкими группами».

Приближение коммивояжёра. Обойди МОД в глубину, выписывая вершины в порядке первого посещения, - получится маршрут не длиннее двойного оптимального (для метрики с неравенством треугольника). Почему: оптимальный маршрут без одного ребра - это остовное дерево, значит w(МОД) <= OPT; обход дерева проходит каждое ребро дважды, то есть 2·w(МОД) <= 2·OPT. Простая гарантия за линейную работу.

Минимаксные пути. В МОД путь между двумя вершинами минимизирует САМОЕ ТЯЖЁЛОЕ ребро на пути - то самое «узкое место» из главы про Флойда. Читается это так: если вес ребра - ПЛАТА (высота подъёма, крутизна, износ), минимальный остов отвечает на вопрос «каким маршрутом худший участок будет самым лёгким».

Сразу оговорка, чтобы не перепутать знак. Вопрос «какой МАКСИМАЛЬНЫЙ груз можно провезти» - другой: там вес ребра это пропускная способность, и надо максимизировать МИНИМУМ по пути. Он решается зеркально - МАКСИМАЛЬНЫМ остовным деревом (тот же Крускал, но рёбра сортируются от тяжёлых к лёгким), и путь в нём максимизирует самое слабое звено. Правило запомнить просто: минимальный остов минимизирует максимум, максимальный - максимизирует минимум. Оба случая закрываются ОДНИМ остовом на весь граф, а не отдельным вычислением для каждой пары.

Что ломается без этого

Первое: в Борувке не разрывать ничьи одинаковым правилом - при равных весах появятся циклы, и дерево перестанет быть деревом. Второе: считать, что Борувка быстрее Прима и Крускала - на обычном последовательном коде она сопоставима; её сила в параллельности. Третье: думать, что МОД единственно всегда: равные веса дают несколько деревьев с одинаковым весом. Четвёртое: применять трюк с кластеризацией, не проверив смысл задачи: одиночная связь чувствительна к «цепочкам» - две далёкие группы, соединённые редкой цепочкой точек, сольются в один кластер. Пятое: ждать от обхода МОД оптимального маршрута коммивояжёра - гарантия только «не хуже двукратного», и это в метрическом случае.

Зачем это в работе

Борувка - основа параллельных и распределённых алгоритмов МОД: выборы независимы, поэтому фаза раскладывается по потокам, по узлам кластера или по ядрам видеокарты; современные библиотеки для больших графов используют именно её. Кластеризация через остов - рабочий инструмент в анализе данных и в обработке изображений (сегментация). Приближение коммивояжёра через МОД - классический пример «дешёвой гарантии»: точное решение NP-трудно, но двукратная оценка получается почти даром (а с дополнением паросочетанием - полуторакратная, это алгоритм Кристофидеса). А свойство минимаксных путей делает МОД ответом на целый класс вопросов про пропускную способность.

Теперь сам

Граф: 1-2 = 5, 2-3 = 1, 3-4 = 4, 4-1 = 2, 1-3 = 3. Проведи первую фазу Борувки: какие рёбра выберет каждая вершина и сколько компонент останется?

Ответ. Смотрим самое лёгкое ребро у каждой вершины. Вершина 1: её рёбра - 1-2 (5), 4-1 (2), 1-3 (3); самое лёгкое - 4-1 (2). Вершина 2: рёбра 1-2 (5), 2-3 (1); самое лёгкое - 2-3 (1). Вершина 3: рёбра 2-3 (1), 3-4 (4), 1-3 (3); самое лёгкое - 2-3 (1). Вершина 4: рёбра 3-4 (4), 4-1 (2); самое лёгкое - 4-1 (2).

Выбранные рёбра (каждое добавляется один раз): 4-1 и 2-3. Компоненты после фазы: {1, 4} и {2, 3} - было четыре, осталось две, ровно вдвое меньше, как и обещает оценка.

Фаза 2 (для проверки): компонента {1,4} смотрит исходящие рёбра 1-2 (5), 1-3 (3), 3-4 (4) - выбирает 1-3 (3). Компонента {2,3} смотрит те же рёбра и тоже выбирает 1-3 (3). Добавляем его один раз, остаётся одна компонента. Итог: МОД = {2-3, 4-1, 1-3}, вес 1 + 2 + 3 = 6; рёбра 1-2 (5) и 3-4 (4) не вошли - и это согласуется со свойством цикла: 1-2 самое тяжёлое в цикле 1-2-3-1, а 3-4 самое тяжёлое в цикле 1-3-4-1.

Главное

Борувка - третий способ применить свойство разреза и исторически первый алгоритм МОД: на каждой фазе КАЖДАЯ компонента одновременно выбирает своё самое лёгкое исходящее ребро, и все выбранные добавляются разом. Каждый выбор законен (разрез «компонента против остального»), число компонент падает минимум вдвое за фазу, поэтому фаз не больше log₂ V, а цена O(E·log V). Ценность алгоритма - независимость выборов: он естественно параллелится, и на нём строят распределённые и GPU-реализации. При равных весах обязательно единое правило разрыва ничьих (например, по номеру ребра), иначе компоненты выберут «друг друга» несогласованно и появится цикл. Если все веса различны, МОД единственно; при равных весах деревьев может быть несколько, но суммарный вес у них одинаков. Из остова вытаскивают и другое: выбросив k − 1 самых тяжёлых рёбер, получаем k кластеров (метод одиночной связи); обход МОД даёт маршрут коммивояжёра не хуже двукратного оптимума в метрическом случае; путь между вершинами в МОД минимизирует самое тяжёлое ребро (а МАКСИМАЛЬНЫЙ остов - максимизирует самое лёгкое, это вопрос про пропускную способность).