Теорема Кёнига (теория графов)

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

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

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

Параметр

Покрытие вершин в графе — это набор вершин, включающий по крайней мере одну конечную точку каждого ребра, и покрытие вершин минимально, если никакое другое покрытие вершин не имеет меньшего количества вершин. ^[1] Сопоставление в графе — это набор ребер, никакие два из которых не имеют общей конечной точки, и сопоставление максимально , если никакое другое сопоставление не имеет большего количества ребер. ^[2]

Из определения очевидно, что любой набор вершин-покрытий должен быть по крайней мере такого же размера, как любой набор сопоставлений (так как для каждого ребра в сопоставлении, по крайней мере одна вершина необходима в покрытии). В частности, минимальный набор вершин-покрытий по крайней мере такого же размера, как максимальный набор сопоставлений . Теорема Кёнига утверждает, что в любом двудольном графе минимальный набор вершин-покрытий и максимальный набор сопоставлений фактически имеют одинаковый размер. ^[3]

Формулировка теоремы

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

Пример

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

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

Конструктивное доказательство

Минимальное сокращение в сети потока ${\displaystyle (S,T)}$ ${\displaystyle G'_{\infty }}$

Следующее доказательство предоставляет способ построения минимального вершинного покрытия из максимального паросочетания. Пусть будет двудольным графом и пусть будут двумя частями множества вершин . Предположим, что является максимальным паросочетанием для . ${\displaystyle G=(V,E)}$ ${\displaystyle A,B}$ ${\displaystyle V}$ ${\displaystyle M}$ ${\displaystyle G}$

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

Размер максимального паросочетания в является размером максимального потока в , который, в свою очередь, является размером минимального разреза в сети , как следует из теоремы о максимальном потоке и минимальном разрезе . ${\displaystyle |M|}$ ${\displaystyle G}$ ${\displaystyle G'_{\infty }}$ ${\displaystyle G'_{\infty }}$

Пусть будет минимальным разрезом. Пусть и , таким образом, что и . Тогда минимальный разрез состоит только из ребер, идущих от до или от до , так как любое ребро от до сделало бы размер разреза бесконечным. ${\displaystyle (S,T)}$ ${\displaystyle A=A_{S}\cup A_{T}}$ ${\displaystyle B=B_{S}\cup B_{T}}$ ${\displaystyle A_{S},B_{S}\subset S}$ ${\displaystyle A_{T},B_{T}\subset T}$ ${\displaystyle s}$ ${\displaystyle A_{T}}$ ${\displaystyle B_{S}}$ ${\displaystyle t}$ ${\displaystyle A_{S}}$ ${\displaystyle B_{T}}$

Следовательно, размер минимального разреза равен . С другой стороны, является вершинным покрытием, так как любое ребро, не инцидентное вершинам из и должно быть инцидентно паре вершин из и , что противоречило бы тому факту, что между и нет ребер . ${\displaystyle |A_{T}|+|B_{S}|}$ ${\displaystyle A_{T}\cup B_{S}}$ ${\displaystyle A_{T}}$ ${\displaystyle B_{S}}$ ${\displaystyle A_{S}}$ ${\displaystyle B_{T}}$ ${\displaystyle A_{S}}$ ${\displaystyle B_{T}}$

Таким образом, является минимальным вершинным покрытием . ^[4] ${\displaystyle A_{T}\cup B_{S}}$ ${\displaystyle G}$

Конструктивное доказательство без концепций потока

Ни одна вершина в вершинном покрытии не может покрывать более одного ребра (потому что полуперекрытие ребер изначально не позволило бы создать соответствие), поэтому если вершинное покрытие с вершинами может быть построено, то оно должно быть минимальным покрытием. ^[5] ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle |M|}$

Чтобы построить такое покрытие, пусть будет множеством непарных вершин в (возможно, пустых), и пусть будет множеством вершин, которые либо находятся в , либо соединены с чередующимися путями (путями, которые чередуются между ребрами, которые находятся в паросочетании, и ребрами, которые не находятся в паросочетании). Пусть ${\displaystyle U}$ ${\displaystyle A}$ ${\displaystyle Z}$ ${\displaystyle U}$ ${\displaystyle U}$

${\displaystyle K=(A\setminus Z)\cup (B\cap Z).}$

