Теорема Кёнига: двудольный граф, паросочетания и покрытия

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

Что такое двудольный граф

Граф $G = (V, E)$ называется двудольным, если множество его вершин можно разбить на две непересекающиеся доли $X$ и $Y$ так, что каждое ребро соединяет вершину из $X$ с вершиной из $Y$. Внутри одной доли рёбер нет. Эквивалентный критерий: граф двудолен тогда и только тогда, когда в нём нет циклов нечётной длины. Это удобно проверять обходом в ширину с раскраской вершин в два цвета.

Двудольный граф - естественная модель для задач о назначениях: доля $X$ - работники, доля $Y$ - задачи, ребро означает «может выполнить». Именно для таких структур теорема Кёнига даёт точный ответ, тогда как для произвольных (недвудольных) графов равенство, вообще говоря, нарушается.

Чтобы не разбирать определения на абстрактном примере, опишите свой граф в инструменте ниже - он подготовит запрос на поиск максимального паросочетания и минимального покрытия с проверкой равенства по теореме Кёнига.

Паросочетание и вершинное покрытие

Паросочетание (matching) $M \subseteq E$ - это набор рёбер, попарно не имеющих общих вершин. Максимальное паросочетание - то, в котором рёбер больше всего; его размер обозначают $\nu(G)$ (число паросочетания). Если в паросочетании участвует каждая вершина, оно называется совершенным.

Вершинное покрытие (vertex cover) $C \subseteq V$ - это набор вершин такой, что у каждого ребра хотя бы один конец лежит в $C$. Минимальное покрытие имеет размер $\tau(G)$ (число покрытия). Эти два параметра всегда связаны неравенством

$\nu(G) \le \tau(G),$

потому что для покрытия рёбер паросочетания нужна хотя бы одна вершина на каждое ребро, а рёбра $M$ не имеют общих концов. Содержание теоремы Кёнига - в том, что для двудольного графа это неравенство обращается в равенство.

Формулировка теоремы Кёнига

В любом двудольном графе $G$ размер максимального паросочетания равен размеру минимального вершинного покрытия: $\nu(G) = \tau(G).$

Утверждение доказано Денешем Кёнигом в 1931 году (близкий результат независимо получил Эгервари). Ключевое слово здесь - «двудольный»: для треугольника $K_3$ имеем $\nu = 1$, но $\tau = 2$, так что без двудольности равенство ломается.

Доказательство через дополняющие пути

Приведём конструктивное доказательство, которое заодно объясняет, как покрытие извлекается из паросочетания. Пусть $M$ - максимальное паросочетание двудольного графа с долями $X$ и $Y$.

1. Возьмём множество $U \subseteq X$ - все вершины доли $X$, не насыщенные паросочетанием $M$ (свободные).
2. Рассмотрим множество $Z$ всех вершин, достижимых из $U$ по чередующимся путям - таким, где рёбра попеременно лежат вне $M$ и в $M$.
3. Построим множество $C = (X \setminus Z) \cup (Y \cap Z)$.

Можно показать, что $C$ - вершинное покрытие и что $|C| = |M|$. Покрытием оно является потому, что не существует ребра из $X \cap Z$ в $Y \setminus Z$ (иначе чередующийся путь продлился бы). А равенство $|C| = |M|$ следует из того, что каждая вершина $C$ насыщена паросочетанием и разным вершинам $C$ соответствуют разные рёбра $M$. Так как заведомо $\nu(G) \le \tau(G)$, а мы предъявили покрытие размера $\nu(G)$, получаем $\tau(G) \le \nu(G)$, откуда $\nu(G) = \tau(G)$.

Эта же конструкция - основа алгоритма Куна и венгерского метода; разбор пошагового поиска паросочетания мы делали в материале про алгоритм Куна для паросочетаний.

Разбор примера

Возьмём двудольный граф с долями $X = \{x_1, x_2, x_3\}$ и $Y = \{y_1, y_2, y_3\}$ и рёбрами $x_1y_1, x_1y_2, x_2y_2, x_3y_2, x_3y_3$. Поиск дополняющих путей даёт максимальное паросочетание $M = \{x_1y_1, x_2y_2, x_3y_3\}$ размера $\nu(G) = 3$ - оно совершенное, насыщает обе доли.

