Теорема Кёнига (комбинаторика)

В теории графов теорема Кёнига (теорема Кёнига-Эгервари, венгерская теорема), доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.

Пример двудольного графа с наибольшим паросочетанием (выделено голубым) и наименьшим вершинным покрытием (выделено красным), оба имеют размер шесть.

Определения

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

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

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

Утверждение теоремы

В любом двудольном графе число рёбер в наибольшем паросочетании равно числу вершин в наименьшем вершинном покрытии.

Пример

Двудольный граф на рисунке вверху имеет по 7 вершин в каждой из долей. Паросочетание с 6 рёбрами выделено синим цветом, а вершинное покрытие $\{x_{2},x_{4},x_{5},y_{2},y_{4},y_{6}\}$ выделено красным. Это покрытие является наименьшим по размеру, поскольку любая вершина в покрытии должна включать по меньшей мере одну конечную вершину ребра паросочетания. Таким же образом, нет паросочетания большего размера, поскольку любое ребро паросочетания должно содержать по меньшей мере одну конечную вершину из вершинного покрытия, так что это паросочетание является наибольшим. Теорема Кёнига как раз и утверждает равенство размеров паросочетания и покрытия (в данном примере оба числа равны шести).

Доказательства

Разделение вершин на посещённые и не посещённые для доказательства теоремы Кёнига.

Доказательство

Пусть задан двудольный граф $G=(X,Y,E)$, а $M$ — наибольшее паросочетание в $G$.

Сначала рассмотрим случай, когда паросочетание $M$ насыщает все вершины доли $X$, то есть размер паросочетания $M$ равен $|X|$. Очевидно, что вся доля $X$ является вершинным покрытием в графе $G$, следовательно, она является и наименьшим вершинным покрытием, и в этом случае утверждение теоремы выполняется.

Иначе возьмём все вершины доли $X$, не насыщенные паросочетанием $M$, и запустим из них обход в ширину (можно обход в глубину) по следующему правилу:

1. Слева направо переходим только по рёбрам, не входящим в $M$ (будем называть их чёрными).
2. Справа налево переходим только по рёбрам, входящим в $M$ (будем называть их голубыми).

Пусть $X^{+}$ и $Y^{+}$ — подмножества вершин левой и правой доли, посещённых во время обхода, а $X^{-}$ и $Y^{-}$ — соответственно, подмножества не посещённых вершин (см. рисунок справа).

Между множествами $X^{+}$ и $Y^{-}$ нет чёрных рёбер, поскольку иначе во время обхода мы бы посетили вершины из множества $Y^{-}$. По аналогичной причине, между множествами $X^{-}$ и $Y^{+}$ нет голубых рёбер.

Докажем, что между множествами $X^{+}$ и $Y^{-}$ нет также и голубых рёбер. От противного, пусть такое ребро $\{x^{+},y^{-}\}$ есть. Вершина $x^{+}$ не могла являться стартовой для обхода в ширину, поскольку она насыщена паросочетанием $M$. Следовательно, обход в ширину пришёл в $x^{+}$ из какой-то вершины $y^{+}$ по голубому ребру, что означает, что вершине $x^{+}$ инцидентны два голубых ребра $\{x^{+},y^{-}\}$ и $\{x^{+},y^{+}\}$. Но это невозможно, поскольку голубые рёбра образуют паросочетание.

Следовательно, любое ребро графа $G$ инцидентно или вершине из $X^{-}$ или вершине из $Y^{+}$, то есть $X^{-}\cup Y^{+}$ является вершинным покрытием. Покажем, что все вершины в $X^{-}\cup Y^{+}$ насыщены паросочетанием $M$. Для вершин из $X^{-}$это очевидно, поскольку все ненасыщенные вершины левой доли по построению лежат в $X^{+}$. Если в $Y^{+}$ есть ненасыщенная вершина, то существует $M$-чередующая цепь, заканчивающаяся в ней, что противоречит тому, что паросочетание $M$ является наибольшим. Теперь осталось вспомнить, что между множествами $X^{-}$ и $Y^{+}$ нет рёбер из $M$, то есть каждому ребру паросочетания инцидентна в точности одна вершина из вершинного покрытия $X^{-}\cup Y^{+}$. Следовательно, $|M|=|X^{-}\cup Y^{+}|$, и вершинное покрытие $X^{-}\cup Y^{+}$ является наименьшим.

