Задачи на паросочетания

Алгоритм нахождения паросочетания далеко не настолько сложный, насколько сложно сводить задачи к нему.

Начнём с простых примеров.

#Кубики

Дано $n$ кубиков, у каждого из них 6 граней, на каждой гране написана какая-то буква. Дано слово $s$ , и требуется каждой букве слова $s$ сопоставить уникальный кубик, так чтобы мы могли повернуть этот кубик и получить нужную нам букву.

Пример — даны три кубика, на гранях которых написаны буквы:

(a, a, a, a, a, a)
(а, а, а, а, а, б)
(а, а, а, б, б, с)

Если задано слово «acb», тогда ответ ровно один: 132.

Решение. Сделаем двудольный граф, одна доля которого — номера кубиков, а другая — номер буквы в слове $s$ . Проведем ребра из номера кубика в номер буквы только если мы можем взять этот кубик на эту позицию в строке, то есть если у него есть грань с соответствующей буквой. Теперь ответ — максимальное паросочетание в этом графе.

По определению паросочетания мы не сопоставим ни один кубик нескольким буквам, но так как наше паросочетание — максимально, то мы покроем максимально возможное количество букв.

#Доминошки

Есть прямоугольное поле $n \times m$ , которое содержит какие-то выколотые клетки. Надо положить на это поле как можно больше костей домино (прямоугольников размера $1 \times 2$ ), но с условием, что поверх выколотых полей ничего лежать не должно.

Составим граф, в котором вершины будут полями, а рёбрами будут возможности положить доминошку на два соседних свободных поля. Заметим, что такой граф будет двудольным: можно его покрасить как шахматную доску, и тогда черные клетки будут вершинами первой доли, а белые — второй.

Ответ — максимальное паросочетание в таком графе. Асимптотика с алгоритмом Куна $O(n^2 m^2)$ , потому что у нас будет $O(nm)$ вершин и рёбер.

#Покрытие путями DAG

Разберем более сложную задачу, до решения которой самостоятельно додуматься сложно.

Дан ориентированный ациклический граф $G$ (англ. directed acyclic graph, DAG). Требуется покрыть его наименьшим числом путей, то есть найти наименьшее множество простых путей, где каждая вершина принадлежит ровно одному пути.

Построим соответствующие изначальному графу $G$ два двудольных графа $H$ и $\overline{H}$ следующим образом:

В каждой доле графа $H$ будет по $n$ вершин. Обозначим их через $a_i$ и $b_i$ соответственно.
Для каждого ребра $(i, j)$ исходного графа $G$ проведём соответствующее ребро $(a_i, b_j)$ в графе $H$ .
Теперь из графа $H$ сделаем граф $\overline{H}$ , добавив обратное ребро $(b_i, a_i)$ для каждого $i$ .

Если мы рассмотрим любой путь $v_1, v_2, \ldots, v_k$ в исходном графе $G$ , то в графе $\overline{H}$ ему будет соответствовать путь $a_{v_1}, b_{v_2}, a_{v_2}, b_{v_3}, \ldots, a_{v_{k-1}}, b_{v_k}$ . Обратное тоже верно: любой путь, начинающийся в левой доле $\overline{H}$ и заканчивающийся в правой будет соответствовать какому-то пути в $G$ .

Итак, есть взаимно однозначное соответствие между путями в $G$ и путями $\overline{H}$ , идущими из левой доли в правую. Заметим, что любой такой путь в $\overline{H}$ — это паросочетание в $H$ (напомним, это $\overline{H}$ без обратных рёбер). Получается, любому пути из $G$ можно поставить в соответствие паросочетание в $H$ , и наоборот. Более того, непересекающимся путям в $G$ соответствуют непересекающиеся паросочетания в $H$ .

Заметим, что если есть $p$ непересекающихся путей, покрывающих все $n$ вершин графа, то они вместе содержат $r = n - p$ рёбер. Отсюда получаем, что чтобы минимизировать число путей $p$ , мы должны максимизировать число рёбер $r$ в них.

Мы теперь можем свести задачу к нахождению максимального паросочетания в двудольном графе $H$ . После нахождения этого паросочетания мы должны преобразовать его в набор путей в $G$ . Это делается тривиальным алгоритмом: возьмем $a_1$ , посмотрим, с какой $b_k$ она соединена, посмотрим на $a_k$ и так далее. Некоторые вершины могут остаться ненасыщенными — в таком случае в ответ надо добавить пути нулевой длины из каждой из этих вершин.

#Минимальное вершинное покрытие

Задача. Назовем вершинным покрытием графа такое множество вершин, что каждое ребро графа инцидентно хотя бы одной вершине из множества. Необходимо найти вершинное покрытие наименьшего размера.

В общем случае это NP-полная задача, но для двудольных графов она имеет достаточно простое решение.

Обозначим за $V_{min}$ наименьшее вершинное покрытие, а за $M$ — максимальное паросочетание в графе. Тогда сразу заметим, что $|V_{min}| \ge |M|$ , потому что $M$ — множество независимых ребер. Теперь приведем алгоритм, который строит вершинное покрытие размера ровно $|M|$ . Очевидно, оно будет минимальным.

Алгоритм. Мысленно ориентируем ребра графа: ребра из $M$ проведем из правой доли в левую, остальные — из левой в правую, после чего запустим обход в глубину из всех вершин левой доли, не включенных в $M$ .

Заметим, что граф разбился на несколько множеств: $L^+, L^-, R^+, R^-$ , где «плюсовые» множества — это множества посещенных в процессе обхода вершин. В графе такого вида не бывает ребер $L^+ \rightarrow R^-$ и $L^- \leftarrow R^+$ по очевидным соображениям. Ребер $L^+ \leftarrow R^-$ не бывает, потому что в противном случае паросочетание $M$ не максимальное — его можно дополнить ребрами такого типа.

L^- \cup R^+ = V_{min}

Понятно, что данное множество покроет все ребра. Осталось выяснить, почему $L^- \cup R^+$ . Это верно потому, что $L^- \cup R^+$ покрывает все ребра $M$ ровно один раз (ведь ребра $L^- \rightarrow R^+$ не принадлежат $M$ ), а также потому, что в нем нет вершин, не принадлежащих $M$ (для $L^-$ это справедливо по определению, для $R^+$ можно провести доказательство от противного с использованием чередующихся цепей).

Упражнение. Подумайте, как это можно применить к решению задачи о нахождении максимального независимого множества.

#Паросочетание минимального веса

Пусть у вершин левой доли есть какие-то веса, и нам нужно набрать максимальное паросочетание минимального веса.

Выясняется, что можно просто отсортировать вершины левой доли по весу и пытаться в таком порядке добавлять их в паросочетание стандартным алгоритмом Куна. Для доказательства этого факта читатель может прочитать про жадный алгоритм Радо-Эдмондса, частным случаем которого является такая модификация алгоритма Куна.

Аналогичную задачу, но когда у ребер есть веса, проще всего решать сведением к нахождению потока минимальной стоимости.