143
правки
Изменения
format
{{Теорема
|about=
Теорема Менгера для вершинной <tex>k </tex> связности
|statement=
Наименьшее число вершин, разделяющих две несмежные вершины <tex>s </tex> и <tex>t</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> это очевидно. Пусть, для некоторого <mathtex>k>1</mathtex> это неверно. Возьмем <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> вершин, а в <mathtex>G-x</mathtex> <mathtex>h-1</mathtex> вершина, где <tex>x </tex> - произвольное ребро графа <tex>G</tex>.
Из определения <tex>G </tex> следует, что для всякого его ребра <tex>x </tex> существует множество <mathtex>S(x)</mathtex> из <mathtex>h-1</mathtex> вершин, которое в <mathtex>G-x</mathtex> разделяет <tex>s </tex> и <tex>t</tex>. Далее, граф <mathtex>G-S(x)</mathtex> содержит по крайней мере одну <tex>(s-t) </tex> цепь, так как граф <tex>G </tex> имеет <tex>h </tex> вершин, разделяющих <tex>s </tex> и <tex>t </tex> в <tex>G</tex>. Каждая такая <tex>(s-t) </tex> цепь должна содержать ребро <mathtex>x=uv</mathtex>, поскольку она не является цепью в <mathtex>G-x</mathtex>. Поэтому <mathtex>u,v \notin S(x)</mathtex>, и если <mathtex>u <> \neq s,t </mathtex> то <mathtex>S(x) \cup {u}</mathtex> разделяет <tex>s </tex> и <tex>t </tex> в <tex>G</tex>
{{Лемма
I
|statement=
В графе <tex>G </tex> нет вершин, смежных одновременно с <tex>s </tex> и <tex>t</tex>
|proof=
Если в <tex>G </tex> есть вершина <tex>w</tex>, смежная как с <tex>s</tex>, так и с <tex>t</tex>, то в графе <mathtex>G-w</mathtex> для разделения <tex>s </tex> и <tex>t </tex> требуется <mathtex>h - 1</mathtex> непересекающихся <tex>(s-t) </tex> цепей. Добавляя <tex>w</tex>, получаем в графе <tex>G </tex> <tex>h </tex> непересекающихся <tex>(s-t) </tex> цепей, что противоречит предположению о графе <tex>F</tex>
}}
II
|statement=
Любой набор <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>. Цепь, соединяющую s с некоторой вершиной <mathtex>w_i \in W</mathtex> и не содержащую других вершин из W будем называть <tex>(s-W) </tex> цепью. Аналогично назовем <tex>(W-t) </tex> цепь. Обозначим наборы всех <tex>(s-W) </tex> и <tex>(W-t) </tex> цепей <mathtex>P_s</mathtex> и <mathtex>P_t</mathtex> соответственно.Тогда каждая <tex>(s-t) </tex> цепь начинается с элемента из <mathtex>P_s</mathtex> и заканчивается элементом из <mathtex>P_t</mathtex>, поскольку любая цепь содержит вершину из <tex>W</tex>. Общие вершины цепей из <mathtex>P_s</mathtex> и <mathtex>P_t</mathtex> принадлежат набору <tex>W</tex>, так как по крайней мере одна цепь из каждого набора <mathtex>P_s</mathtex> и <mathtex>P_t</mathtex> содержит (любую) вершину <mathtex>w_i</mathtex>, и если бы существовала некоторая вершина, не принадлежащая набору <tex>W</tex>, но содержащаяся сразу и в <tex>(s-W) </tex> и в <tex>(W-t) </tex> цепи, то нашлась бы <tex>(s-t) </tex> цепь, не имеющая вершин из <tex>W</tex>. Наконец, выполняется либо равенство <mathtex>P_s-W={s}</mathtex>, либо равенство <mathtex>P_t - W={t}</mathtex>, поскольку в противном случае либо <mathtex>P_s</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) цепей. Мы пришли к противоречию. Утверждение доказано.
}}
Пусть <math>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, для которого теорема не верна
