Изменения

Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как ''<tex>k</tex>-связность'' и ''количество непересекающихся путей'' относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ''ориентированном'' или ''неориентированном'' графе, и подразумеваем ли ''реберную <tex>k</tex>-связность'' и ''реберно непересекающиеся пути'' или же ''вершинную <tex>k</tex>-связность'' и ''вершинно непересекающиеся пути''. ==Подготовка к доказательству==Для доказательства мы будем пользоваться развитой раннее [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуется понятие [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе {{Теорема---}} дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]]. Кроме того, потребуется лемма о целочисленности потока, которую сейчас и докажем:{{Лемма|about=Теорема Менгера для k связностио целочисленности потока|statement=Наименьшее число вершин&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Если пропускные способности всех ребер целочисленные (сеть целочислена), разделяющих две несмежные вершины s и tто существует максимальный поток, равно наибольшему числу непересекающихся простых (s-t) цепейцелочисленный на каждом ребре.

{{Определениеdefinition=Множество S вершин, ребер или вершин и ребер разделяет u и v, если u и v принадлежат различным компонентам графа <math>G:# В начале берем какой-S</math>}} Очевидно, что если k вершин разделяют s и tнибудь поток за начальный (например, то сущесвует не более k непересекающихся простых (s-tнулевой) цепей.Теперь покажем, что k вершин графа разделяют s :# В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и t, существует k непересекающихся простых (s-t) цепей. Для k=1 это очевидноувеличиваем поток на пропускную способность этого пути. Пусть, для некоторого :# Повторяем пункт <math>ktex>12</mathtex> это неверно. Возьмем h - наименьшее такое k и F - граф с наименьшим числом вершин, для которого при выбранном h теорема не верна. Будем удалять из F ребрадо тех пор, пока не получим G такой, что находится хоть какой-то путь в G s и t разделяют h вершин, а в <math>G-x</math> <math>h-1</math> вершина, где x - произвольное ребро графа Gостаточной сети.

{{Утверждение|statement=Из определения G следует:То, что для всякого его ребра x существует множество <math>S(x)</math> из <math>h-1</math> вершинполучится в конце, который будет максимальным потоком. В случае целочисленной сети достаточно в <math>G-x</math> разделяют s и t. Далеекачестве начального приближения взять нулевой поток, граф <math>G-S(x)</math> содержит по крайней мере одну (s-t) цепь, так как граф G имеет h вершин, разделяющих s и t в G. Каждая такая (s-t) цепь должна содержать ребро <math>x=uv</math>, поскольку она не является цепью в <math>G-x</math>. Поэтому <math>uтрудно видеть,v \notin Sчто на каждой итерации (xв том числе и последней)</math>этот поток будет оставаться целочисленным, что и если <math>u <> s,t </math> то <math>S(x) \cup {u}</math> разделяет s и t в Gдокажет требуемое.

|about=I|statement=Если в графе G нет вершинсети, где все пропускные способности ребер равны <tex>1</tex>, смежных одновременно с s существует целочисленный поток величиной <tex>L</tex> то существует и t<tex>L</tex> реберно непересекающихся путей.

Если в G есть вершина w: Считаем, что <tex>u</tex> {{---}} источник, смежная как с s<tex>v</tex> {{---}} сток.: В начале поймем, так и с tчто если поток не нулевой, то существует маршрут из <tex>u</tex> в графе <mathtex>G-wv</mathtex> для разделения s и t требуется лежащий только на ребрах с потоком равным <mathtex>h - 1</mathtex> непересекающихся . В самом деле, если бы такого маршрута не существовало, то можно было бы выделить множество вершин до которых такие маршруты из вершины <tex>u</tex> существуют, не включающее <tex>v</tex>, и по нему построить разрез. Поток через такой разрез, очевидно равен нулю, видим противоречие (s-t) цепейт.к. Добавляя w<tex>f(U, получаем в графе G h непересекающихся (s-tV) цепей=|f|</tex>, что противоречит предположению смотри [[Разрез, лемма о графе F}}потоке через разрез|первую лемму]]).

{{Утверждение|about=II|statement=любой набор W:Итак, содержащий h вершин и разделяющий s и t является смежным с s или t |proof=Пусть W найдем какой- произвольный набор h вершин, разделяющих s и t в G. Цепь, соединяющую s с некоторой вершиной <math>w_i \in W</math> и не содержащую других вершин нибудь маршрут из W будем называть (s-W) цепью. Аналогично назовем (W-t) цепь. Обозначим наборы всех (s-W) и (W-t) цепей <mathtex>P_su</mathtex> и <math>P_t</math> соответственно.Тогда каждая (s-t) цепь начинается с элемента из в <mathtex>P_sv</mathtex> и заканчивается элементом из лежащий только на ребрах где поток равен <mathtex>P_t1</mathtex>, поскольку любая цепь содержит вершину из W. Общие вершины цепей из <math>P_s</math> и <math>P_t</math> принадлежат набору W, так как по крайней мере одна цепь из каждого набора <math>P_s</math> и <math>P_t</math> содержит (любую) вершину <math>w_i</math>, и если бы существовала некоторая вершина, не принадлежащая набору W, но содержащаяся сразу и Удалив все ребра находящиеся в (s-W) этом маршруте и в (W-t) цепиоставив все остальное неизменным, то нашлась бы (s-t) цепь, не имеющая вершин из W. Наконец, выполняется либо равенство придем к целочисленному потоку величиной <mathtex>P_sL-W={s}1</mathtex>. Ясно, либо равенство что можно повторить тоже самое еще <mathtex>P_t L- W={t}1</mathtex>раз, поскольку в противном случае либо <math>P_s</math> вместе с ребрами <math>\{w_1t,w_2t...\}</math>и, либо таким образом мы выделим <mathtex>P_tL</mathtex> вместе с ребрами <math>\{sw_1,sw_2...\}</math> образуют связные графы с меньшим числом вершин, чем у G, в которых s и t не смежны, и, следовательно, в каждом из них имеется h реберно непересекающихся (s-t) цепей. Объединяя (s-W) и (W-t) части этих цепей, образуем в графе G h непересекающихся (s-t) цепей. Мы пришли к противоречию. Утверждение доказаномаршрутов.

{{Теорема|about=Менгера о реберной двойственности в ориентированном графе|statement=Между вершинами <tex>u</tex> и <tex>v</tex> существует <tex>L</tex> реберно непересекающихся путей тогда и только тогда, когда после удаления любых <tex>(L-1)</tex> ребер существует путь из <tex>u</tex> в <tex>v</tex>.|proof=<tex>\Leftarrow</tex> :Как и прежде, пусть <tex>u</tex> {{---}}источник, а <tex>v</tex> {{---}} сток. :Назначим каждому ребру пропускную способность <tex>1</tex>. Тогда существует максимальный поток, целочисленный на каждом ребре (по лемме). :По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в этом разрезе <tex>L-1</tex> ребер, и тогда, раз <tex>u</tex> и <tex>v</tex> находятся в разных частях разреза и, существует путь из <tex>u</tex> в <tex>v</tex>, то в разрезе останется хотя бы еще одно ребро. Это значит, что пропускная способность разреза и вместе с ним величина потока не меньше <tex>L</tex>. А так как поток целочисленный, то это и означает, что найдется <tex> L</tex> реберно непересекающихся путей.

{{Теорема<tex>\Rightarrow</tex> |about=Теорема Менгера для k связности :Существует <tex> L</tex> реберно непересекающихся путей, а значит, удалив любые <tex>L-1</tex> ребер хотя бы один путь останется не тронутым (альтернативная формулировкапринцип Дирихле)|statement=Две несмежные вершины k-отделимы тогда . Это и только тогдаозначает, когда они k-соединимычто существует путь из <tex>u</tex> в <tex>v</tex>.

|about=Теорема Менгера для k-реберной связностио вершинной двойственности в ориентированном графе|statement=Пусть G - конечный, неориентированный граф, Между вершинами <mathtex>\lambda(G) = ku</mathtex> и <mathtex>\Leftrightarrowv</mathtex> для всех пар вершин существует <mathtex>xL</tex> вершинно непересекающихся путей тогда и только тогда, y \backepsilon Gкогда после удаления любых <tex>(L-1)</mathtex> вершин существует k реберно непересекающихся путей путь из x <tex>u</tex> в y<tex>v</tex>.

Аналогично вершинному случаю:Разобьем каждую вершину на две таким образом: :[[Файл:Menger-vertex.JPG]] :''(все входящие ребра заходят в левую вершину, исходящие выходят из правой. между двумя новыми вершинами добавляем ребро)'' :Теперь задача практически сведена к первой теореме.:Необходимо лишь отметить, что если в старом графе пути вершинно пересекаются, то в новом графе пути необходимо реберно пересекаются и наоборот.:Кроме того, предложение "удалить в исходном графе любые <tex>L</tex> вершин" можно заменять на "в новом графе можно удалить любые <tex>L</tex> ребер" (достаточно выбирать вершины на концах этих ребер). Можно заменять и обратно, если учесть, что можно удалять ребра между парой вершин, которые раньше были одним целым.