В математической дисциплине теории графов теорема Менгера гласит, что в конечном графе размер минимального множества разрезов равен максимальному числу непересекающихся путей, которые можно найти между любой парой вершин . Доказанная Карлом Менгером в 1927 году, она характеризует связность графа. Она обобщается теоремой о максимальном потоке и минимальном разрезе , которая является взвешенной, рёберной версией и которая, в свою очередь, является частным случаем теоремы о сильной двойственности для линейных программ.
Версия теоремы Менгера для реберной связности выглядит следующим образом:
Для графа G имеет место следующая версия:
Утверждение о связности вершин теоремы Менгера выглядит следующим образом:
Следствием для всего графа G является такая версия:
Все эти утверждения как в реберной, так и в вершинной версии остаются верными в ориентированных графах (при рассмотрении направленных путей).
Большинство прямых доказательств рассматривают более общее утверждение, чтобы позволить доказать его по индукции. Также удобно использовать определения, которые включают некоторые вырожденные случаи. Следующее доказательство для неориентированных графов работает без изменений для ориентированных графов или мультиграфов, при условии, что мы берем путь для обозначения направленного пути.
Для множеств вершин A,B ⊂ G (не обязательно непересекающихся) AB-путь — это путь в G с начальной вершиной в A , конечной вершиной в B , и без внутренних вершин ни в A , ни в B . Мы допускаем путь с единственной вершиной в A ∩ B и нулевыми ребрами. AB-разделитель размера k — это множество S из k вершин (которые могут пересекать A и B ), такое, что G−S не содержит AB -путей. AB-соединитель размера k — это объединение k вершинно-непересекающихся 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 , то в G−e , а значит, и в G , существует AB -коннектор размера k .
В противном случае пусть S будет AB -разделителем G−e размера меньше k , так что каждый AB -путь в G содержит вершину S или ребро e . Размер S должен быть k-1 , так как если бы он был меньше, S вместе с любой конечной точкой e был бы лучшим AB -разделителем G . В G−S есть AB -путь через e , так как S сам по себе слишком мал, чтобы быть AB -разделителем G . Пусть v 1 будет более ранней, а v 2 - более поздней вершиной e на таком пути. Тогда v 1 достижима из A , но не из B в G−S−e , в то время как v 2 достижима из B , но не из A .
Теперь пусть S 1 = S ∪ {v 1 } и рассмотрим минимальный AS 1 -разделитель T в G−e . Так как v 2 недостижим из A в G−S 1 , T также является AS 1 -разделителем в G . Тогда T также является AB -разделителем в G (потому что каждый AB -путь пересекает S 1 ). Следовательно, он имеет размер не менее k . По индукции G−e содержит AS 1 -соединитель C 1 размера k . Из-за его размера конечные точки путей в нем должны быть в точности S 1 .
Аналогично, пусть S 2 = S ∪ {v 2 } , минимальный S 2 B -разделитель имеет размер k , и существует S 2 B -соединитель C 2 размера k с путями, начальные точки которых в точности совпадают с S 2 .
Более того, поскольку S 1 разъединяет G , каждый путь в C 1 внутренне разъединен с каждым путем в C 2 , и мы можем определить AB -соединитель размера k в G путем конкатенации путей ( k−1 путей через S и один путь, проходящий через e=v 1 v 2 ). ЧТЭК
Версия теоремы с направленными ребрами легко подразумевает другие версии. Чтобы вывести версию с направленными вершинами графа, достаточно разбить каждую вершину v на две вершины v 1 , v 2 , со всеми входящими ребрами, идущими в v 1 , всеми исходящими ребрами, идущими из v 2 , и дополнительным ребром из v 1 в v 2 . Направленные версии теоремы немедленно подразумевают ненаправленные версии: достаточно заменить каждое ребро ненаправленного графа парой направленных ребер (двуугольником).
Версия направленного ребра в свою очередь следует из ее взвешенного варианта, теоремы о максимальном потоке и минимальном разрезе . Ее доказательства часто являются доказательствами корректности для алгоритмов максимального потока. Она также является частным случаем еще более общей (сильной) теоремы о двойственности для линейных программ .
Формулировка, которая для конечных орграфов эквивалентна приведенной выше формуле, имеет вид:
В этой версии теорема довольно легко следует из теоремы Кёнига : в двудольном графе минимальный размер покрытия равен максимальному размеру паросочетания.
Это делается следующим образом: заменяем каждую вершину 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). Следующий результат Рона Ахарони и Эли Бергера изначально был гипотезой, предложенной Полом Эрдёшем , и до доказательства был известен как гипотеза Эрдёша–Менгера . Она эквивалентна теореме Менгера, когда граф конечен.