← к оглавлению
MST и DSU — теория устных вопросов 14–17
Система непересекающихся множеств, минимальное остовное дерево, лемма о безопасном ребре, Прим, Крускал. Формулировки — по лекции курса.
14. Система непересекающихся множеств (DSU)
Что это
Структура для работы с набором непересекающихся множеств. Операции: Unite(a,b) — объединить множества a и b; AreSame(a,b) — лежат ли в одном множестве; FindSet(x) — представитель (корень) множества x.
Каждое множество хранится как подвешенное дерево, его представитель — корень. Объединение = подвесить один корень к другому. AreSame = сравнить представителей.
Две эвристики
Ранговая (весовая) эвристика: при объединении подвешиваем дерево с меньшим рангом (глубиной) или весом (размером) к большему.
Сжатие путей: при FindSet подвешиваем все вершины на пути к корню напрямую к корню.
Асимптотика
- Одна эвристика (любая) → O*(log N) на запрос.
- Обе вместе → O*(α(N)), где α — обратная функция Аккермана.
α(N) = min{k | A(k,k) ≥ N}. Для всех реальных N имеем α(N) ⩽ 4 (так как A(4,4) астрономически велико), но формально это не константа.
Спросят: определение α(N), почему обе эвристики дают почти константу, применение (Крускал, оффлайн-компоненты связности).
15. MST. Лемма о безопасном ребре
Определения
Остов графа G=(V,E) — подграф H=(V,E′), E′⊆E (те же вершины, часть рёбер).
Остовное дерево — остов, являющийся деревом.
MST — остовное дерево минимального суммарного веса.
Разрез ⟨S,T⟩: S∪T=V, S∩T=∅. Ребро (u,v) пересекает разрез, если u и v в разных долях.
Безопасное ребро
Пусть G′=(V,E′) — подграф некоторого MST. Ребро (u,v)∉E′ безопасно, если G′∪{(u,v)} тоже подграф некоторого MST.
Лемма. Если ни одно ребро E′ не пересекает разрез ⟨S,T⟩, а (u,v) — ребро минимального веса среди пересекающих разрез, то (u,v) безопасно для E′.
Доказательство (для устного)
Достроим E′ до некоторого MST T_min. Если (u,v)∈T_min — готово. Иначе рассмотрим путь из u в v в T_min: так как u и v в разных долях разреза, на пути есть ребро e′, пересекающее разрез. По условию w(u,v) ⩽ w(e′). Заменим e′ на (u,v): получим снова остовное дерево (связность сохранилась), вес не вырос → это тоже MST. Значит E′∪{(u,v)} достраивается до MST, ребро безопасно.
Спросят: смысл «некоторого MST», доказательство замены ребра, как из леммы следуют Прим и Крускал.
16. Алгоритм Прима
Идея
Растим одно дерево из S={s}. На каждом шаге рассматриваем разрез ⟨S, V∖S⟩, находим минимальное ребро через разрез (оно безопасно по лемме), добавляем его и новую вершину в S. Повторяем, пока S≠V.
Корректность — прямое следствие леммы о безопасном ребре: каждое добавляемое ребро безопасно.
Асимптотика
| Контейнер рёбер | Итого |
|---|
| Массив | O(|V|²) |
| Приоритетная очередь / TreeSet | O(|E| log|V|) |
| Фибоначчиева куча | O(|E| + |V| log|V|) |
Спросят: связь с Дейкстрой (та же структура, другой ключ релаксации — вес ребра, а не расстояние), выбор контейнера, когда O(|V|²) лучше (плотные графы).
17. Алгоритм Крускала
Идея
- Отсортировать рёбра по весу.
- Идти по возрастанию веса; ребро берём, если его концы в разных компонентах (не создаёт цикл), иначе пропускаем.
Проверка «в разных компонентах» — через DSU: добавление ребра = Unite, проверка цикла = AreSame.
Корректность: минимальное ребро, соединяющее две компоненты, безопасно (лемма, где разрез отделяет одну компоненту от остальных).
Асимптотика
O(|E| log|E|) на сортировку + O(|E|·α(|V|)) на DSU = O(|E| log|E|) (доминирует сортировка).
Спросят: роль DSU, почему сортировка доминирует, сравнение с Примом по плотности графа.
▶ интерактив: Крускал на точках (манхэттен)
Прим vs Крускал: оба строят MST, оба опираются на лемму о безопасном ребре. Прим растит одно дерево (хорош на плотных графах, особенно O(V²) массивом). Крускал сортирует все рёбра и склеивает компоненты через DSU (хорош на разреженных графах). На экзамене полезно уметь вывести оба из леммы.