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

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

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

Окружение

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

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

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

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

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

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

Теорема названа в честь венгерскрого математика Денеша Кёнига. Кёниг заявил о ней в 1914 и опубликовал в 1916 доказательство, что любой регулярный двудольный граф имеет совершенное паросочетание, и, обобщённо, что хроматический индекс любого двудольного графа (то есть минимальное число паросочетаний, на которые можно разложить все дуги графа) равен максимальной степени. Последнее утверждение известно как теорема Кёнига о рёберной раскраске. Однако Бонди и Мерфи (Bondy, Murty, 1976) приписывают саму теорему более поздней работе Кёнига (1931). Согласно Бигу (Bigg) Кёниг приписывает идею изучения паросочетаний в двудольных графах своему отцу, математику Юлию Кёнигу.

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

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

В русскоязычном интернете распростанена следующая формулировка теоремы:

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

Данная формулировка легко переводится на язык двудольных графов:

Строки таблицы – это вершины одной части двудольного графа, столбцы – другой части.

Линии – это вершинное покрытие.

Единицы матрицы – рёбра. Требование, чтобы никакие две единицы не лежали на одной линии, соответствует паросочетанию.

Пример

Двудольный граф на рисунке вверху имеет 14 вершин, паросочетание с 6 рёбрами выделено синим цветом, а вершинное покрытие из шести вершин выделено красным. Нет меньшего по размеру вершинного покрытия, поскольку любая вершина должна включать по меньшей мере одну конечную вершину ребра паросочетания, так что это покрытие минимально. Таким же образом, нет паросочетания большего размера, поскольку любое ребро паросочетания должно содержать по меньшей мере одну конечную вершину из вершинного покрытия, так что это паросочетание максимально. Теорема Кёнига как раз и утверждает равенство размеров паросочетания и покрытия (в данном примере оба числа равны шести).

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

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

Пусть задан двудольный граф G=(V,E), и пусть V делится на левое множество L и правое R. Пусть M – максимальное паросочетание в G.

По определению "паросочетания", никакая вершина не может принадлежать более чем одному ребру из M. Таким образом, если вершинное покрытие с |M| вершинами может быть построено, оно минимально.

Если M – совершенное паросочетание (что предполагает, что M - максимально), то |L| = |R| = |M|. Поскольку каждое ребро G сопряжено ровно с одной вершиной из L и ровно с одной вершиной из R, либо L, либо R является вершинным покрытием размера |M| и теорема доказана.

В противном случае используем построение чередующегося пути для построения минимального покрытия. При заданном M чередующимся путём называется путь, рёбра которого поочерёдно берутся из M и E \ M. Разделим вершины V графа G на подмножества S_i, как описано ниже. Мы покажем, что объединение подмножеств с нечётными индексами является вершинным покрытием с |M| вершинами.

• Пусть S₀ состоит из всех вершин, не принадлежащих паросочетанию M.
• Для целого j ≥ 0, пусть S_2j+1 – множество всех вершин v, таких, что

1. v связано с некоторой вершиной из S_2j ребром из E \ M
2. v не входит ни в одно из ранее построенных множеств S_k, где k < 2j+1.

Если таких вершин нет, но остаются вершины, не содержащиеся в ранее построенных множествах S_k, выбираем произвольную из них и полагаем, что S_2j+1 состоит из этой единственной вершины.

• Для целого j ≥ 1, пусть S_2j – множество всех вершин u, таких, что u принадлежит некоторому ребру из M со второй вершиной из S_2j−1. Заметим, что для любой v из S_2j−1 существует вершина u, в паре, с которой они входят в паросочетание, поскольку в противном случае v была бы в S₀. Таким образом, M устанавливает однозначное соответствие между вершинами из S_2j−1 и вершинами из S_2j.

Относительно последнего члена этого списка могут возникнуть сомнения – а не может ли случиться так, что вершина u, принадлежащая некоторому ребру из M с вершиной v в S_2j−1, будет также содержаться и в множестве S_i с индексом, меньшим 2j, откуда последует, что множество S_i не образует отдельной части. Мы покажем, что такого произойти не может.

