В математической области теории графов , теорема Кёниги , доказанная Dénes Konig ( 1931 ), описывает эквивалентность между максимальной согласующей задачей и минимальной задачей вершины крышки в двудольных графах . Он был независимо открыт также в 1931 году Йене Эгервари в более общем случае взвешенных графов .
Параметр
Вершина крышка в графе представляет собой набор вершин , что содержит , по меньшей мере , один конец каждого ребра, а вершина крышка минимальная , если никакой другой вершину крышки не имеет меньше вершин. [1] соответствие в графе представляет собой набор ребер никаких два из которых разделяет конечную точку, и соответствующее это максимум , если нет другого соответствия не имеет больше кромок. [2]
Из определения очевидно, что любое множество покрывающих вершин должно быть не меньше любого совпадающего множества (поскольку для каждого ребра в совпадении требуется по крайней мере одна вершина в покрытии). В частности, минимальный набор покрытий вершин по крайней мере такой же, как максимальный набор соответствий . Теорема Кёнига утверждает, что в любом двудольном графе минимальное множество покрытий вершин и максимальное множество соответствий фактически имеют одинаковый размер. [3]
Формулировка теоремы
В любом двудольном графе количество ребер в максимальном сопоставлении равно количеству вершин в минимальном покрытии вершин . [3]
Пример
Двудольный граф, показанный на иллюстрации выше, имеет 14 вершин; соответствие с шестью ребрами показано синим цветом, а покрытие вершины с шестью вершинами показано красным. Не может быть меньшего покрытия вершин, потому что любое покрытие вершин должно включать по крайней мере одну конечную точку каждого согласованного ребра (а также любого другого ребра), так что это минимальное покрытие вершин. Точно так же не может быть большего соответствия, потому что любое совпадающее ребро должно включать по крайней мере одну конечную точку в покрытии вершины, так что это максимальное совпадение. Теорема Кёнига утверждает, что равенство между размерами сопоставления и покрытия (в этом примере оба числа равны шести) в более общем случае применимо к любому двудольному графу.
Доказательства
Конструктивное доказательство
Следующее доказательство дает способ построения минимального покрытия вершин из максимального паросочетания. Позволять двудольный граф и пусть - две части множества вершин . Предположим, что максимальное соответствие для . Ни одна вершина в вершинном покрытии не может покрывать более одного ребра (потому что половинное перекрытие краев предотвратит от совпадения в первую очередь), поэтому, если вершина покрывается вершины можно построить, это должно быть минимальное покрытие. [4]
Чтобы построить такую крышку, пусть - множество несовпадающих вершин в (возможно, пустой), и пусть - множество вершин, находящихся либо в или связаны с путем чередования путей (путей, которые чередуются между ребрами, которые находятся в сопоставлении, и кромками, которые не находятся в сопоставлении). Позволять
Каждый край в либо принадлежит альтернативному пути (и имеет правую конечную точку в ), или он имеет левую конечную точку в . Ведь если совпадает, но не находится в чередующемся пути, то его левая конечная точка не может находиться в чередующемся пути (потому что два согласованных ребра не могут иметь общую вершину) и, таким образом, принадлежит . В качестве альтернативы, если не совпадает, но не находится в чередующемся пути, то его левая конечная точка не может находиться в чередующемся пути, поскольку такой путь может быть расширен путем добавления к нему. Таким образом,образует вершинное покрытие. [5]
Кроме того, каждая вершина в - конечная точка согласованного ребра. В самом деле, каждая вершина в совпадает, потому что это надмножество , множество несовпадающих левых вершин. И каждая вершина втакже должны быть сопоставлены, поскольку, если существовал альтернативный путь к несовпадающей вершине, то изменение сопоставления путем удаления сопоставленных ребер из этого пути и добавления несовпадающих ребер на их место увеличило бы размер сопоставления. Однако ни одно совпадающее ребро не может иметь обе конечные точки в. Таким образом, - вершинное покрытие мощности, равной , и должно быть минимальным вершинным покрытием. [5]
Доказательство с использованием двойственности линейного программирования
Чтобы объяснить это доказательство, мы сначала должны расширить понятие сопоставления до понятия дробного сопоставления - присвоения веса в [0,1] каждому ребру, так что сумма весов около каждой вершины не превосходит 1 (интегральное сопоставление - это частный случай дробного сопоставления, в котором веса находятся в {0,1}). Точно так же мы определяем дробное вершинное покрытие - присвоение неотрицательного веса каждой вершине так, чтобы сумма весов на каждом ребре была не меньше 1 (целое вершинное покрытие является частным случаем дробного вершинного покрытия. в котором веса находятся в {0,1}).
Максимальный размер дробного соответствия на графике является решением следующей линейной программы :
Увеличить 1 E · x
При условии: x ≥ 0 E
__________ G · х ≤ 1 V .
где x - вектор размера | E | в котором каждый элемент представляет собой вес ребра при дробном сопоставлении. 1 E - вектор | E | единицы, поэтому первая строка указывает размер соответствия. 0 E - вектор | E | нули, поэтому вторая строка указывает ограничение, что веса неотрицательны. 1 V - вектор | V | и те , G является матрица инцидентности из G, так что третья линия указывает на то ограничение , что сумма весов вблизи каждой вершины не превосходит 1. Аналогично, минимальный размер дробной вершинного покрова в является решением следующей ЛП:
Минимизировать 1 В · у
При условии: y ≥ 0 В
__________ С Т · у ≥ 1 Е .
где y - вектор размера | V | в котором каждый элемент представляет собой вес вершины дробного покрытия. Здесь первая строка - это размер покрытия, вторая строка представляет неотрицательность весов, а третья строка представляет требование, чтобы сумма весов около каждого края была не менее 1. Теперь минимальное дробное значение. cover LP - это в точности двойственная линейная программа максимального дробного соответствия LP. Следовательно, по теореме двойственности LP обе программы имеют одно и то же решение. Это верно не только для двудольных графов, но и для произвольных графов:
В любом графе наибольший размер дробного сопоставления равен наименьшему размеру дробного покрытия вершин.
Что делает двудольные графы особенными, так это то, что в двудольных графах обе эти линейные программы имеют оптимальные решения, в которых все значения переменных являются целыми числами. Это следует из того факта, что в многограннике дробного паросочетания двудольного графа все крайние точки имеют только целочисленные координаты, и то же самое верно для многогранника дробного совпадения вершин. Следовательно, из приведенной выше теоремы следует: [6] : 270
В любом двудольном графе наибольший размер сопоставления равен наименьшему размеру вершинного покрытия.
Алгоритм
Конструктивное доказательство, описанное выше, обеспечивает алгоритм для создания минимального покрытия вершин при максимальном сопоставлении. Таким образом, алгоритм Хопкрофта – Карпа для поиска максимального совпадения в двудольных графах также может использоваться для эффективного решения проблемы вершинного покрытия в этих графах. [7]
Несмотря на эквивалентность двух задач с точки зрения точных решений, они не эквивалентны для приближенных алгоритмов . Двудольные максимальные совпадения могут быть аппроксимированы произвольно точно за постоянное время с помощью распределенных алгоритмов ; напротив, аппроксимация минимального вершинного покрытия двудольного графа требует как минимум логарифмического времени. [8]
Пример
На графике, показанном во введении, возьмите быть набором вершин в нижнем слое диаграммы и быть набором вершин в верхнем слое диаграммы. Слева направо обозначьте вершины нижнего слоя номерами 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}, что приводит к , и минимальное вершинное покрытие .
Недвудольные графы
Для недвудольных графов минимальное покрытие вершин может быть больше максимального соответствия. Более того, эти две задачи сильно различаются по сложности: максимальное сопоставление может быть найдено за полиномиальное время для любого графа, а минимальное покрытие вершин является NP-полным .
Дополнение вершинного покрытия в любом графе является независимым множеством , поэтому минимальное вершинное покрытие является дополнительным к максимальному независимому множеству; поиск максимальных независимых множеств - еще одна NP-полная проблема. Эквивалентность согласования и покрытия, сформулированная в теореме Кёнига, позволяет вычислять минимальные вершинные покрытия и максимальные независимые множества за полиномиальное время для двудольных графов, несмотря на NP-полноту этих проблем для более общих семейств графов. [9]
История
Теорема Кёнига названа в честь венгерского математика Денеса Кёнига . Кёниг объявил в 1914 году и опубликовал в 1916 году результаты о том, что каждый регулярный двудольный граф имеет идеальное соответствие , [10] и, в более общем плане, что хроматический индекс любого двудольного графа (то есть минимальное количество сопоставлений, на которое он может быть разбит ) равна его максимальной степени [11] - последнее утверждение известно как теорема Кёнига о раскраске линий . [6] : теорема 1.4.17, с. 37ff. Однако Бонди и Мурти (1976) приписывают саму теорему Кёнига более поздней работе Кёнига (1931).
Согласно Biggs, Lloyd & Wilson (1976) , Кёниг приписал идею изучения сопоставлений в двудольных графах своему отцу, математику Дьюле Кёнигу . В венгерском языке имя Кенига имеет двойной острый акцент , но его теорема обычно пишется немецкими буквами с умляутом .
Связанные теоремы
Теорема Кёнига эквивалентно многих других теорем мин-макс в теории графов и комбинаторики, такими как Теорема Холла и теоремы Дилуорса . Поскольку двустороннее согласование является частным случаем максимального потока , теорема также вытекает из теоремы о максимальном потоке и минимальном разрезе . [12]
Связи с идеальными графами
Граф называется совершенным , если в каждом наведенном подграфе , то хроматическое число равно размером самой большой клики . Любой двудольный граф совершенен [13], потому что каждый его подграф либо двудольный, либо независимый; в двудольном графе, который не является независимым, хроматическое число и размер наибольшей клики равны двум, тогда как в независимом наборе хроматическое число и кликовое число равны единице.
Граф совершенен тогда и только тогда, когда его дополнение совершенно, [14] и теорема Кёнига может рассматриваться как эквивалентная утверждению, что дополнение двудольного графа совершенно. В самом деле, каждый цветовой класс в раскраске дополнения двудольного графа имеет размер не более 2, а классы размера 2 образуют соответствие, клика в дополнении графа G является независимым множеством в G , и поскольку мы уже описал независимый набор в двудольный граф G является дополнением к вершине крышки в G . Таким образом, любое согласование М в двудольный граф G с п вершинами соответствует к раскраске дополнения G с п - | M | цветов, которые по совершенству дополнений двудольных графов соответствуют независимому множеству в G с n - | M | вершин, что соответствует вершинному покрытию G с M вершинами. Наоборот, теорема Кёнига доказывает совершенство дополнений к двудольным графам - результат, доказанный в более явной форме Галлаи (1958) .
Можно также связать теорему Кёнига о раскраске линий с другим классом совершенных графов - линейными графами двудольных графов. Если G представляет собой график, линия графа L ( G ) имеет вершину для каждого ребра G и ребро для каждой пары смежных ребер в G . Таким образом, хроматическое число L ( G ) равно хроматическая индекс G . Если G двудольна, клики в L ( G ) - это в точности наборы ребер в G, имеющих общий конец. Теперь теорема Кёнига о раскраске линий, утверждающая, что хроматический индекс равен максимальной степени вершины в любом двудольном графе, может быть интерпретирована как утверждение, что линейный граф двудольного графа совершенен. [15]
Поскольку линейные графы двудольных графов совершенны, дополнения линейных графов двудольных графов также совершенны. Клика в дополнении к линии графа G просто в соответствии G . А раскраска дополнения к линейному графу группы G , когда G двудольна, представляет собой разбиение ребер графа G на подмножества ребер, имеющих общий конец; конечные точки разделяют каждый из этих подмножеств образуют вершину покрытие для G . Следовательно, сама теорема Кёнига также может быть истолкована как утверждение, что дополнения к линейным графам двудольных графов совершенны. [15]
Взвешенные варианты
Теорема Кенига может быть распространена на взвешенные графы .
Теорема Эгервари для реберно-взвешенных графов
Jen Egerváry (1931) рассматривал графы, в которых каждое ребро e имеет неотрицательный целочисленный вес w e . Весовой вектор обозначается w . W- вес соответствия является суммой весов ребер , участвующих в согласовании. W- вершина покров является мультимножеством вершин ( «мультимножество» означает , что каждая вершина может появиться несколько раз), в которых каждое ребро е примыкает , по меньшей мере , ж е вершин. Теорема Эгервари гласит:
В любом двудольном графе, взвешенном по ребрам, максимальный w- вес паросочетания равен наименьшему количеству вершин в w- вершинном покрытии.
Максимальный вес w дробного совпадения определяется LP: [6] : 271
Увеличить w · x
При условии: x ≥ 0 E
__________ G · х ≤ 1 V .
А минимальное количество вершин в дробном w- вершинном покрытии дает двойственная ЛП:
Минимизировать 1 В · у
При условии: y ≥ 0 В
__________ A G T · y ≥ w .
Как и в доказательстве теоремы Кенига, теорема двойственности LP подразумевает, что оптимальные значения равны (для любого графа), а тот факт, что граф является двудольным, означает, что эти программы имеют оптимальные решения, в которых все значения являются целыми числами.
Теорема для вершинно-взвешенных графов
Можно рассматривать граф, в котором каждая вершина v имеет неотрицательный целочисленный вес b v . Весовой вектор обозначается b . Б -вес из вершины покрова представляет собой сумму б V для всех V в крышке. Б Сопоставление является присвоением неотрицательного целого веса к каждому краю, таким образом, что сумма весов ребер , смежных с любой вершиной V не превосходит б v . Теорема Эгервари может быть расширена, используя аналогичные аргументы, на графы, которые имеют как веса ребер w, так и веса вершин b : [6] : 271
В любом двудольном графе, взвешенном по ребрам и вершинам , максимальный w- вес b- сопоставления равен минимальному b- весу вершин в w- вершинном покрытии.
Смотрите также
- Свойство Кёнига в гиперграфах
Заметки
- ^ Названный покрытием и минимальным покрытием соответственно Бонди и Мурти (1976) , стр. 73.
- ^ Бонди и Мурти (1976) , стр. 70.
- ^ Б Бонди и Мурти (1976) теорема 5.3, стр. 74; Cook et al. (2011) .
- ^ Бонди и Мурти (1976) , лемма 5.3, стр. 74.
- ^ Б Бонди & Мурти (1976) , стр. 74-75.
- ^ a b c d Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, 29 , Северная Голландия, ISBN 0-444-87916-1, Руководство по ремонту 0859549
- ^ Об этом алгоритме см. Storer (2001) , стр. 319, а о связи с вершинным покрытием см. Стр. 342.
- ^ Goos & Суомела (2012) .
- ^ Шторер (2001) , упражнение 261, стр. 342 .
- ↑ На плакате, показанном на Международном конгрессе математиков в Берлинев 1998 годуи снова на Международной конференции по теории графов в Блед'07, Харальд Гропп указал, что тот же результат уже появляется на языке конфигураций в тезисе Эрнста Стейница 1894 года..
- ^ Биггс, Ллойд и Уилсон (1976) .
- ^ Кук и др. (2011) .
- ^ "Тривиально", согласно Ловасу (1974) .
- ^ Это идеальная теорема о графике Ловаса (1972)
- ^ а б Ловас (1974) .
Рекомендации
- Биггс, EK; Ллойд; Уилсон, Р.Дж. (1976), Теория графов 1736–1936 , Oxford University Press, стр. 203–207, ISBN 0-19-853916-9.
- Кук, Уильям Дж .; Каннингем, Уильям Х .; Pulleyblank, Уильям Р .; Шрайвер, Александр (2011), Комбинаторная оптимизация , Ряд Уайли по дискретной математике и оптимизации, 33 , John Wiley & Sons, стр. 48–49, ISBN 9781118031391.
- Bondy, JA ; Мурти, USR (1976), Теория графов с приложениями , Северная Голландия, ISBN 0-444-19451-7.
- Галлай, Тибор (1958), «Максимум-минимум Sätze über Graphen», Acta Math. Акад. Sci. Повесили. , 9 (3-4): 395-434, DOI : 10.1007 / BF02020271 , МР 0124238.
- Гёш, Мика; Суомела, Юкка (2012), «Нет схемы аппроксимации сублогарифмического времени для двудольного вершинного покрытия», 26-й Международный симпозиум по распределенным вычислениям (DISC), Сальвадор, Бразилия, октябрь 2012 г. , arXiv : 1205.4605 , Bibcode : 2012arXiv1205.4605G.
- Kőnig, Dénes (1916), "Gráfok és alkalmazásuk aterminánsok és halmazok elméletére", Matematikai és Természettudományi Értesítő , 34 : 104–119.
- Kőnig, Dénes (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.
- Ловас, Ласло (1974), "Минимаксные теоремы для гиперграфов", семинар по гиперграфам (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; посвященный Арнольду Россу) , Берлин: Springer, стр. 111–126 . Конспект лекций по математике, Vol. 411, DOI : 10.1007 / BFb0066186 , МР 0406862.
- Storer, JA (2001), Введение в структуры данных и алгоритмы , Progress in Computer Science and Applied Logic Series, Springer, ISBN 9780817642532.