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

Теорема (Теорема Менгера для k связности):

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]