Доказательство через теорему Форда — Фалкерсона

Минимальный разрез $(S,T)$ в транспортной сети двудольного графа

Задача поиска наибольшего паросочетания в графе $G=(A,B,E)$ может быть сведена к нахождению наибольшего потока в транспортной сети $G'_{\infty }$, такой что из истока $s$ в первую долю $A$ и из второй доли $B$ в сток $t$ проходят рёбра пропускной способности $1$, а для любого ребра $(a,b)\in E$ исходного графа, из $a$ в $b$ проходит ребро пропускной способности $+\infty$.

По теореме Форда — Фалкерсона, величина такого потока равна величине минимального разреза в $G'_{\infty }$. Пусть такой разрез задан множествами вершин $S$ и $T$. Вершины исходного графа можно разбить на четыре группы $A_{S},A_{T},B_{S},B_{T}$, такие что $A=A_{S}\cup A_{T}$ и $B=B_{S}\cup B_{T}$, при том $A_{S},B_{S}\subset S$ и $A_{T},B_{T}\subset T$. При такой классификации, в исходном графе не может быть рёбер из $A_{S}$ в $B_{T}$, так как такие рёбра сделали бы величину разреза бесконечной.

Отсюда, в свою очередь, следует, что любое ребро графа инцидентно вершине из $A_{T}$, либо вершине из $B_{S}$. В то же время сам разрез составляют рёбра из $s$ в $A_{T}$ и из $B_{S}$ в $t$. Таким образом, с одной стороны $A_{T}\cup B_{S}$ является вершинным покрытием исходного графа, с другой — величина минимального разреза в графе равна $|A_{T}|+|B_{S}|$, из чего следует, что множество $A_{T}\cup B_{S}$ и есть минимальное вершинное покрытие графа $G$.

Следствие из теоремы Кёнига

Пусть $M$ и $C$ — соответственно, наибольшее паросочетание и наименьшее вершинное покрытие в двудольном графе $G$. Тогда любое ребро из $M$ инцидентно в точности одной вершине из $C$. И наоборот, любой вершине из $C$ инцидентно в точности одно ребро из $M$. Другими словами, отношение инцидентности задаёт биекцию между множествами $M$ и $C$.

Заметим, что если бы граф $G$ не являлся двудольным, то некоторым рёбрам $M$ могли бы быть инцидентны сразу две вершины из $C$, а некоторые вершины из $C$ могли бы не иметь инцидентных им рёбер из $M$.

Алгоритм построения наименьшего вершинного покрытия в двудольном графе

Описанный выше обход в ширину из доказательства теоремы строит наименьшее вершинное покрытие по заданному наибольшему паросочетанию. Данный алгоритм имеет сложность $O(|E|)$. Наибольшее паросочетание в двудольном графе может быть найдено алгоритмом Хопкрофта–Карпа за время ${\textstyle O(|E|{\sqrt {|V|}})}$.

Связь с совершенными графами

Говорят, что граф совершенен, если для любого порождённого подграфа его хроматическое число равно размеру максимальной клики. Любой двудольный граф совершенен, поскольку любой его подграф является либо двудольным, либо независимым. В двудольном графе, не являющемся независимым, хроматическое число и размер максимальной клики равны двум, в то время как для независимого множества оба этих числа равны единице.

