Теорема Менгера

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

Периферийное подключение

Версия о связности ребер теоремы Менгера выглядит следующим образом:

Пусть G — конечный неориентированный граф, а x и y — две различные вершины. Тогда размер минимального разреза ребра для x и y (минимальное количество ребер, удаление которых разъединяет x и y ) равен максимальному количеству попарно непересекающихся ребер путей от x до y .

Импликацией для графа G является следующая версия:

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

Связность вершин

Утверждение вершинной связности теоремы Менгера выглядит следующим образом:

Пусть G — конечный неориентированный граф, а x и y — две несмежные вершины. Тогда размер минимального вершинного разреза для x и y (минимальное количество вершин, отличных от x и y , удаление которых разъединяет x и y ) равен максимальному числу попарно внутренне непересекающихся путей из x в y .

Следствием для всего графа G является эта версия:

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

Ориентированные графы

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

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

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

Для множеств вершин A,B ⊂ G (не обязательно непересекающихся) AB-путь — это путь в G с начальной вершиной в A конечной вершиной в B и без внутренних вершин ни в A, ни в B. , Мы допускаем путь с одной вершиной из A ∩ B и нулевыми ребрами. AB -разделитель размера k — это набор S из k вершин (которые могут пересекать A и B ) такой, что G−S не содержит AB -пути. AB -коннектор размера k представляет собой объединение k непересекающихся по вершинам AB -путей.

Теорема: Минимальный размер AB -разделителя равен максимальному размеру AB -соединителя.

Другими словами, если никакие k 1 вершины не соединяют A с B , то существует k непересекающихся путей из A в B. − Этот вариант подразумевает приведенное выше утверждение о связности вершин: для x,y ∈ G из предыдущего раздела применим текущую теорему к G −{ x,y } с A = N(x) , B = N(y) , соседними вершины x,y . Тогда набор вершин, соединяющих x и y, — это то же самое, что AB -разделитель, а удаление конечных вершин в наборе независимых xy -путей дает AB -соединитель.

Доказательство теоремы: ^{[ 1 ]} Индукция по числу ребер в G . Для G без ребер минимальный AB -сепаратор равен A ∩ B , который сам по себе является AB -коннектором, состоящим из одновершинных путей.

Для G, имеющего ребро e , мы можем по индукции предположить, что теорема верна для G−e . Если G−e имеет минимальный AB -сепаратор размера k существует AB -коннектор размера k , то в G−e и , следовательно, в G .

В противном случае пусть S — AB -сепаратор группы G−e размера меньше k , так что каждый AB -путь в G содержит вершину из S или ребро e . Размер S должен быть k-1 если бы он был меньше, S вместе с любой конечной точкой e был бы лучшим AB -разделителем G. , так как В G-S существует AB -путь через e , так как сам по себе слишком мал, чтобы быть AB- разделителем G. S Пусть v ₁ — более ранняя, а v ₂ — поздняя вершина e на таком пути. Тогда v ₁ достижима из A но не из B в G−S−e , а v ₂ достижима из B , но не из A. ,

Теперь пусть S ₁ = S ∪ {v ₁ } и рассмотрим минимальный AS ₁ -сепаратор T в G−e . Поскольку v ₂ недостижим из A в G−S ₁ , T также является AS ₁ -сепаратором в G . Тогда T также является AB -сепаратором в G (поскольку каждый AB -путь пересекает S ₁ ). Следовательно, он имеет размер не менее k . По индукции G−e содержит AS ₁ -коннектор C ₁ размера k . Из-за его размера конечные точки путей в нем должны быть ровно S ₁ .

Аналогично, если S ₂ = S ∪ {v ₂ } , минимальный S ₂ B -сепаратор имеет размер k и существует S с ₂ B -соединитель C ₂ размера k с путями, начальные точки которых совпадают в точности S ₂ .

, поскольку S1 _{Более того} отключает G , каждый путь в C1 _с внутренне не пересекается каждый путь в C ₂ , и мы можем определить AB -коннектор размера k в G путем объединения путей ( k−1 путей через S и один путь, проходящий через e=v ₁ v ₂ ). КЭД

Другие доказательства

