Изменения

{{Теорема|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>sv</tex> и <tex>t</tex> в <tex>G</tex>. Цепь, соединяющую <tex>s</tex> с некоторой вершиной <tex>w_i \in W</tex> и не содержащую других вершин из <tex>W</tex> будем называть <tex>(s{{-W)</tex> цепью. Аналогично назовем <tex>(W-t)</tex> цепь. Обозначим наборы всех <tex>(s-W)</tex> и <tex>(W-t)</tex> цепей <tex>P_s</tex> и <tex>P_t</tex> соответственно}} сток.Тогда каждая <tex>(s-t)</tex> цепь начинается с элемента из <tex>P_s</tex> и заканчивается элементом из <tex>P_t</tex>: В начале поймем, поскольку любая цепь содержит вершину из <tex>W</tex>. Общие вершины цепей из <tex>P_s</tex> и <tex>P_t</tex> принадлежат набору <tex>W</tex>что если поток не нулевой, так как по крайней мере одна цепь то существует маршрут из каждого набора <tex>P_su</tex> и в <tex>P_tv</tex> содержит (любую) вершину лежащий только на ребрах с потоком равным <tex>w_i1</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>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> реберно непересекающихся путей.

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