Изменения

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

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

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

{{Лемма|about=I|statement=В графе <tex>G</tex> нет вершин:То, смежных одновременно с <tex>s</tex> и <tex>t</tex>|proof=Если что получится в <tex>G</tex> есть вершина <tex>w</tex>конце, смежная как с <tex>s</tex>будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, так и с <tex>t</tex>не трудно видеть, то что на каждой итерации (в графе <tex>G-w</tex> для разделения <tex>s</tex> том числе и <tex>t</tex> требуется <tex>h - 1</tex> непересекающихся <tex>(s-t)</tex> цепей. Добавляя <tex>w</tex>, получаем в графе <tex>G</tex> <tex>h</tex> непересекающихся <tex>(s-tпоследней)</tex> цепейэтот поток будет оставаться целочисленным, что противоречит предположению о графе <tex>F</tex>и докажет требуемое.

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

Пусть : Считаем, что <tex>Wu</tex> {{-- произвольный набор <tex>h</tex> вершин-}} источник, разделяющих <tex>s</tex> и <tex>t</tex> в <tex>Gv</tex>{{---}} сток. Цепь: В начале поймем, соединяющую <tex>s</tex> с некоторой вершиной <tex>w_i \in W</tex> и что если поток не содержащую других вершин нулевой, то существует маршрут из <tex>Wu</tex> будем называть <tex>(s-W)</tex> цепью. Аналогично назовем <tex>(W-t)</tex> цепь. Обозначим наборы всех <tex>(s-W)</tex> и <tex>(W-t)</tex> цепей в <tex>P_sv</tex> и <tex>P_t</tex> соответственно. Тогда каждая <tex>(s-t)</tex> цепь начинается лежащий только на ребрах с элемента из <tex>P_s</tex> и заканчивается элементом из <tex>P_t</tex>, поскольку любая цепь содержит вершину из потоком равным <tex>W1</tex>. Общие вершины цепей из <tex>P_s</tex> и <tex>P_t</tex> принадлежат набору <tex>W</tex>В самом деле, так как по крайней мере одна цепь из каждого набора <tex>P_s</tex> и <tex>P_t</tex> содержит (любую) вершину <tex>w_i</tex>, и если бы существовала некоторая вершина, такого маршрута не принадлежащая набору <tex>W</tex>, но содержащаяся сразу и в <tex>(s-W)</tex> и в <tex>(W-t)</tex> цеписуществовало, то нашлась можно было бы <tex>(s-t)</tex> цепь, не имеющая выделить множество вершин до которых такие маршруты из вершины <tex>Wu</tex>. Наконецсуществуют, выполняется либо равенство не включающее <tex>P_s-W={s}v</tex>, либо равенство <tex>P_t - W={t}</tex>и по нему построить разрез. Поток через такой разрез, поскольку в противном случае либо <tex>P_s</tex> вместе с ребрами <tex>\{w_1tочевидно равен нулю,w_2tвидим противоречие (т.к..\}</tex>f(U, либо <tex>P_tV)=|f|</tex> вместе с ребрами <tex>\{sw_1,sw_2смотри [[Разрез, лемма о потоке через разрез|первую лемму]])...\}</tex> образуют связные графы с меньшим числом вершин :Итак, чем у найдем какой-нибудь маршрут из <tex>Gu</tex>, в которых <tex>sv</tex> и лежащий только на ребрах где поток равен <tex>t1</tex> не смежны, . Удалив все ребра находящиеся в этом маршруте иоставив все остальное неизменным, следовательно, в каждом из них имеется придем к целочисленному потоку величиной <tex>h</tex> непересекающихся <tex>(sL-t)1</tex> цепей. Объединяя Ясно, что можно повторить тоже самое еще <tex>(sL-W)1</tex> раз, и <tex>(W-t)</tex> части этих цепей, образуем в графе таким образом мы выделим <tex>G</tex> <tex>hL</tex> реберно непересекающихся <tex>(s-t)</tex> цепей. Мы пришли к противоречию. Утверждение доказаномаршрутов.

Пусть {{Теорема|about=Менгера о реберной двойственности в ориентированном графе|statement=Между вершинами <tex>P=\{s, u_1, u_2 ... t\}u</tex> - кратчайшая и <tex>(s-t)v</tex> цепь в существует <tex>GL</tex>реберно непересекающихся путей тогда и только тогда, когда после удаления любых <tex>u_1u_2=x</tex>. Заметим, что из (IL-1) <tex>u_1 \neq t</tex> Образуем множество ребер существует путь из <tex>S(x)=\{v_1, ... , v_{h-1}\}u</tex>, разделяющее в <tex>G-xv</tex> вершины .|proof=<tex>s\Leftarrow</tex> :Как и прежде, пусть <tex>tu</tex>. Из (I) следует{{---}} источник, что а <tex>u_1t \notin Gv</tex>. Используя (II) и беря <tex>W=S(x)\cup {u_1{---}} сток. :Назначим каждому ребру пропускную способность </tex>, получаем <tex>\forall i \; sv_i \in G1</tex>. Таким образом в силу Тогда существует максимальный поток, целочисленный на каждом ребре (Iпо лемме) . :По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в этом разрезе <tex>\forall i \; v_it \notin GL-1</tex>. Однакоребер, и тогда, если выбрать раз <tex>W=S(x) \cup {u_2}u</tex>, то в силу (II) получим и <tex>su_2 \in Gv</tex>находятся в разных частях разреза и, что противоречит выбору существует путь из <tex>Pu</tex> как кратчайшей в <tex>(s-t)v</tex> цепи, то в разрезе останется хотя бы еще одно ребро. Из полученного противоречия следуетЭто значит, что графа пропускная способность разреза и вместе с ним величина потока не меньше <tex>GL</tex>. А так как поток целочисленный, удовлетворяющего указанным условиям не существуетто это и означает, а значит не существует и графа что найдется <tex>FL</tex>, для которого теорема не вернареберно непересекающихся путей.}}

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

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

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

==Литература==[[Категория:Алгоритмы и структуры данных]]* Харари, Ф. Теория графов. — М.[[Категория: Книжный дом «ЛИБРОКОМ», 2009Связность в графах]]