Теорема Менгера

Теорема (Теорема Менгера для вершинной [math]k[/math] связности):

Наименьшее число вершин, разделяющих две несмежные вершины [math]s[/math] и [math]t[/math], равно наибольшему числу непересекающихся простых [math](s-t)[/math] цепей

Доказательство:

[math]\triangleright[/math]

Очевидно, что если [math]k[/math] вершин разделяют [math]s[/math] и [math]t[/math], то сущесвует не более [math]k[/math] непересекающихся простых [math](s-t)[/math] цепей. Теперь покажем, что если [math]k[/math] вершин графа разделяют [math]s[/math] и [math]t[/math], то существует [math]k[/math] непересекающихся простых [math](s-t)[/math] цепей. Для [math]k=1[/math] это очевидно. Пусть, для некоторого [math]k\gt 1[/math] это неверно. Возьмем [math]h[/math] - наименьшее такое [math]k[/math] и [math]F[/math] - граф с наименьшим числом вершин, для которого при выбранном [math]h[/math] теорема не верна. Будем удалять из [math]F[/math] ребра, пока не получим [math]G[/math] такой, что в [math]G[/math] [math]s[/math] и [math]t[/math] разделяют [math]h[/math] вершин, а в [math]G-x[/math] [math]h-1[/math] вершина, где [math]x[/math] - произвольное ребро графа [math]G[/math]. Из определения [math]G[/math] следует, что для всякого его ребра [math]x[/math] существует множество [math]S(x)[/math] из [math]h-1[/math] вершин, которое в [math]G-x[/math] разделяет [math]s[/math] и [math]t[/math]. Далее, граф [math]G-S(x)[/math] содержит по крайней мере одну [math](s-t)[/math] цепь, так как граф [math]G[/math] имеет [math]h[/math] вершин, разделяющих [math]s[/math] и [math]t[/math] в [math]G[/math]. Каждая такая [math](s-t)[/math] цепь должна содержать ребро [math]x=uv[/math], поскольку она не является цепью в [math]G-x[/math]. Поэтому [math]u,v \notin S(x)[/math], и если [math]u \neq s,t [/math] то [math]S(x) \cup {u}[/math] разделяет [math]s[/math] и [math]t[/math] в [math]G[/math] Лемма (I): В графе [math]G[/math] нет вершин, смежных одновременно с [math]s[/math] и [math]t[/math] Доказательство: [math]\triangleright[/math] Если в [math]G[/math] есть вершина [math]w[/math], смежная как с [math]s[/math], так и с [math]t[/math], то в графе [math]G-w[/math] для разделения [math]s[/math] и [math]t[/math] требуется [math]h - 1[/math] непересекающихся [math](s-t)[/math] цепей. Добавляя [math]w[/math], получаем в графе [math]G[/math] [math]h[/math] непересекающихся [math](s-t)[/math] цепей, что противоречит предположению о графе [math]F[/math] [math]\triangleleft[/math] Лемма (II): Любой набор [math]W[/math], содержащий [math]h[/math] вершин и разделяющий [math]s[/math] и [math]t[/math] является смежным с [math]s[/math] или [math]t[/math] Доказательство: [math]\triangleright[/math] Пусть [math]W[/math] - произвольный набор [math]h[/math] вершин, разделяющих [math]s[/math] и [math]t[/math] в [math]G[/math]. Цепь, соединяющую s с некоторой вершиной [math]w_i \in W[/math] и не содержащую других вершин из W будем называть [math](s-W)[/math] цепью. Аналогично назовем [math](W-t)[/math] цепь. Обозначим наборы всех [math](s-W)[/math] и [math](W-t)[/math] цепей [math]P_s[/math] и [math]P_t[/math] соответственно.Тогда каждая [math](s-t)[/math] цепь начинается с элемента из [math]P_s[/math] и заканчивается элементом из [math]P_t[/math], поскольку любая цепь содержит вершину из [math]W[/math]. Общие вершины цепей из [math]P_s[/math] и [math]P_t[/math] принадлежат набору [math]W[/math], так как по крайней мере одна цепь из каждого набора [math]P_s[/math] и [math]P_t[/math] содержит (любую) вершину [math]w_i[/math], и если бы существовала некоторая вершина, не принадлежащая набору [math]W[/math], но содержащаяся сразу и в [math](s-W)[/math] и в [math](W-t)[/math] цепи, то нашлась бы [math](s-t)[/math] цепь, не имеющая вершин из [math]W[/math]. Наконец, выполняется либо равенство [math]P_s-W={s}[/math], либо равенство [math]P_t - W={t}[/math], поскольку в противном случае либо [math]P_s[/math] вместе с ребрами [math]\{w_1t,w_2t...\}[/math], либо [math]P_t[/math] вместе с ребрами [math]\{sw_1,sw_2...\}[/math] образуют связные графы с меньшим числом вершин, чем у [math]G[/math], в которых [math]s[/math] и [math]t[/math] не смежны, и, следовательно, в каждом из них имеется [math]h[/math] непересекающихся [math](s-t)[/math] цепей. Объединяя [math](s-W)[/math] и [math](W-t)[/math] части этих цепей, образуем в графе [math]G[/math] [math]h[/math] непересекающихся [math](s-t)[/math] цепей. Мы пришли к противоречию. Утверждение доказано. [math]\triangleleft[/math] Пусть [math]P=\{s, u_1, u_2 ... t\}[/math] - кратчайшая [math](s-t)[/math] цепь в [math]G[/math], [math]u_1u_2=x[/math] Заметим, что из(I) [math]u_1 \neq t[/math] Образуем множество [math]S(x)=\{v_1, ... , v_{h-1}\}[/math], разделяющее в [math]G-x[/math] вершины [math]s[/math] и [math]t[/math]. Из (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], что противоречит выбору [math]P[/math] как кратчайшей [math](s-t)[/math] цепи. Из полученного противоречия следует, что графа [math]G[/math], удовлетворяющего указанным условиям не существует, а значит не существует и графа [math]F[/math], для которого теорема не верна

[math]\triangleleft[/math]

Теорема (Теорема Менгера для [math]k[/math] связности (альтернативная формулировка)):

Две несмежные вершины k-отделимы тогда и только тогда, когда они [math]k[/math]-соединимы

Теорема (Теорема Менгера для [math]k[/math]-реберной связности):

Пусть [math]G[/math] - конечный, неориентированный граф, [math]\lambda(G) = k[/math] [math]\Leftrightarrow[/math] для всех пар вершин [math]x, y \in G[/math] существует [math]k[/math] реберно непересекающихся путей из [math]x[/math] в [math]y[/math]

Доказательство:

[math]\triangleright[/math]

Аналогично теореме для вершинной связности.

[math]\triangleleft[/math]

Литература

Харари