Изменения

{{Теорема|about=Теорема Менгера для вершинной представляет собой группу теорем, связывающих такие понятия на графах как ''<tex>k связности|statement=Наименьшее число </tex>-связность'' и ''количество непересекающихся путей'' относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ''ориентированном'' или ''неориентированном'' графе, разделяющих две несмежные вершины s и t, равно наибольшему числу непересекающихся простых (sподразумеваем ли ''реберную <tex>k</tex>-связность'' и ''реберно непересекающиеся пути'' или же ''вершинную <tex>k</tex>-t) цепей|proof=связность'' и ''вершинно непересекающиеся пути''.

Очевидно, что если k вершин разделяют s и t==Подготовка к доказательству==Для доказательства мы будем пользоваться развитой раннее [[Определение сети, то сущесвует не более k непересекающихся простых (s-t) цепейпотока|теорией потоков]].Теперь покажемКроме базовых определений нам потребуется понятие [[Дополняющая сеть, что если k вершин графа разделяют s и t, то существует k непересекающихся простых дополняющий путь| остаточной сети]] (sиначе {{-t) цепей. Для k=1 это очевидно. Пусть, для некоторого <math>k>1</math> это неверно. Возьмем h - наименьшее такое k и F - граф с наименьшим числом вершин, для которого при выбранном h теорема не верна. Будем удалять из F ребра, пока не получим G такой, что в G s и t разделяют h вершин}} дополнительной сети), а в <math>Gтакже [[Теорема_Форда-x</math> <math>h-1</math> вершина, где x Фалкерсона|теорема Форда- произвольное ребро графа GФалкерсона]].

Из определения 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) цепь должна содержать ребро :# Повторяем пункт <mathtex>x=uv2</mathtex>до тех пор, поскольку она не является цепью в <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 нет вершин:То, смежных одновременно с s и t|proof=Если что получится в G есть вершина wконце, смежная как с sбудет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, так и с tне трудно видеть, то что на каждой итерации (в графе <math>G-w</math> для разделения s том числе и t требуется <math>h - 1</math> непересекающихся (s-t) цепей. Добавляя w, получаем в графе G h непересекающихся (s-tпоследней) цепейэтот поток будет оставаться целочисленным, что противоречит предположению о графе Fи докажет требуемое.

И, наконец, сделаем немного более осознанным в общем-то и так интуитивно понятное утверждение:{{Лемма|about=IIУтверждение|statement=Любой набор WЕсли в сети, где все пропускные способности ребер равны <tex>1</tex>, содержащий h вершин и разделяющий s существует целочисленный поток величиной <tex>L</tex> то существует и t является смежным с s или t <tex>L</tex> реберно непересекающихся путей.

Пусть W - произвольный набор h вершин, разделяющих s и t в G. Цепь: Считаем, соединяющую s с некоторой вершиной что <mathtex>w_i \in Wu</mathtex> и не содержащую других вершин из W будем называть (s{{-W) цепью. Аналогично назовем (W-t) цепь. Обозначим наборы всех (s-W) и (W-t) цепей }} источник, <mathtex>P_sv</mathtex> и {{---}} сток.: В начале поймем, что если поток не нулевой, то существует маршрут из <mathtex>P_tu</mathtex> соответственно.Тогда каждая (s-t) цепь начинается с элемента из в <mathtex>P_sv</mathtex> и заканчивается элементом из лежащий только на ребрах с потоком равным <mathtex>P_t1</mathtex>. В самом деле, если бы такого маршрута не существовало, поскольку любая цепь содержит вершину то можно было бы выделить множество вершин до которых такие маршруты из W. Общие вершины цепей из <mathtex>P_su</mathtex> и существуют, не включающее <mathtex>P_tv</mathtex> принадлежат набору W, так как и по крайней мере одна цепь из каждого набора <math>P_sнему построить разрез. Поток через такой разрез, очевидно равен нулю, видим противоречие (т.к. </mathtex> и <math>P_t</math> содержит f(любуюU,V) вершину <math>w_i=|f|</mathtex>, и если бы существовала некоторая вершина, не принадлежащая набору Wсмотри [[Разрез, но содержащаяся сразу и в (s-Wлемма о потоке через разрез|первую лемму]]) и в (W-t) цепи. :Итак, то нашлась бы (sнайдем какой-t) цепь, не имеющая вершин нибудь маршрут из W. Наконец, выполняется либо равенство <mathtex>P_s-W={s}u</mathtex>, либо равенство в <mathtex>P_t - W={t}v</mathtex>, поскольку в противном случае либо лежащий только на ребрах где поток равен <mathtex>P_s1</mathtex> вместе с ребрами . Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к целочисленному потоку величиной <mathtex>\{w_1t,w_2t...\}L-1</mathtex>. Ясно, либо что можно повторить тоже самое еще <mathtex>P_tL-1</mathtex> вместе с ребрами раз, и, таким образом мы выделим <mathtex>\{sw_1,sw_2...\}L</mathtex> образуют связные графы с меньшим числом вершин, чем у 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 \in Gкогда после удаления любых <tex>(L-1)</mathtex> вершин существует k реберно непересекающихся путей путь из x <tex>u</tex> в y<tex>v</tex>.

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