Изменения
Нет описания правки
Очевидно, что если <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>W</tex>, содержащий <tex>h</tex> вершин и разделяющий <tex>s</tex> и <tex>t</tex> является смежным с <tex>s</tex> или <tex>t</tex>.
|proof=
Пусть <tex>W</tex> {{- --}} произвольный набор <tex>h</tex> вершин, разделяющих <tex>s</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_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>W</tex>. Наконец, выполняется либо равенство <tex>P_s-W={s}</tex>, либо равенство <tex>P_t - W={t}</tex>, поскольку в противном случае либо <tex>P_s</tex> вместе с ребрами <tex>\{w_1t,w_2t...\}</tex>, либо <tex>P_t</tex> вместе с ребрами <tex>\{sw_1,sw_2...\}</tex> образуют связные графы с меньшим числом вершин, чем у <tex>G</tex>, в которых <tex>s</tex> и <tex>t</tex> не смежны, и, следовательно, в каждом из них имеется <tex>h</tex> непересекающихся <tex>(s-t)</tex> цепей. Объединяя <tex>(s-W)</tex> и <tex>(W-t)</tex> части этих цепей, образуем в графе <tex>G</tex> <tex>h</tex> непересекающихся <tex>(s-t)</tex> цепей. Мы пришли к противоречию. Утверждение доказано.
}}
Пусть <tex>P=\{s, u_1, u_2 ... t\}</tex> {{- --}} кратчайшая <tex>(s-t)</tex> цепь в <tex>G</tex>, <tex>u_1u_2=x</tex>. Заметим, что из (I) <tex>u_1 \neq t</tex> Образуем множество <tex>S(x)=\{v_1, ... , v_{h-1}\}</tex>, разделяющее в <tex>G-x</tex> вершины <tex>s</tex> и <tex>t</tex>. Из (I) следует, что <tex>u_1t \notin G</tex>. Используя (II) и беря <tex>W=S(x)\cup {u_1}</tex>, получаем <tex>\forall i \; sv_i \in G</tex>. Таким образом в силу (I) <tex>\forall i \; v_it \notin G</tex>. Однако, если выбрать <tex>W=S(x) \cup {u_2}</tex>, то в силу (II) получим <tex>su_2 \in G</tex>, что противоречит выбору <tex>P</tex> как кратчайшей <tex>(s-t)</tex> цепи. Из полученного противоречия следует, что графа <tex>G</tex>, удовлетворяющего указанным условиям не существует, а значит не существует и графа <tex>F</tex>, для которого теорема не верна.
}}
Теорема Менгера для <tex>k</tex>-реберной связности
|statement=
Пусть <tex>G</tex> {{- --}} конечный, неориентированный граф, <tex>\lambda(G) = k</tex> <tex>\Leftrightarrow</tex> для всех пар вершин <tex>x, y \in G</tex> существует <tex>k</tex> реберно непересекающихся путей из <tex>x</tex> в <tex>y</tex>.
|proof=
Аналогично теореме для вершинной связности.
}}
==Смотри также==
*[[Теорема Менгера]]
==ЛитератураИсточники информации==
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]