Версия теоремы с направленными ребрами легко влечет за собой другие версии. Чтобы сделать вывод о версии вершин ориентированного графа, достаточно разбить каждую вершину v на две вершины v ₁ , v ₂ , причем все входящие ребра идут в v ₁ , все исходящие ребра идут из v ₂ и дополнительное ребро из v ₁ в v . ₂ . Из ориентированных версий теоремы сразу же вытекают неориентированные версии: достаточно заменить каждое ребро неориентированного графа парой направленных ребер (двуугольником).

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

Формулировка, которая для конечных орграфов эквивалентна приведенной выше формулировке:

Пусть A и B — множества вершин конечного орграфа G . Тогда существует семейство P непересекающихся AB -путей и AB -разделяющее множество, состоящее ровно из одной вершины каждого пути из P .

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

Это делается следующим образом: замените каждую вершину v в исходном орграфе D двумя вершинами v' , v'' и каждое ребро uv на ребро u'v'' ; кроме того, включите ребра v'v'' для каждой вершины v , которая не находится ни в A, ни в B . В результате получается двудольный граф, одна сторона которого состоит из вершин v' , а другая - из вершин v'' .

Применяя теорему Кенига, получаем паросочетание M и покрытие C того же размера. В частности, ровно один конец каждого ребра M находится в C . Добавьте к C все вершины a'' для a в A и все вершины ' для b в B. b Пусть P — множество всех AB -путей, состоящих из ребер uv в D, таких, что u'v'' принадлежит M. Пусть Q в исходном графе состоит из всех вершин v таких, что и v' , и v'' принадлежат C . Несложно проверить, что Q является AB -разделяющим множеством, что каждый путь в семействе P содержит ровно одну вершину из Q и каждая вершина в Q лежит на пути из P , как и требовалось. ^{[ 2 ]}

Бесконечные графы

Теорема Менгера справедлива для бесконечных графов и в этом контексте применима к минимальному разрезу между любыми двумя элементами, которые являются либо вершинами, либо концами графа ( Halin 1974 ). Следующий результат Рона Ахарони и Эли Бергера изначально был гипотезой, предложенной Полом Эрдешем , и до того, как был доказан, был известен как гипотеза Эрдеша-Менгера . Это эквивалентно теореме Менгера, когда граф конечен.

Пусть A и B — множества вершин в (возможно, бесконечном) орграфе G . Тогда существует семейство P непересекающихся A - B -путей и разделяющее множество, состоящее ровно из одной вершины каждого пути P. из

См. также

Ссылки

^ Геринг, Франк (2000). «Краткое доказательство теоремы Менгера» . Дискретная математика . 219 (1–3): 295–296. дои : 10.1016/S0012-365X(00)00088-1 .
^ Ахарони, Рон (1983). «Теорема Менгера для графов, не содержащих бесконечных путей» . Европейский журнал комбинаторики . 4 (3): 201–4. дои : 10.1016/S0195-6698(83)80012-2 .

Дальнейшее чтение

Менгер, Карл (1927). «Об общей теории кривых» . Находить. Математика . 10 :96-115. дои : 10.4064/fm-10-1-96-115 .
Аарон, Рон; Бергер, Эли (2008). «Теорема Менгера для бесконечных графов». Математические открытия . 176 (1): 1–62. arXiv : math/0509397 . Бибкод : 2009InMat.176....1A . дои : 10.1007/s00222-008-0157-3 . S2CID 15355399 .
Халин, Р. (1974). «Заметка о теореме Менгера для бесконечных локально конечных графов». Трактаты математического семинара Гамбургского университета . 40 : 111-114. дои : 10.1007/BF02993589 . S2CID 120915644 .

Внешние ссылки

[1] Геринг, Франк (2000). «Краткое доказательство теоремы Менгера» . Дискретная математика . 219 (1–3): 295–296. дои : 10.1016/S0012-365X(00)00088-1 .

[2] Ахарони, Рон (1983). «Теорема Менгера для графов, не содержащих бесконечных путей» . Европейский журнал комбинаторики . 4 (3): 201–4. дои : 10.1016/S0195-6698(83)80012-2 .

[ 1 ]

[ 2 ]