Теорема Менгера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Фикс доказательств)
(Изящное доказательство из Харари)
Строка 1: Строка 1:
−
{{Лемма
+
{{Теорема
−
|statement=x, y вершины G, существует k вершинно непересекающихся пути из x в y. Тогда все остальные пути пересекают выбранные k следующим образом:
+
|about=
−
а) существуют вершины, принадлежащие первым k путям, такие, что любой новый путь проходит через одну из них.
+
Теорема Менгера для k связности
−
б) на каждом из путей не более одной такой вершины
+
|statement=
 +
Наименьшее число вершин, разделяющих две несмежные вершины s и t, равно наибольшему числу непересекающихся простых (s-t) цепей
 +
|proof=
 +
Очевидно, что если k вершин разделяют s и t, то сущесвует не более k непересекающихся простых (s-t) цепей.
 +
Теперь покажем, что k вершин графа разделяют s и t, существует k непересекающихся простых (s-t) цепей. Для k=1 это очевидно.
 +
Пусть, для некоторого <math>k>1</math> это неверно. Возьмем h - наименьшее такое k и F - граф с наименьшим числом вершин, для которого при выбранном h теорема не верна. Будем удалять из F ребра, пока не получим G такой, что в G s и t разделяют h вершин, а в <math>G-x</math> <math>h-1</math> вершина, где x - произвольное ребро графа G.
 +
 
 +
{{Утверждение
 +
|statement=
 +
Из определения 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 <> s,t </math> то <math>S(x) \cup {u}</math> разделяет s и t в G
 +
}}
 +
 
 +
{{Утверждение
 +
|about=
 +
I
 +
|statement=
 +
в графе G нет вершин, смежных одновременно с s и t
 
|proof=
 
|proof=
−
Пусть, существуют пути, не проходящие через одну из таких вершин <math>x, u_1 ...q...p... u_n, y</math>, <math>x, v_1 ...q... v_m, y</math> и <math>x, w_1 ...p... w_p, y</math> тогда последние 2 пути не пересекаются с первыми k, а по условию у нас всего k непересекающихся путей, а не <math>k + 1</math>
+
Если в G есть вершина w, смежная как с s, так и с t, то в графе <math>G-w</math> для разделения s и t  требуется <math>h - 1</math> непересекающихся (s-t) цепей. Добавляя w, получаем в графе G h непересекающихся (s-t) цепей, что противоречит предположению о графе F
 
}}
 
}}
  
−
{{Теорема
+
{{Утверждение
 +
|about=
 +
II
 
|statement=
 
|statement=
−
Пусть G - конечный, неориентированный граф, <math>\kappa(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon G</math> существует k вершинно непересекающихся путей из x в y
 
 
|proof=
 
|proof=
−
Пусть, существует лишь <math>m < k</math> вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти m, причем по лемме можно удалить <math>l \le m</math> вершин так, чтобы разорвать все добавленные пути и l из выбранных изначально.. Тогда удалив m вершин (l и по одной из оставшихся <math>m - l</math> путей) мы разорвем все пути из x в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано.
+
}}
−
Докажем обратное:
+
Пусть <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, для которого теорема не верна
−
Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить <math>m < k</math> вершин так, чтобы граф потерял связность. Покажем, что достаточно удалить k вершин, чтобы граф потерял связность. Возьмем все пути из x в y, они пересекут выбранные k, причем по лемме можно выбрать не более k точек пересечения. Удалив все вершины пересечения и произвольные вершины из оставшихся путей (всего не более k) мы порвем все пути. Теорема доказана.
+
 
  
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 +
|about=
 +
Теорема Менгера для k связности (альтернативная формулировка)
 +
|statement=
 +
Две несмежные вершины k-отделимы тогда и только тогда, когда они k-соединимы
 +
}}
 +
 +
{{Теорема
 +
|about=
 +
Теорема Менгера для k-реберной связности
 
|statement=
 
|statement=
 
Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math>  для всех пар вершин <math>x, y \backepsilon G</math> существует k реберно непересекающихся путей из x в y
 
Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math>  для всех пар вершин <math>x, y \backepsilon G</math> существует k реберно непересекающихся путей из x в y

Версия 17:19, 10 октября 2010

Теорема (Теорема Менгера для k связности):
Наименьшее число вершин, разделяющих две несмежные вершины s и t, равно наибольшему числу непересекающихся простых (s-t) цепей
Доказательство:
[math]\triangleright[/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):
Пусть [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 \backepsilon G[/math] существует k реберно непересекающихся путей из x в y
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Менгера&oldid=3483»