Задачи на паросочетания - Алгоритмика
Задачи на паросочетания

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

авторы Сергей Слотин Максим Иванов

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

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

Кубики

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

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

  1. (a, a, a, a, a, a)
  2. (а, а, а, а, а, б)
  3. (а, а, а, б, б, с)

Если задано слово «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$ и так далее. Некоторые вершины могут остаться ненасыщенными — в таком случае в ответ надо добавить пути нулевой длины из каждой из этих вершин.

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

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

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

Теорема. $\mid V_{min} \mid \le \mid M \mid$, где $V_{min}$ — минимальное вершинное покрытие, а $M$ — максимальное паросочетание.

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

Алгоритм. Мысленно ориентируем ребра графа: ребра из $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^+$ можно провести доказательство от противного с использованием чередующихся цепей).

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

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

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

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

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

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