Граф совершенен тогда и только тогда, когда его дополнение совершенно, и теорему Кёнига можно считать эквивалентом утверждения, что дополнение двудольного графа совершенно. Любые раскраски дополнения двудольного графа имеют размер максимум 2, а классы размера 2 образуют паросочетания. Клики в дополнении графа $G$ — это независимое множество в $G$, и, как мы уже писали выше, независимое множество в двудольном графе $G$ — это дополнение вершинного покрытия $G$. Таким образом, любое паросочетание $M$ в двудольном графе $G$ с $n$ вершинами соответствует раскраске дополнения $G$ с $n-|M|$ цветами, что, ввиду совершенства дополнения двудольных графов, соответствует независимому множеству в $G$ с $n-|M|$ вершинами, что соответствует вершинному покрытию $G$ $|M|$ вершинами. Следовательно, теорема Кёнига доказывает совершенство дополнений двудольных графов, то есть результат, выраженный в более явной форме у Галлаи.

Можно связать также теорему Кёнига о рёберной раскраске с другим классом совершенных графов, рёберными графами двудольных графов. Для графа $G$ рёберный граф $L(G)$ имеет вершины, соответствующие рёбрам графа $G$, и рёбра для каждой пары смежных рёбер в $G$. Таким образом, хроматическое число $L(G)$ равно хроматическому индексу $G$. Если $G$ — двудольный, клики в $L(G)$ — это в точности множества рёбер в $G$, имеющих общую конечную вершину. Теперь теорема Кёнига о рёберной раскраске, утверждающая, что хроматический индекс равен максимальной степени вершин в двудольном графе, может быть интерпретирована как утверждение, что рёберный граф двудольного графа совершенен.

Поскольку рёберные графы двудольных графов совершенны, дополнения рёберных графов двудольных графов тоже совершенны. Клика в дополнении рёберного графа для $G$ — это просто паросочетание $G$. А раскраска дополнения рёберного графа для $G$, в случае, если $G$ является двудольным, — это разбиение рёбер графа $G$ на подмножества рёбер, имеющих общие вершины. Конечные вершины, являющиеся общими в этих подмножествах, образуют вершинное покрытие графа $G$. Таким образом, сама теорема Кёнига может быть также интерпретирована как утверждение, что дополнение рёберных графов двудольных графов совершенно.

Дополнения

• Для графов, не являющихся двудольными, ситуация с задачами о наибольшем паросочетании и наименьшем вершинном покрытии совсем другая — наибольшее паросочетание можно найти за полиномиальное время для любого графа, в то время как поиск наименьшего вершинного покрытия является NP-полной задачей. Дополнение вершинного покрытия для любого графа — это независимое множество, и поиск наибольшего независимого множества — это ещё одна NP-полная задача.
• Теорема Кёнига эквивалентна массе других минимаксных теорем в теории графов и комбинаторике, таких как теорема Холла о свадьбах и теорема Дилуорса. Поскольку паросочетание в двудольных графах является частным случаем потока в сети, теорема Кёнига также вытекает из теоремы Форда — Фалкерсона.
• В русскоязычном интернете и научной литературе распространена следующая формулировка теоремы: если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, которые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин «линия» обозначает либо строку, либо столбец в матрице).

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

Ссылки

• Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. — М.: Мир, 1998. — 653 с. — ISBN 5-03-002517-0.
• Рыбников К.А. Введение в комбинаторный анализ. — МГУ, 1972.

• Эвнин А. Ю. Вокруг теоремы Холла (рус.) // Матем. обр.. — 2005. — Т. 3(34). — С. 2—23.

• Bondy, J. A., Murty, U. S. R. Graph Theory with Applications. — North Holland, 1976. — ISBN 0-444-19451-7.

• Egerváry, Jenő. Matrixok kombinatorius tulajdonságairól [On combinatorial properties of matrices] (венг.) // Matematikai és Fizikai Lapok. — 1931. — Vol. 38. — P. 16-28.

• Gallai, Tibor. Maximum-minimum Sätze über Graphen // Acta Math. Acad. Sci. Hungar.. — 1958. — Vol. 9. — Вып. 3-4. — P. 395–434. — doi:10.1007/BF02020271.

• Göös, Mika. Jukka Suomela. 26th International Symposium on Distributed Computing (DISC), Salvador, Brazil, October 2012. — 2012.

• Kőnig, Dénes. Gráfok és mátrixok (венг.) // Matematikai és Fizikai Lapok. — 1931. — Vol. 38. — P. 116–119.