Паросочетания в двудольном графе
Также: Bipartite matching · maximum matching · алгоритм Куна · Kuhn's algorithm · алгоритм Хопкрофта — Карпа · Hopcroft–Karp · теорема Кёнига · теорема Холла
Как разбить вершины на пары по рёбрам, чтобы пар было больше всего: заявки и мастера, клетки под доминошки, студенты и темы. Ответ ищут чередующимися путями — алгоритм Куна по одному, Хопкрофт — Карп целыми фазами, — а когда пар больше не найти, теорема Кёнига показывает, кто этому мешает.
Можно ли выложить тёмную часть фотографии доминошками так, чтобы каждая тёмная клетка была закрыта и ни одна доминошка не легла на светлое? Обычно нельзя, но насколько близко можно подойти и что мешает? Ниже снимок «Буря», разбитый на клетки; клетки темнее порога надо закрыть. Алгоритм Хопкрофта — Карпа кладёт доминошки фаза за фазой, и в конце красным остаются клетки, которые не закрыть никакой раскладкой. Двигайте порог, меняйте снимок и касайтесь красных клеток.
На «Буре» тёмных клеток 5854. Доминошек легло 2923, без пары осталось 8 клеток. Четыре из них объясняет простой подсчёт: если раскрасить клетки как шахматную доску, чёрных 2929, белых 2925, а доминошка всегда закрывает одну чёрную и одну белую. Остальные четыре — сложнее: коснитесь красной клетки, и сцена покажет область, где клеток одного цвета больше, чем их соседей другого. Такая область есть у каждой красной клетки, и это не свойство алгоритма, а теорема.
Идея
Граф двудольный, если вершины делятся на две доли и рёбра идут только между долями: заявки и мастера, студенты и темы, чёрные и белые клетки. Паросочетание — набор рёбер без общих концов, то есть разбиение части вершин на пары. Нужно наибольшее.
Иногда доли видны сразу, иногда их нужно найти: граф двудольный тогда и только тогда, когда в нём нет нечётных циклов, и проверяет это один обход в ширину — соседние слои получают разные цвета, а ребро внутри слоя выдаёт нечётный цикл. У клетчатого поля доли — цвета шахматной раскраски: соседние по стороне клетки всегда разного цвета.
Возьмём текущие пары и найдём путь, который начинается в свободной вершине слева, кончается в свободной вершине справа и чередует рёбра: не в паре, в паре, не в паре… Поменяем на нём роли рёбер — те, что были в паре, выйдут, остальные войдут, — и пар станет на одну больше. Когда такого пути нет, пар больше всего.
Такой путь называют увеличивающим, как в задаче о максимальном потоке, и это не совпадение: паросочетание — поток единичной величины через каждую вершину, а чередующийся путь — увеличивающий путь в остаточной сети. Но работать прямо с парами проще и быстрее, чем строить сеть.
Алгоритм Куна по шагам
Самый простой способ — перебирать вершины слева по очереди и для каждой искать увеличивающий путь поиском в глубину. Нужный мастер занят — спросим его заказ, нельзя ли тому перейти к другому мастеру; тот занят — спросим дальше. Мастеров, которых уже спрашивали в этом поиске, второй раз не трогаем. Пример выдуманный: шесть заказов и шесть мастеров.
Заказ 2 получает Айдара, потому что заказ 1 переходит к Белле. Заказ 5 — сложнее: его Гаухар держит заказ 4, и тот переезжает к Дине, причём сначала поиск заходит в тупик через Вадима и Беллу. А для заказа 6 пути нет вовсе. Почему — видно в последнем шаге: заказы 1, 2, 3 и 6 вместе умеют брать только трёх мастеров.
Почему этого достаточно
Паросочетание M наибольшее тогда и только тогда, когда для него нет увеличивающего пути.
Если путь есть, переворот даёт паросочетание на одно ребро больше. Пусть пути нет, но есть паросочетание M′ больше. Возьмём рёбра, которые лежат ровно в одном из двух, — их симметрическую разность. У каждой вершины таких рёбер не больше двух, по одному из каждого паросочетания, поэтому разность распадается на пути и циклы, где рёбра M и M′ чередуются. В циклах их поровну. Раз в M′ рёбер больше, какой-то путь содержит больше рёбер M′, чем M, — он начинается и кончается рёбрами M′, его концы свободны в M, и это увеличивающий путь для M. Противоречие.
Когда путей нет, есть и короткий способ это доказать — предъявить вершинное покрытие того же размера. Каждая пара — ребро, а рёбра паросочетания не имеют общих концов, поэтому любое покрытие содержит хотя бы по вершине из каждой пары, и пар не больше, чем вершин в любом покрытии.
В двудольном графе наибольшее паросочетание равно наименьшему вершинному покрытию.
Пусть M наибольшее. Пусть Z — все вершины, до которых доходят чередующиеся пути от свободных вершин слева. Возьмём C = (левые вне Z) ∪ (правые в Z). Каждое ребро покрыто: если его левый конец в Z, то правый тоже в Z — до него можно дойти по этому ребру (а если это ребро пары, то левый конец пришёл в Z через него). Размер: каждая правая вершина в Z занята — иначе нашёлся бы увеличивающий путь, — и её пара слева тоже в Z; каждая левая вершина вне Z занята — свободные слева все в Z. Так в C ровно по одной вершине из каждой пары, и |C| = |M|.
Отсюда теорема Холла: все вершины слева можно разобрать по парам тогда и только тогда, когда у любых k из них вместе не меньше k соседей справа. Если пары найти не удалось, множество Z слева и есть нарушитель: его соседи — правые вершины в Z, и их меньше. Это и рисует сцена, когда вы касаетесь красной клетки, и то же видно в последнем шаге примера с заказами.
Код
Программа строит граф клеток четырёх снимков, кладёт доминошки алгоритмом Хопкрофта — Карпа, для сравнения считает, сколько рёбер просмотрел бы Кун, и строит покрытие из доказательства теоремы Кёнига — оно всегда того же размера, что и паросочетание. Поиск в глубину — со своим стеком: увеличивающие пути на клетках бывают длиной в тысячи шагов, и рекурсия Python упёрлась бы в предел глубины.
На «Озере Иссык» без пары остаются 33 клетки при разнице цветов в одну: разница — только нижняя оценка, дыр и узких перешейков в настоящей картинке хватает. А сравнение с Куном показывает, что на таких полях он неплох: на трёх снимках просмотрел примерно столько же рёбер, сколько Хопкрофт — Карп, и только на «Буре» — в шесть раз больше.
Сколько это стоит
У Куна каждый поиск стоит O(E), а поисков — по одному на вершину слева: O(V E). Плохо становится, когда многим вершинам пары не достанется: неудачный поиск обходит всё, до чего дотягиваются чередующиеся пути, и ничего не меняет, а следующий проходит то же место снова. Хопкрофт — Карп работает фазами. Один обход в ширину сразу от всех свободных вершин слева раскладывает граф по слоям — по длине кратчайшего чередующегося пути. Потом поиск в глубину, который ходит только из слоя в следующий слой, находит много кратчайших увеличивающих путей без общих вершин, и все они переворачиваются за одну фазу.
Фаз не больше 2√V, поэтому алгоритм работает за O(E √V).
Каждая фаза — O(E): вершина, из которой путь не нашёлся, до конца фазы помечается тупиком, и каждое ребро просматривается константное число раз. После фазы кратчайший увеличивающий путь становится строго длиннее, так что после √V фаз все увеличивающие пути длиннее √V. Сравним текущее паросочетание с наибольшим: их симметрическая разность содержит столько увеличивающих путей без общих вершин, сколько пар не хватает, и каждый длиннее √V. Вершин всего V, значит, не хватает меньше √V пар, и каждая следующая фаза добавляет хотя бы одну. Всего фаз не больше 2√V.
Замер — на той ситуации, где Куну хуже всего: заявок вдвое больше, чем исполнителей, каждая подходит трём случайным. Третья линия — Кун с известной уловкой: отметки «уже спрашивали» сбрасываются только после удачного поиска, ведь неудачный ничего не изменил.
Кун растёт как квадрат: на двух тысячах заявок он медленнее Хопкрофта — Карпа в 60 раз на Python, а на шестнадцати тысячах в Go — больше чем в тысячу раз. Уловка помогает на порядок, но не меняет наклона: после каждого удачного поиска отметки всё равно сбрасываются. У Хопкрофта — Карпа время растёт почти линейно. Связь с потоками и тут прямая: на сети с единичными пропускными способностями алгоритм Диница делает ровно то же — слои и блокирующий поток — и работает за то же время.
Где работает
Назначения без весов. Заявки и исполнители, задачи и машины, рейсы и стоянки: кого с кем можно поставить, и как поставить больше всех. Если у каждой пары есть цена и нужна самая дешёвая полная расстановка, это уже венгерский алгоритм; если у участников есть предпочтения и нужна устойчивость, — алгоритм Гейла — Шепли из главы курса.
Сколько нужно исполнителей. Работы с временем начала и конца, исполнитель после одной работы успевает к другой — сколько исполнителей хватит на всё? Ответ: число работ минус наибольшее паросочетание в графе «работа → работа, которую можно сделать следом». Если отношение «можно следом» транзитивно, это теорема Дилуорса о разбиении частично упорядоченного множества на цепи.
Физика. Разбиения решётки на домино — модель димеров в статистической физике. В 1961 году Питер Кастелейн и, независимо, Гарольд Темперли с Майклом Фишером нашли формулу для числа таких разбиений прямоугольника; у шахматной доски их 12 988 816. А если у доски вырезать два противоположных угла, разбиений не останется ни одного — та же разница цветов, что в сцене. Эту головоломку в 1946 году предложил философ Макс Блэк.
История
Теорему о покрытии опубликовал Денеш Кёниг в 1931 году; в том же году Енё Эгервари доказал её вариант с весами. Филип Холл в 1935 году сформулировал условие «у любых k вместе не меньше k соседей» — в задаче о системе различных представителей, а за ним закрепилось шутливое название «теорема о свадьбах». В 1955 году Гарольд Кун построил на работах Кёнига и Эгервари алгоритм для задачи о назначениях и назвал его венгерским методом; поиск увеличивающих путей по одному в русскоязычной олимпиадной традиции называют алгоритмом Куна. Клод Берж в 1957 году доказал лемму об увеличивающих путях для любых графов, не только двудольных. Джон Хопкрофт и Ричард Карп опубликовали алгоритм с фазами в 1973 году.
Задачи
В первой задаче нужно самому увидеть двудольный граф в клетчатом поле — и не поверить подсчёту цветов. Во второй заявок больше, чем мастеров, и простой алгоритм Куна не успевает.
Мозаика из доминошек Заявки и мастераДанные: Фотографии автора сайта