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

Эквивалентная линейно-алгебраическая формулировка: если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, которые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (линия — либо строка, либо столбец в матрице).

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

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

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

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

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

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

Теорема Кёнига эквивалентна ряду других минимаксных теорем в теории графов и комбинаторике, таких как теорема Холла о свадьбах и теорема Дилуорса. Поскольку паросочетание в двудольных графах является частным случаем потока в сети, теорема Кёнига также вытекает из теоремы Форда — Фалкерсона.

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

Примечания

Литература

Ссылки

К Категория:Комбинаторика