Каждое ребро в либо принадлежит чередующемуся пути (и имеет правую конечную точку в ), либо имеет левую конечную точку в . Ибо, если совпадает, но не находится в чередующемся пути, то его левая конечная точка не может находиться в чередующемся пути (потому что два сопоставленных ребра не могут иметь общую вершину) и, таким образом, принадлежит . В качестве альтернативы, если не совпадает, но не находится в чередующемся пути, то его левая конечная точка не может находиться в чередующемся пути, поскольку такой путь может быть расширен путем добавления к нему. Таким образом, образует вершинное покрытие. ^[6] ${\displaystyle e}$ ${\displaystyle E}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle e}$ ${\displaystyle A\setminus Z}$ ${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle K}$

Кроме того, каждая вершина в является конечной точкой сопоставленного ребра. Ведь каждая вершина в сопоставлена, поскольку является надмножеством , множества несопоставленных левых вершин. И каждая вершина в также должна быть сопоставлена, поскольку если бы существовал чередующийся путь к несопоставленной вершине, то изменение сопоставления путем удаления сопоставленных ребер из этого пути и добавления несопоставленных ребер на их место увеличило бы размер сопоставления. Однако ни одно сопоставленное ребро не может иметь обе свои конечные точки в . Таким образом, является вершинным покрытием мощности, равной , и должно быть минимальным вершинным покрытием. ^[6] ${\displaystyle K}$ ${\displaystyle A\setminus Z}$ ${\displaystyle Z}$ ${\displaystyle U}$ ${\displaystyle B\cap Z}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle M}$

Доказательство с использованием двойственности линейного программирования

Чтобы объяснить это доказательство, нам сначала нужно расширить понятие сопоставления до понятия дробного сопоставления — назначения веса в [0,1] каждому ребру, так что сумма весов около каждой вершины не превышает 1 (целочисленное сопоставление — это частный случай дробного сопоставления, в котором веса находятся в {0,1}). Аналогично мы определяем дробное вершинное покрытие — назначение неотрицательного веса каждой вершине, так что сумма весов в каждом ребре не менее 1 (целочисленное вершинное покрытие — это частный случай дробного вершинного покрытия, в котором веса находятся в {0,1}).

Максимальный размер дробного паросочетания в графе является решением следующей линейной программы : ${\displaystyle G=(V,E)}$

Увеличить 1 _E · x

При условии: x ≥ 0 _E

__________ А _Г · х ≤ 1 _В .

где x — вектор размера | E |, в котором каждый элемент представляет вес ребра в дробном паросочетании. 1 _E — вектор из | E | единиц, поэтому первая строка указывает размер паросочетания. 0 _E — вектор из | E | нулей, поэтому вторая строка указывает ограничение, что веса неотрицательны. 1 _V — вектор из | V | единиц, а A _G — матрица инцидентности G , поэтому третья строка указывает ограничение, что сумма весов вблизи каждой вершины не превышает 1. Аналогично, минимальный дробный размер вершинного покрытия в является решением следующей LP: ${\displaystyle G=(V,E)}$

Минимизировать 1 _В · у

При условии: y ≥ 0 _В

__________ А _Г ^Т · у ≥ 1 _Е .

где y — вектор размера |V|, в котором каждый элемент представляет вес вершины в дробном покрытии. Здесь первая строка — размер покрытия, вторая строка — неотрицательность весов, а третья строка — требование, чтобы сумма весов около каждого ребра была не менее 1. Теперь минимальное дробное покрытие LP — это в точности двойственная линейная программа максимального дробного паросочетания LP. Следовательно, по теореме о двойственности LP обе программы имеют одно и то же решение. Этот факт верен не только в двудольных графах, но и в произвольных графах:

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

Что делает двудольные графы особенными, так это то, что в двудольных графах обе эти линейные программы имеют оптимальные решения, в которых все значения переменных являются целыми числами. Это следует из того факта, что в дробном многограннике соответствия двудольного графа все крайние точки имеют только целые координаты, и то же самое верно для дробного многогранника вершинного покрытия. Поэтому из вышеприведенной теоремы следует: ^[7]

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

Алгоритм

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

Несмотря на эквивалентность двух задач с точки зрения точных решений, они не эквивалентны для алгоритмов аппроксимации . Двудольные максимальные паросочетания могут быть аппроксимированы произвольно точно за постоянное время с помощью распределенных алгоритмов ; в отличие от этого, аппроксимация минимального вершинного покрытия двудольного графа требует по крайней мере логарифмического времени. ^[9]

Пример

