Теорема Кёнигса (теория графов) - Википедия - Kőnigs theorem (graph theory)

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

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

Параметр

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

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

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

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

Пример

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

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

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

Следующее доказательство дает способ построения минимального покрытия вершин из максимального совпадения. Позволять ${ Displaystyle G = (V, E)}$ - двудольный граф и пусть ${ Displaystyle L, R}$ - две части множества вершин ${ displaystyle V}$. Предположим, что ${ displaystyle M}$ максимальное соответствие для ${ displaystyle G}$. Ни одна вершина в вершинном покрытии не может покрывать более одного ребра ${ displaystyle M}$ (потому что половинное перекрытие краев предотвратит ${ displaystyle M}$ от совпадения в первую очередь), поэтому, если вершина покрывается ${ displaystyle | M |}$ вершины можно построить, это должно быть минимальное покрытие.^[4]

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

${ Displaystyle К = (L setminus Z) чашка (R cap Z).}$

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

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

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

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

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

Максимизировать 1_E · Икс

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

__________ А_грамм · Икс ≤ 1_V.

куда Икс вектор размера |E| в котором каждый элемент представляет собой вес ребра при дробном сопоставлении. 1_E вектор |E| единицы, поэтому в первой строке указывается размер соответствия. 0_E вектор |E| нули, поэтому вторая строка указывает на ограничение, что веса неотрицательны. 1_V вектор |V| те и А_грамм это матрица инцидентности из ГРАММ, поэтому третья строка указывает ограничение, согласно которому сумма весов около каждой вершины не превышает 1. Аналогично, минимальный дробный размер покрытия вершины в ${ Displaystyle G = (V, E)}$ является решением следующей ЛП:

Свести к минимуму 1_V · у

При условии: у ≥ 0_V

__________ А_грамм^Т · у ≥ 1_E.

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

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

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

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

Алгоритм

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

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

Пример

На графике, приведенном во введении, возьмите ${ displaystyle L}$ быть набором вершин в нижнем слое диаграммы и ${ displaystyle R}$ быть набором вершин в верхнем слое диаграммы. Слева направо обозначьте вершины нижнего слоя номерами 1,…, 7, а вершины верхнего слоя - числами 8,…, 14. Набор ${ displaystyle U}$ несовпадающих вершин из ${ displaystyle L}$ равно {1}. Чередующиеся пути, начиная с ${ displaystyle U}$ 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. Набор ${ displaystyle Z}$ следовательно, {1,3,5,7,10,11,13}, что приводит к ${ Displaystyle L setminus Z = {2,4,6 }}$, ${ Displaystyle R cap Z = {10,11,13 }}$ и минимальное вершинное покрытие ${ Displaystyle К = {2,4,6,10,11,13 }}$.

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

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

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

История

Теорема Кенига названа в честь венгерского математика. Денес Кёниг. Кёниг объявил в 1914 году и опубликовал в 1916 году результаты, что каждый обычный двудольный граф имеет идеальное соответствие,^[10] и в более общем плане хроматический индекс любого двудольного графа (то есть минимальное количество паросочетаний, на которое он может быть разбит) равно его максимальная степень^[11] - последнее утверждение известно как Теорема Кёнига о раскраске линий.^{[6]:Теорема 1.4.17, стр. 37ff.} Тем не мение, Бонди и Мёрти (1976) относят саму теорему Кёнига к более поздней работе Кёнига (1931).

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

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

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

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

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

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

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

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

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

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

Эгервари Теорема для взвешенных по ребрам графов

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

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

Максимум w-вес дробного совпадения определяется LP:^[6]:271

Максимизировать ш · Икс

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

__________ А_грамм · Икс ≤ 1_V.

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

Свести к минимуму 1_V · у

При условии: у ≥ 0_V

__________ А_грамм^Т · у ≥ ш.

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

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

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

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

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

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

Примечания

Рекомендации

• Biggs, E.K .; Ллойд; Уилсон, Р. Дж. (1976), Теория графов 1736–1936 гг., Oxford University Press, стр. 203–207, ISBN  0-19-853916-9.
• Кук, Уильям Дж.; Каннингем, Уильям Х .; Pulleyblank, Уильям Р.; Шрайвер, Александр (2011), Комбинаторная оптимизация, Ряд Уайли по дискретной математике и оптимизации, 33, John Wiley & Sons, стр. 48–49, ISBN  9781118031391.
• Бонди, Дж. А.; Мурти, США. (1976), Теория графов с приложениями, Северная Голландия, ISBN  0-444-19451-7.
• Галлай, Тибор (1958), "Максимум-минимум Sätze über Graphen", Acta Math. Акад. Sci. Подвешенный., 9 (3–4): 395–434, Дои:10.1007 / BF02020271, МИСТЕР  0124238.
• Göös, Mika; Суомела, Юкка (2012), "Схема аппроксимации без сублогарифмического времени для двудольного вершинного покрытия", 26-й Международный симпозиум по распределенным вычислениям (DISC), Сальвадор, Бразилия, октябрь 2012 г., arXiv:1205.4605, Bibcode:2012arXiv1205.4605G.
• Кениг, Денес (1916), "Gráfok és alkalmazásuk aterminánsok és halmazok elméletére", Matematikai és Természettudományi Értesítő, 34: 104–119.
• Кениг, Денес (1931), "Графок матриксок", Matematikai és Fizikai Lapok, 38: 116–119.
• Ловас, Ласло (1972), «Нормальные гиперграфы и гипотеза об идеальном графе», Дискретная математика, 2 (3): 253–267, Дои:10.1016 / 0012-365X (72) 90006-4, МИСТЕР  0302480.
• Ловас, Ласло (1974), "Теоремы о минимаксе для гиперграфов", Семинар по гиперграфу (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; посвящен Арнольду Россу), Берлин: Springer, стр. 111–126. Конспект лекций по математике, Vol. 411, г. Дои:10.1007 / BFb0066186, МИСТЕР  0406862.
• Сторер, Дж. А. (2001), Введение в структуры данных и алгоритмы, "Прогресс в компьютерных науках и прикладной логике", Springer, ISBN  9780817642532.