Изменения

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

{{Определение:# В начале берем какой-нибудь поток за начальный (например, нулевой).:# В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.:# Повторяем пункт <tex>2</tex> до тех пор, пока находится хоть какой-то путь в остаточной сети.|definition=Множество S вершин:То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, ребер или вершин и ребер разделяет u не трудно видеть, что на каждой итерации (в том числе и vпоследней) этот поток будет оставаться целочисленным, если u что и v принадлежат различным компонентам графа <math>G-S</math>докажет требуемое.

ОчевидноИ, что если k вершин разделяют s и tнаконец, то сущесвует не сделаем немного более k непересекающихся простых (sосознанным в общем-t) цепей.то и так интуитивно понятное утверждение:{{УтверждениеТеперь покажем|statement=Если в сети, что если k вершин графа разделяют s и tгде все пропускные способности ребер равны <tex>1</tex>, существует целочисленный поток величиной <tex>L</tex> то существует k и <tex>L</tex> реберно непересекающихся простых (s-t) цепейпутей. Для k|proof=1 это очевидно. Пусть: Считаем, для некоторого что <mathtex>ku</tex> {{---}} источник, <tex>1v</mathtex> это неверно. Возьмем h {{-- наименьшее такое k и F - граф с наименьшим числом вершин}} сток.: В начале поймем, для которого при выбранном h теорема что если поток не вернанулевой, то существует маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах с потоком равным <tex>1</tex>. Будем удалять из F ребраВ самом деле, пока если бы такого маршрута не получим G такойсуществовало, что в G s и t разделяют h то можно было бы выделить множество вершиндо которых такие маршруты из вершины <tex>u</tex> существуют, а в не включающее <mathtex>G-xv</mathtex> , и по нему построить разрез. Поток через такой разрез, очевидно равен нулю, видим противоречие (т.к. <mathtex>h-1f(U,V)=|f|</mathtex> вершина, где 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) цепь должна содержать ребро <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=Между вершинами <tex>u</tex> и <tex>v</tex> существует <tex>L</tex> реберно непересекающихся путей тогда и только тогда, когда после удаления любых <tex>(L-1)</tex> ребер существует путь из <tex>u</tex> в графе G нет вершин, смежных одновременно с s и t<tex>v</tex>.

Если <tex>\Leftarrow</tex> :Как и прежде, пусть <tex>u</tex> {{---}} источник, а <tex>v</tex> {{---}} сток. :Назначим каждому ребру пропускную способность <tex>1</tex>. Тогда существует максимальный поток, целочисленный на каждом ребре (по лемме). :По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в G есть вершина wэтом разрезе <tex>L-1</tex> ребер, смежная как с sи тогда, так раз <tex>u</tex> и <tex>v</tex> находятся в разных частях разреза и с t, существует путь из <tex>u</tex> в <tex>v</tex>, то в графе разрезе останется хотя бы еще одно ребро. Это значит, что пропускная способность разреза и вместе с ним величина потока не меньше <mathtex>G-wL</mathtex> для разделения s . А так как поток целочисленный, то это и t требуется означает, что найдется <tex> L</tex> реберно непересекающихся путей. <tex>\Rightarrow</tex> :Существует <tex> L</tex> реберно непересекающихся путей, а значит, удалив любые <mathtex>h L- 1</mathtex> непересекающихся ребер хотя бы один путь останется не тронутым (s-tпринцип Дирихле) цепей. Добавляя wЭто и означает, получаем что существует путь из <tex>u</tex> в графе G h непересекающихся (s-t) цепей, что противоречит предположению о графе F<tex>v</tex>.

{{ЛеммаТеорема|about=IIМенгера о вершинной двойственности в ориентированном графе|statement=любой набор WМежду вершинами <tex>u</tex> и <tex>v</tex> существует <tex>L</tex> вершинно непересекающихся путей тогда и только тогда, содержащий h когда после удаления любых <tex>(L-1)</tex> вершин и разделяющий s и t является смежным с s или t существует путь из <tex>u</tex> в <tex>v</tex>.

Пусть W :Разобьем каждую вершину на две таким образом: :[[Файл:Menger- произвольный набор h вершин, разделяющих s и t vertex.JPG]] :''(все входящие ребра заходят в G. Цепьлевую вершину, соединяющую s с некоторой вершиной <math>w_i \in W</math> и не содержащую других вершин исходящие выходят из W будем называть (s-W) цепьюправой. Аналогично назовем (W-tмежду двумя новыми вершинами добавляем ребро) цепь'' :Теперь задача практически сведена к первой теореме. Обозначим наборы всех (s-W) и (W-t) цепей <math>P_s</math> и <math>P_t</math> соответственно.Тогда каждая (s-t) цепь начинается с элемента из <math>P_s</math> и заканчивается элементом из <math>P_t</math>, поскольку любая цепь содержит вершину из 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_s-W={s}L</mathtex>, либо равенство <math>P_t - W={t}</math>, поскольку вершин" можно заменять на "в противном случае либо новом графе можно удалить любые <mathtex>P_sL</mathtex> вместе с ребрами <math>\{w_1t,w_2tребер" (достаточно выбирать вершины на концах этих ребер)...\}</math>Можно заменять и обратно, либо <math>P_t</math> вместе с ребрами <math>\{sw_1если учесть,sw_2...\}</math> образуют связные графы с меньшим числом что можно удалять ребра между парой вершин, чем у G, в которых s и t не смежны, и, следовательно, в каждом из них имеется h непересекающихся (s-t) цепей. Объединяя (s-W) и (W-t) части этих цепей, образуем в графе G h непересекающихся (s-t) цепей. Мы пришли к противоречию. Утверждение доказанокоторые раньше были одним целым.

Пусть <mathincludeonly>P=\{s, u_1, u_2 ... t\}</math> - кратчайшая (s-t) цепь в G, <math>u_1u_2=x</math> Заметим, что из(I) <math>u_1 <> t</math> Образуем множество <math>S(x)=\{v_1, ... , v_{h-1}\}</math>, разделяющее в <math>G-x</math> вершины s и t. Из (I) следует, что <math>u_1t \notin G</math> Используя (II) и беря <math>W=S(x)\cup {u_1}</math>, получаем <math>\forall i sv_i \in G</math> Таким образом в силу (I) <math>\forall v_it \notin G</math>. Однако, если выбрать <math>W=S(x) \cup {u_2}</math>, то в силу (II) получим <math>su_2 \in G</math>, что противоречит выбору P как кратчайшей (s-t) цепи. Из полученного противоречия следует, что Теоремы для неориентированного графа G, удовлетворяющего указанным условиям не существуетформулируются идентично, а значит не существует и графа F, для которого теорема не вернаих доказательства сводятся к своим ориентированным двойникам путем замены каждого ребра на две дуги:

==См. также==*[[Теорема Менгера, альтернативное доказательство]]* [[wikipedia:Menger's theorem | Wikipedia {{---}}Menger's theorem ]]

==Источники информации==* Ловас Л., Пламмер М. {{Теорема|about=Теорема Менгера для k связности ---}} '''Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии''' (альтернативная формулировкаглава 2.4 стр. 117)|statement=Две несмежные вершины k{{---}} 1998. {{---}} 656 с. {{--отделимы тогда и только тогда, когда они k-соединимы}}ISBN 5-03-002517-0 * Харари Ф. '''Теория графов.''' глава 5 — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)

{{Теорема[[Категория:Алгоритмы и структуры данных]]|about=Теорема Менгера для k-реберной связности|statement=Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \in G</math> существует k реберно непересекающихся путей из x [[Категория:Связность в y|proof=Аналогично теореме для вершинной связности.}}графах]]