В графе, показанном во введении, возьмем в качестве множества вершин в нижнем слое диаграммы, а в качестве множества вершин в верхнем слое диаграммы. Слева направо обозначим вершины в нижнем слое числами 1, …, 7, а вершины в верхнем слое числами 8, …, 14. Множество несовпадающих вершин из равно {1}. Чередующиеся пути, начинающиеся с , равны 1–10–3–13–7, 1–10–3–11–5–13–7, 1–11–5–13–7, 1–11–5–10–3–13–7, и все подпути из них начинаются с 1. Таким образом, множество равно {1,3,5,7,10,11,13}, что приводит к , и минимальному вершинному покрытию . ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle U}$ ${\displaystyle L}$ ${\displaystyle U}$ ${\displaystyle Z}$ ${\displaystyle L\setminus Z=\{2,4,6\}}$ ${\displaystyle R\cap Z=\{10,11,13\}}$ ${\displaystyle K=\{2,4,6,10,11,13\}}$

Недвудольные графы

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

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

История

Теорема Кёнига названа в честь венгерского математика Денеша Кёнига . Кёниг объявил в 1914 году и опубликовал в 1916 году результаты о том, что каждый регулярный двудольный граф имеет совершенное паросочетание , ^[11] и, в более общем смысле, что хроматический индекс любого двудольного графа (то есть минимальное число паросочетаний, на которые его можно разбить) равен его максимальной степени ^[12] — последнее утверждение известно как теорема Кёнига о раскраске линий . ^[13] Однако Бонди и Мёрти (1976) приписывают саму теорему Кёнига более поздней работе Кёнига (1931).

Согласно Biggs, Lloyd & Wilson (1976), Кёниг приписал идею изучения паросочетаний в двудольных графах своему отцу, математику Дьюле Кёнигу . В венгерском языке имя Кёнига имеет двойной острый ударение , но его теорему иногда пишут (неправильно) немецкими буквами, с умлаутом .

Связанные теоремы

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

Связи с идеальными графами

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

Граф совершенен тогда и только тогда, когда его дополнение совершенно ^[16] , и теорему Кёнига можно рассматривать как эквивалент утверждения, что дополнение двудольного графа совершенно. Так как каждый цветовой класс в раскраске дополнения двудольного графа имеет размер не более 2, а классы размера 2 образуют паросочетание, клика в дополнении графа G является независимым множеством в G , и, как мы уже описали, независимое множество в двудольном графе G является дополнением вершинного покрытия в G. Таким образом, любое паросочетание M в двудольном графе G с n вершинами соответствует раскраске дополнения к G с n - | M | цветами, что в силу совершенства дополнений двудольных графов соответствует независимому множеству в G с n - | M | вершинами, что соответствует вершинному покрытию G с M вершинами. Напротив, теорема Кёнига доказывает совершенство дополнений двудольных графов, результат, доказанный в более явной форме Галлаи (1958).

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

Поскольку линейные графы двудольных графов являются совершенными, дополнения линейных графов двудольных графов также являются совершенными. Клика в дополнении линейного графа графа G является просто паросочетанием в G . А раскраска в дополнении линейного графа графа G , когда G является двудольным, является разбиением ребер графа G на подмножества ребер, имеющих общую конечную точку; конечные точки, общие для каждого из этих подмножеств, образуют вершинное покрытие для графа G . Следовательно, сама теорема Кёнига может также интерпретироваться как утверждение о том, что дополнения линейных графов двудольных графов являются совершенными. ^[17]

Взвешенные варианты

Теорему Кёнига можно распространить на взвешенные графы .

ЭгервариТеорема для графов с рёберным весом

Jenő Egerváry (1931) рассматривал графы, в которых каждое ребро e имеет неотрицательный целый вес w _e . Вектор веса обозначается w . W- вес паросочетания — это сумма весов ребер, участвующих в паросочетании. W -покрытие вершин — это мультимножество вершин («мультимножество» означает, что каждая вершина может встречаться несколько раз), в котором каждое ребро e смежно по крайней мере с w _e вершинами. Теорема Эгервари гласит :

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

Максимальный w- вес дробного соответствия определяется LP: ^[18]

Увеличить w · x

При условии: x ≥ 0 _E

__________ А _Г · х ≤ 1 _В .

А минимальное число вершин в дробном w -вершинном покрытии задается двойственным LP:

Минимизировать 1 _В · у

При условии: y ≥ 0 _В

__________ А _Г ^Т · у ≥ ш .

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

