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

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

Версия 23:06, 13 октября 2010

Теорема (Теорема Менгера для вершинной [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] образуют связные графы с меньшим числом вершин, чем у 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]

Литература

Харари