Теорема Кёнига в теории графов¶

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

¶Формулировка

Пусть дан двудольный граф \(G = (U, V, E)\), где множество вершин разбито на две доли \(U\) и \(V\), а каждое ребро соединяет вершину из \(U\) с вершиной из \(V\). Тогда справедливо равенство:

\[ \nu(G) = \tau(G), \]

где \(\nu(G)\) — размер наибольшего паросочетания (набора попарно несмежных рёбер), а \(\tau(G)\) — размер наименьшего вершинного покрытия (набора вершин, покрывающего все рёбра графа).

Иными словами, максимальное число рёбер, которые можно выбрать так, чтобы они не имели общих концов, в точности равно минимальному числу вершин, которых достаточно, чтобы «задеть» каждое ребро.

¶История

Денеш Кёниг (1884–1944) — венгерский математик, один из основателей комбинаторики и теории графов. Результат был опубликован в 1931 году в работе, посвящённой теории конечных и бесконечных множеств. Независимо и в близкой форме аналогичное утверждение получил в 1931 году американский математик Дженё Эгервари, поэтому в англоязычной литературе теорему часто называют теоремой Кёнига — Эгервари. Позднее, в 1955 году, Харольд Кун распространил идею на взвешенный случай, что дало начало венгерскому алгоритму решения задачи о назначениях.

¶Связь с другими результатами

Теорема Кёнига тесно связана с рядом классических утверждений.

• Теорема Холла о свадьбах (1935) даёт критерий существования паросочетания, покрывающего одну из долей целиком. Из неё теорема Кёнига выводится как следствие.
• Теорема Менгера о непересекающихся путях является обобщением на произвольные графы и вместе с теоремой Кёнига образует ядро теории потоков и сетей.
• Теорема о максимальном потоке и минимальном разрезе (Форд — Фалкерсон, 1956) может рассматриваться как непрерывный аналог теоремы Кёнига.
• Теорема Дилворта о разбиении частично упорядоченного множества на цепи является «двойственной» формулировкой для двудольных графов сравнения.

Все эти результаты объединяет общая идея двойственности линейного программирования: задача о паросочетании и задача о вершинном покрытии образуют пару взаимно двойственных задач целочисленного программирования.

¶Доказательство (схема)

Одно из стандартных доказательств опирается на теорему Холла. Пусть \(M\) — наибольшее паросочетание. Строится вспомогательное множество вершин, достижимых из ненасыщенных вершин левой доли чередующимися путями (рёбра вне паросочетания — из \(U\) в \(V\), рёбра паросочетания — из \(V\) в \(U\)). Множество, составленное из ненасыщенных вершин \(U\) и насыщенных вершин \(V\), достижимых таким обходом, образует вершинное покрытие, мощность которого равна \(|M|\). Поскольку любое вершинное покрытие не меньше любого паросочетания, получается требуемое равенство.

Алгоритмически это построение реализуется методом поиска в ширину или в глубину и лежит в основе алгоритма Куна нахождения наибольшего паросочетания в двудольном графе.

¶Алгоритмическое значение

Теорема Кёнига имеет прямое прикладное значение.

Благодаря теореме задача поиска минимального вершинного покрытия в двудольном графе сводится к задаче о максимальном паросочетании, которая решается за полиномиальное время. Для произвольных графов аналогичное равенство не выполняется: например, в треугольнике наибольшее паросочетание имеет размер 1, а минимальное вершинное покрытие — 2.

¶Обобщения и ограничения

• Взвешенная версия (теорема Кёнига — Эгервари — Куна) утверждает равенство оптимальных значений прямой и двойственной задач линейного программирования для взвешенного паросочетания и взвешенного покрытия.
• Для недвудольных графов равенство нарушается; там действует теорема Галлаи — Эдмондса, связывающая размер паросочетания с дефицитом графа.
• Бесконечные графы требуют аксиомы выбора; для счётных графов утверждение сохраняется.

¶Значение

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

Источники: Кёниг Д. «Gráfok és mátrixok» (1931); Холл Ф. «On representatives of subsets» (1935); Форд Л., Фалкерсон Д. «Потоки в сетях» (1962); Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. «Лекции по теории графов»; Кристофидес Н. «Теория графов. Алгоритмический подход».