• Вершина v, появившаяся по построению первый раз в S_2j−1, не может вместе с вершиной из S_2k с k < j принадлежать паросочетанию, поскольку вершины S_2k либо не содержатся ни в какой дуге паросочетания (при k = 0), либо образуют дугу паросочетания вместе с дугой из S_2k−1 (при k ≥ 1).
• Вершина v не может паросочетаться с вершиной u из S_2k-1 с k ≤ j. Заметим, во-первых, что вершины из S_2k−1 с k < j паросочетаются с вершинами из S_2k с 2k < 2j−1 и, поэтому, не могут паросочетаться с v. Во-вторых, предположим, что v паросочетается с u из S_2j−1. Построим чередующийся путь с началом в вершине v путём выбора ребра из E \ M, содержащего конечную вершину v и вторую вершину из S_2j−2, ребра из M, содержащего полученную вершину и вершину из S_2j-3, и так далее. Получим связи вершин из S_i с вершинами из S_i−1 рёбрами из E \ M при i нечётном и рёбрами из M при i чётном. Процесс будет продолжаться, пока либо не достигнем S₀, либо множество S_2h+1 будет содержать единственную вершину, не имеющую рёбер, соединяющих её с нижним уровнем S_2h. Построим такой же путь, начиная с u. Объединяя эти два пути ребром vu из M, получим более длинный чередующийся путь P. Путь P является простым, поскольку в случае наличия общей вершины w на уровне i, получили бы нечётной длины цикл, содержащий вершину w, что невозможно в двудольных графах. Как следствие, конечные вершины пути P должны быть различными вершинами из S₀. Поскольку первое и последнее ребро P принадлежат E \ M, P содержит на единицу больше рёбер из E \ M чем из M. Тогда, убирая рёбра P ∩ M из M и добавляя рёбра P ∩ (E \ M) к M мы получим паросочетание с большим числом рёбер, чем в M, что противоречит максимальности M.

Мы показали, что каждая вершина множества V содержится ровно в одном множестве S_i. Отсюда следует, что рёбра M всегда соединяют вершины смежных уровней S_2j−1 и S_2j. Покажем, что никакое ребро E \ M не соединяет пару вершин, лежащих на чётных уровнях. Предположим, что ребро из E \ M соединяет вершину из S_2j с вершиной из S_2k при k ≤ j. Если v – вершина в S_2k с k < j, то любая вершина, сопряжённая с v ребром из E \ M, находится на уровне S_i с i ≤ 2k+1 < 2j, а потому v не может быть связано ребром из E \ M с вершиной из S_2j. С другой стороны, применяя тот же приём построения чередующегося пути, две вершины из S_2j не могут быть связаны друг с другом дугой из E \ M . Следовательно, любое ребро из M имеет в точности одну вершину в нечётном множестве и любое ребро из E \ M имеет по меньшей мере одну конечную вершину в нечётном множестве. Таким образом, объединение всех нечётных множеств даст вершинное покрытие с |M| вершинами.

Алгоритм

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

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

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

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

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

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

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

Ссылки

• Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. Graph Theory 1736–1936. — Oxford University Press, 1976. — С. 203–207. — ISBN 0-19-853916-9.
• J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — North Holland, 1976. — С. 74. — ISBN 0-444-19451-7.
• Gallai, Tibor. Maximum-minimum Sätze über Graphen // Acta Math. Acad. Sci. Hungar.. — 1958. — Т. 9, вып. 3-4. — С. 395–434. — doi:10.1007/BF02020271.
• Mika Göös, Jukka Suomela. 26th International Symposium on Distributed Computing (DISC), Salvador, Brazil, October 2012. — 2012.
• Kőnig, Dénes. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére // Matematikai és Természettudományi Értesítő. — 1916. — Т. 34. — С. 104–119.
• Kőnig, Dénes. Gráfok és mátrixok // Matematikai és Fizikai Lapok. — 1931. — Т. 38. — С. 116–119.
• László Lovász, M. D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.
• Lovász, László. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics. — 1972. — Т. 2, вып. 3. — С. 253–267. — doi:10.1016/0012-365X(72)90006-4.