Теорема для графов с вершинным весом

Можно рассмотреть граф, в котором каждая вершина v имеет неотрицательный целочисленный вес b _v . Вектор веса обозначается как b . B -вес вершинного покрытия равен сумме b _v для всех v в покрытии. B -сопоставление — это присвоение неотрицательного целочисленного веса каждому ребру, так что сумма весов ребер, смежных с любой вершиной v , не превышает b _v . Теорему Эгервари можно распространить, используя похожие рассуждения, на графы, которые имеют как вес ребер w , так и вес вершин b : ^[18]

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

Смотрите также

• Свойство Кёнига в гиперграфах

Примечания

1. Названы покрытием и минимальным покрытием соответственно Бонди и Мёрти (1976), стр. 73.
2. Бонди и Мурти (1976), стр. 70.
3. Bondy & Murty (1976), Теорема 5.3, стр. 74; Cook et al. (2011).
4. Чеза-Бьянки (2020).
5. Бонди и Мурти (1976), Лемма 5.3, стр. 74.
6. Bondy & Murty (1976), стр. 74–75.
7. Ловас и Пламмер (1986), с. 270.
8. Для этого алгоритма см. Storer (2001), стр. 319, а для связи с вершинным покрытием см. стр. 342.
9. Гёёс и Суомела (2014).
10. Сторер (2001), Упражнение 261, стр. 342.
11. В плакате, представленном на Международном конгрессе математиков в Берлине в 1998 году, а затем на Международной конференции по теории графов в Бледе'07, Харальд Гропп указал, что тот же результат уже появляется на языке конфигураций в диссертации Эрнста Штайница 1894 года .
12. Биггс, Ллойд и Уилсон (1976).
13. Ловас и Пламмер (1986), Теорема 1.4.17, стр. 37 и далее.
14. Кук и др. (2011).
15. «Тривиально», по словам Ловаса (1974).
16. Это теорема Ловаса о совершенном графе (1972)
17. Lovász (1974).
18. Ловас и Пламмер (1986), стр. 271.

Ссылки

• Биггс, EK; Ллойд; Уилсон, RJ (1976), Теория графов 1736–1936 , Oxford University Press, стр. 203–207, ISBN 0-19-853916-9.
• Чеза-Бьянки, Николо (11 апреля 2020 г.), Сопоставления и теорема о максимальном потоке и минимальном разрезе (PDF)
• Кук, Уильям Дж .; Каннингем, Уильям Х.; Пуллибланк, Уильям Р .; Шрайвер, Александр (2011), Комбинаторная оптимизация, Wiley Series in Discrete Mathematics and Optimization, т. 33, John Wiley & Sons, стр. 48–49, ISBN 9781118031391.
• Бонди, JA ; Мурти, USR (1976), Теория графов с приложениями , Северная Голландия, ISBN 0-444-19451-7.
• Галлай, Тибор (1958), «Максимум-минимум Sätze über Graphen», Acta Mathematica Academiae Scientiarum Hungaricae , 9 (3–4): 395–434, doi : 10.1007/BF02020271, MR  0124238.
• Гёос, Мика; Суомела, Юкка (2014), «Нет схемы сублогарифмической аппроксимации для двудольного вершинного покрытия», Distributed Computing , 27 (6): 435–443, arXiv : 1205.4605 , doi : 10.1007/s00446-013-0194-z, MR  3280546 , S2CID  13513566
• Кениг, Денес (1916), «Графок - это алкалмаз, детерминант - это халмазок эльмелетер», Matematikai é Természettudomány Értesítő , 34 : 104–119..
• Кениг, Денес (1931), «Gráfok és mátrixok», Matematikai és Fizikai Lapok , 38 : 116–119..
• Ловас, Ласло (1972), «Нормальные гиперграфы и гипотеза о совершенном графе», Дискретная математика , 2 (3): 253–267, doi :10.1016/0012-365X(72)90006-4, MR  0302480.
• Lovász, László (1974), "Теоремы минимакса для гиперграфов", Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; посвящается Арнольду Россу) , Lecture Notes in Mathematics, т. 411, Berlin: Springer, стр. 111–126, doi :10.1007/BFb0066186, ISBN 978-3-540-06846-4, МР  0406862.
• Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
• Сторер, Дж. А. (2001), Введение в структуры данных и алгоритмы , Progress in Computer Science and Applied Logic Series, Springer, ISBN 9780817642532.