Что ещё сводится к паросочетанию

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

Как думаешь, при чём тут расписание поездов

Есть список рейсов: у каждого время отправления, время прибытия и станции. Один состав может обслужить два рейса подряд, если успевает доехать от конца первого до начала второго. Вопрос диспетчера: сколько составов нужно минимально?

Соблазн - написать перебор. Но присмотрись: «рейс X может идти сразу после рейса Y» - это ребро. Составы - это цепочки рейсов, то есть ПУТИ в таком графе. А «покрыть все вершины минимальным числом путей» - задача, которая решается паросочетанием и одним вычитанием.

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

Домино. Каждая костяшка - ребро; чем больше костяшек ты сложил в цепочки, тем меньше цепочек получится. Одна дополнительная состыковка склеивает две цепочки в одну, то есть уменьшает ответ на единицу. Поэтому «минимум цепочек» и «максимум состыковок» - одна и та же задача, просто считанная с разных концов.

Механизм: четыре сведения

двудольный граф, |V| вершин, максимальное паросочетание M:

минимальное вершинное покрытие   = |M|                 (Кёниг)
максимальное независимое множество = |V| − |M|         (дополнение покрытия)
минимальное рёберное покрытие      = |V| − |M|         (для графа без изолированных вершин)

ациклический граф, |V| вершин:
минимальное покрытие путями      = |V| − |M|,
    где M - паросочетание в РАСЩЕПЛЁННОМ графе:
    каждая вершина v даёт левую «v-выход» и правую «v-вход»,
    ребро u → v графа даёт ребро «u-выход» — «v-вход»

Независимое множество получается так: покрытие накрывает все рёбра, значит вне покрытия рёбер нет - оставшиеся вершины попарно несмежны. Покрытие путями: каждое ребро паросочетания склеивает две цепочки в одну, поэтому цепочек становится на |M| меньше, чем вершин.

веса на рёбрах         → задача о назначениях: венгерский алгоритм O(V³)
                          или поток минимальной стоимости (глава 4 раздела)
граф не двудольный     → алгоритм Эдмондса со сжатием цветков, O(V³)
нужна не величина,
а устойчивость         → стабильное паросочетание, алгоритм Гейла-Шепли O(V²)

Правило

В двудольном графе одно максимальное паросочетание M отвечает сразу на четыре вопроса: минимальное вершинное покрытие равно |M|, максимальное независимое множество и минимальное рёберное покрытие равны |V| − |M|. В ациклическом графе минимальное покрытие путями равно |V| − |M|, где M считается в расщеплённом графе «выходы против входов». Веса на рёбрах превращают задачу в задачу о назначениях (венгерский алгоритм или поток минимальной стоимости), недвудольность - в алгоритм Эдмондса со сжатием цветков, а требование устойчивости - в совершенно другую задачу со своим алгоритмом Гейла-Шепли.

Разбор: сколько составов нужно

Рейсы 1, 2, 3, 4. Успеваем: после 1 можно 2, после 2 можно 3, после 1 можно 4. Это ациклический граф с рёбрами 1→2, 2→3, 1→4.

Расщепляем: слева выходы 1в, 2в, 3в, 4в, справа входы 1´, 2´, 3´, 4´. Рёбра расщеплённого графа: 1в-2´, 2в-3´, 1в-4´.

максимальное паросочетание: 1в-2´ и 2в-3´   размер 2
покрытие путями = 4 − 2 = 2 состава

Проверим руками: один состав идёт по цепочке 1 → 2 → 3, второй обслуживает 4. Два состава, сходится. А если бы мы жадно взяли 1в-4´ (то есть пустили первый состав по маршруту 1 → 4), то паросочетание нашлось бы ещё одно - 2в-3´, - и размер остался бы 2: цепочки 1 → 4 и 2 → 3. Ответ тот же, маршруты разные. Минимум составов от выбора не зависит, а вот конкретное расписание - зависит.

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

Эти две задачи путают постоянно, а они разные. Пусть есть два кандидата A, B и две вакансии 1, 2, и подходят все ко всем. Максимальное паросочетание - любое из двух полных: A-1, B-2 или A-2, B-1. Размер одинаков, выбирать не из чего.

Теперь добавим ПРЕДПОЧТЕНИЯ. Кандидат A хочет вакансию 1, кандидат B тоже хочет 1; вакансия 1 предпочитает B, вакансия 2 - кого угодно.

назначение A-1, B-2:  пара (B, 1) - «блокирующая»:
                      B хочет 1 больше, чем 2, и 1 хочет B больше, чем A
                      → такое назначение развалится
назначение B-1, A-2:  блокирующих пар нет → стабильно

Оба назначения максимальны по размеру, но одно устойчиво, а другое нет. Алгоритм Гейла-Шепли находит стабильное за O(V²), и именно он лежит в основе распределения выпускников медвузов по больницам и школьников по школам. Мораль: прежде чем писать Куна, спроси, что именно оптимизируется - РАЗМЕР, СТОИМОСТЬ или УСТОЙЧИВОСТЬ. Это три разные задачи с тремя разными алгоритмами.

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

Первое: считать независимое множество через |V| − |M| в НЕдвудольном графе - там эта формула неверна, а сама задача NP-трудна. Второе: забыть про изолированные вершины в рёберном покрытии - их накрыть нечем, и формула ломается. Третье: строить расщеплённый граф для графа с циклами: покрытие путями через паросочетание работает только на ациклических. Четвёртое: решать задачу о назначениях Куном, просто отсортировав рёбра по весу, - жадность здесь даёт не оптимум, нужен венгерский алгоритм или поток минимальной стоимости. Пятое: путать стабильное паросочетание с максимальным: Гейл-Шепли не ищет самое большое, он ищет такое, которое не развалится.

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

Приём «свести к паросочетанию» стоит держать в голове как отдельный инструмент. Он превращает «назначить», «покрыть», «выбрать несовместимые» в задачу с готовым быстрым решением - а заодно даёт объяснение ответа через покрытие или дефицит Холла. Реальные примеры: минимальное число машин на маршрутах, распределение экзаменов по аудиториям, выбор непересекающихся сделок, сопоставление записей из двух баз («один к одному»), назначение задач по исполнителям в планировщике. И обратное предупреждение: как только появляются веса, приоритеты или ограничение «не больше трёх задач на человека», задача перестаёт быть простым паросочетанием - но почти всегда остаётся потоком, просто с другими пропускными способностями.

Теперь сам

Ациклический граф: 1→3, 2→3, 3→4. Посчитай минимальное покрытие путями.