Изменения
Новая страница: «{{Теорема |about= Теорема Менгера для вершинной <tex>k</tex> связности |statement= Наименьшее число верш…»
{{Теорема
|about=
Теорема Менгера для вершинной <tex>k</tex> связности
|statement=
Наименьшее число вершин, [[k-связность|разделяющих]] две несмежные вершины <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> это очевидно.
Пусть, для некоторого <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=uv</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>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>, для которого теорема не верна.
}}
{{Теорема
|about=
Теорема Менгера для <tex>k</tex>-связности (альтернативная формулировка)
|statement=
Две несмежные вершины <tex>k</tex>-отделимы тогда и только тогда, когда они <tex>k</tex>-соединимы.
}}
{{Теорема
|about=
Теорема Менгера для <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
|about=
Теорема Менгера для вершинной <tex>k</tex> связности
|statement=
Наименьшее число вершин, [[k-связность|разделяющих]] две несмежные вершины <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> это очевидно.
Пусть, для некоторого <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=uv</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>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>, для которого теорема не верна.
}}
{{Теорема
|about=
Теорема Менгера для <tex>k</tex>-связности (альтернативная формулировка)
|statement=
Две несмежные вершины <tex>k</tex>-отделимы тогда и только тогда, когда они <tex>k</tex>-соединимы.
}}
{{Теорема
|about=
Теорема Менгера для <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