Теперь извлечём покрытие. Свободных вершин в доле $X$ нет, поэтому множество $Z$, достижимое чередующимися путями, пусто, и покрытие получается из насыщенных вершин: одного представителя на каждое ребро паросочетания достаточно. Возьмём $C = \{x_1, y_2, x_3\}$ - нетрудно проверить, что каждое из пяти рёбер имеет конец в $C$, а его размер $\tau(G) = 3$. Равенство $\nu(G) = \tau(G) = 3$ подтверждает теорему Кёнига. Заметьте: минимальное покрытие здесь не единственно, но его размер фиксирован.

Связь с теоремой Холла

Теорема Кёнига тесно переплетена с теоремой Холла о системе различных представителей. Теорема Холла говорит: совершенное паросочетание, насыщающее всю долю $X$, существует тогда и только тогда, когда для любого подмножества $S \subseteq X$ выполнено

$|N(S)| \ge |S|,$

где $N(S)$ - множество соседей вершин из $S$. Из теоремы Кёнига условие Холла выводится в несколько строк, и наоборот. Обе они - частные случаи более общей теоремы о максимальном потоке и минимальном разрезе (Форд - Фалкерсон): паросочетание соответствует потоку, а покрытие - разрезу.

Как применить на практике

Чтобы найти оба объекта вручную для небольшого двудольного графа, удобно действовать так:

1. Разбейте вершины на доли $X$ и $Y$, проверив отсутствие нечётных циклов.
2. Постройте максимальное паросочетание поиском дополняющих путей (алгоритм Куна).
3. По описанной выше конструкции с множеством $Z$ извлеките минимальное покрытие.
4. Сверьте: число выбранных рёбер должно совпасть с числом вершин покрытия - это и есть проверка теоремы Кёнига.

Для задач о назначениях с весами вместо «голого» паросочетания применяют венгерский алгоритм, но структура двойственности остаётся той же.

Частые ошибки

• Применяют теорему к недвудольному графу. Равенство $\nu = \tau$ гарантировано только при двудольности. Для графа с нечётным циклом сначала проверьте раскраску в два цвета.
• Путают максимальное и максимальное по включению паросочетание. «Максимальное по числу рёбер» (maximum) и «нерасширяемое» (maximal) - разные вещи; теорема говорит именно о первом.
• Считают покрытием множество рёбер. Вершинное покрытие состоит из вершин, а не из рёбер; рёберное покрытие - отдельное понятие со своей теоремой Галлаи.
• Забывают про изолированные вершины. Они не входят ни в одно ребро и не влияют ни на $\nu$, ни на $\tau$, но иногда их ошибочно добавляют в покрытие.
• Останавливают поиск паросочетания на первом нерасширяемом. Без перебора дополняющих путей легко получить не максимум, и тогда равенство с покрытием не сойдётся.

FAQ

Работает ли теорема Кёнига для взвешенных графов? В классическом виде - нет, она про мощности множеств. Для весов используют двойственность линейного программирования и венгерский алгоритм, но идея «паросочетание ↔ покрытие» сохраняется.

Чем теорема Кёнига отличается от теоремы Холла? Холл даёт критерий существования паросочетания, насыщающего одну долю; Кёниг даёт точное равенство размеров паросочетания и покрытия. Они эквивалентны и выводятся друг из друга.

Что такое дополнение Кёнига для независимого множества? Поскольку дополнение вершинного покрытия - независимое множество, из теоремы следует, что в двудольном графе максимальное независимое множество имеет размер $|V| - \nu(G)$.

Коротко

Теорема Кёнига утверждает, что в двудольном графе максимальное паросочетание и минимальное вершинное покрытие имеют одинаковый размер: $\nu(G) = \tau(G)$. Это равенство - следствие двойственности задач, доказывается конструкцией с чередующимися путями и тесно связано с теоремами Холла и Форда - Фалкерсона. Для произвольных графов оно не выполняется, а для двудольных даёт основу эффективных алгоритмов о назначениях.