Свойство разреза: одна теорема на все алгоритмы

Если ты умеешь доказать свойство разреза обменным аргументом, знаешь свойство цикла и понимаешь, почему из них следуют оба алгоритма, листай до «Теперь сам».

Как думаешь, какое ребро точно войдёт

Надо соединить V городов дорогами так, чтобы можно было доехать откуда угодно куда угодно, а суммарная длина дорог была наименьшей. Прежде чем читать дальше, ответь на вопрос поменьше: про КАКОЕ-НИБУДЬ ребро можно ли сказать наверняка, что оно войдёт в ответ? Подсказка: посмотри на самое лёгкое ребро при какой-нибудь вершине.

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

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

Механизм: остов, разрез и две теоремы

остовное дерево  - связный подграф без циклов, содержит все вершины, ровно V − 1 ребро
МОД              - остовное дерево наименьшего суммарного веса
разрез (S, V∖S)  - разбиение вершин на две непустые части
                   (V - МНОЖЕСТВО вершин, знак ∖ читается «без»:
                    V∖S - все вершины, кроме попавших в S)
ребро пересекает разрез, если его концы лежат в разных частях

Свойство разреза. Для любого разреза самое лёгкое пересекающее его ребро входит в некоторое минимальное остовное дерево. Если веса всех рёбер различны, оно входит в ЕДИНСТВЕННОЕ МОД - и само МОД единственно.

Свойство цикла. В любом цикле самое ТЯЖЁЛОЕ ребро не входит ни в одно МОД (если оно единственное самое тяжёлое). Это зеркальное утверждение, и из него растут алгоритмы «удаления»: выбрасывай самое тяжёлое ребро каждого цикла, пока не останется дерево.

Правило

Остовное дерево связывает все вершины и содержит ровно V − 1 ребро; минимальное - то, у которого суммарный вес наименьший. СВОЙСТВО РАЗРЕЗА: для любого разбиения вершин на две непустые части самое лёгкое ребро между частями входит в некоторое МОД (а при различных весах - в единственное). СВОЙСТВО ЦИКЛА: самое тяжёлое ребро любого цикла не входит ни в одно МОД. Алгоритмы Прима и Крускала - это два разных способа выбирать разрезы, и корректность обоих следует из первой теоремы.

Разбор: доказательство обменом

Пусть дан разрез (S, V∖S) и пусть e - самое лёгкое ребро, его пересекающее. Докажем, что e входит в некоторое минимальное остовное дерево.

Возьмём любое МОД T. Если e уже в нём - доказывать нечего. Пусть e не в T. Добавим e к T: в дереве появится ровно один цикл (добавление ребра к дереву всегда даёт один цикл - между концами e уже был единственный путь, и теперь он замкнулся).

Этот цикл выходит из S и возвращается обратно, значит он пересекает разрез ЧЁТНОЕ число раз - и кроме e в нём есть ещё хотя бы одно ребро f, пересекающее разрез. Выбросим f:

T' = T + e − f

Что получилось? Число рёбер прежнее (V − 1), циклов нет (мы разорвали единственный появившийся), связность цела (удалённое ребро лежало на цикле, значит его концы соединены обходным путём). Значит T' - остовное дерево. Его вес: w(T') = w(T) + w(e) − w(f). Но e - САМОЕ ЛЁГКОЕ среди пересекающих разрез, значит w(e) <= w(f), откуда w(T') <= w(T).

Дерево T было минимальным, значит w(T') = w(T), и T' - тоже МОД, причём содержащий e. Что и требовалось. А если веса различны, то w(e) < w(f) строго, и w(T') < w(T) - противоречие с минимальностью T: значит e входит в КАЖДОЕ минимальное остовное дерево, и оно единственно.

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

Разбор: как из одной теоремы получаются два алгоритма

Оба алгоритма только и делают, что применяют свойство разреза - к разным разрезам.

Прим. Держим растущее дерево S (сначала одна вершина). Разрез - это «уже в дереве» против «ещё нет». Берём самое лёгкое ребро, пересекающее ЭТОТ разрез, добавляем, вершина переходит в S. По свойству разреза добавленное ребро принадлежит МОД, значит после V − 1 шага получится МОД целиком.

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

Борувка. Каждая компонента одновременно выбирает своё самое лёгкое исходящее ребро - это V разрезов сразу, и все выборы законны по той же теореме.

Один результат, три стратегии выбора разреза. Именно поэтому в этой главе доказывается ОДНА теорема, а алгоритмы после неё разбираются почти без доказательств.

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

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

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

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

Теперь сам

Граф: a-b = 4, a-c = 1, b-c = 2, b-d = 5, c-d = 3. Примени свойство разреза к разбиению {a, c} против {b, d} и скажи, какое ребро точно войдёт в МОД. Потом найди само МОД и проверь.