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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Теорема)
(не показаны 24 промежуточные версии 7 участников)
Строка 1: Строка 1:
{{Теорема
+
Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как ''<tex>k</tex>-связность'' и ''количество непересекающихся путей'' относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ''ориентированном'' или ''неориентированном'' графе, и подразумеваем ли ''реберную <tex>k</tex>-связность'' и ''реберно непересекающиеся пути'' или же ''вершинную <tex>k</tex>-связность'' и  ''вершинно непересекающиеся пути''.
|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>.
 
  
 +
Кроме того, потребуется лемма о целочисленности потока, которую сейчас и докажем:
 +
{{Лемма
 +
|about=о целочисленности потока
 +
|statement=&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.
 +
|proof=
 +
:Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]] для поиска максимального потока. Алгоритм делает примерно следующее (подробней {{---}} читай в соответствующей статье):
  
Из определения <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>
+
:# В начале берем какой-нибудь поток за начальный (например, нулевой).
 +
:# В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.
 +
:# Повторяем пункт <tex>2</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>1</tex>, существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей.
|statement=
 
Любой набор <tex>W</tex>, содержащий <tex>h</tex> вершин и разделяющий <tex>s</tex> и <tex>t</tex> является смежным с <tex>s</tex> или <tex>t</tex>  
 
 
|proof=
 
|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>u</tex> {{---}} источник, <tex>v</tex> {{---}} сток.
 +
: В начале поймем, что если поток не нулевой, то существует маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах с потоком равным <tex>1</tex>. В самом деле, если бы такого маршрута не существовало, то можно было бы выделить множество вершин до которых такие маршруты из вершины <tex>u</tex> существуют, не включающее <tex>v</tex>, и по нему построить разрез. Поток через такой разрез, очевидно равен нулю, видим противоречие (т.к. <tex>f(U,V)=|f|</tex>, смотри [[Разрез, лемма о потоке через разрез|первую лемму]]).
 +
 
 +
:Итак, найдем какой-нибудь маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах где поток равен <tex>1</tex>. Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к целочисленному потоку величиной <tex>L-1</tex>. Ясно, что можно повторить тоже самое еще <tex>L-1</tex> раз, и, таким образом мы выделим <tex>L</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=Менгера о реберной двойственности в ориентированном графе
 +
|statement=Между вершинами <tex>u</tex> и <tex>v</tex> существует <tex>L</tex> реберно непересекающихся путей тогда и только тогда, когда после удаления любых <tex>(L-1)</tex> ребер существует путь из <tex>u</tex> в <tex>v</tex>.
 +
|proof=
 +
<tex>\Leftarrow</tex> 
 +
:Как и прежде, пусть <tex>u</tex> {{---}} источник, а <tex>v</tex> {{---}} сток.
 +
:Назначим каждому ребру пропускную способность <tex>1</tex>. Тогда существует максимальный поток, целочисленный на каждом ребре (по лемме).
 +
:По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в этом разрезе <tex>L-1</tex> ребер, и тогда, раз <tex>u</tex> и <tex>v</tex> находятся в разных частях разреза и, существует путь из <tex>u</tex> в <tex>v</tex>, то в разрезе останется хотя бы еще одно ребро. Это значит, что пропускная способность разреза и вместе с ним величина потока не меньше <tex>L</tex>. А так как поток целочисленный, то это и означает, что найдется <tex> L</tex> реберно непересекающихся путей.
  
{{Теорема
+
<tex>\Rightarrow</tex>
|about=
+
:Существует <tex> L</tex> реберно непересекающихся путей, а значит, удалив любые <tex>L-1</tex> ребер хотя бы один путь останется не тронутым (принцип Дирихле). Это и означает, что существует путь из <tex>u</tex> в <tex>v</tex>.
Теорема Менгера для <tex>k</tex>-связности (альтернативная формулировка)
 
|statement=
 
Две несмежные вершины k-отделимы тогда и только тогда, когда они <tex>k</tex>-соединимы
 
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
|about=
+
|about=Менгера о вершинной двойственности в ориентированном графе
Теорема Менгера для <tex>k</tex>-реберной связности
+
|statement=Между вершинами <tex>u</tex> и <tex>v</tex> существует <tex>L</tex> вершинно непересекающихся путей тогда и только тогда, когда после удаления любых <tex>(L-1)</tex> вершин существует путь из <tex>u</tex> в <tex>v</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=
 
|proof=
Аналогично теореме для вершинной связности.
+
 
 +
:Разобьем каждую вершину на две таким образом:
 +
 
 +
:[[Файл:Menger-vertex.JPG]]
 +
 
 +
:''(все входящие ребра заходят в левую вершину, исходящие выходят из правой. между двумя новыми вершинами добавляем ребро)''
 +
 
 +
:Теперь задача практически сведена к первой теореме.
 +
:Необходимо лишь отметить, что если в старом графе пути вершинно пересекаются, то в новом графе пути необходимо реберно пересекаются и наоборот.
 +
:Кроме того, предложение "удалить в исходном графе любые <tex>L</tex> вершин" можно заменять на "в новом графе можно удалить любые <tex>L</tex> ребер" (достаточно выбирать вершины на концах этих ребер). Можно заменять и обратно, если учесть, что можно удалять ребра между парой вершин, которые раньше были одним целым.
 
}}
 
}}
 +
<includeonly>
 +
Теоремы для неориентированного графа формулируются идентично, а их доказательства сводятся к своим ориентированным двойникам путем замены каждого ребра на две дуги:
 +
 +
[[Файл:Menger_undirected.JPG‎]]
 +
</includeonly>
 +
 +
==См. также==
 +
*[[Теорема Менгера, альтернативное доказательство]]
 +
* [[wikipedia:Menger's theorem | Wikipedia {{---}} Menger's theorem ]]
 +
 +
==Источники информации==
 +
* Ловас Л., Пламмер М. {{---}} '''Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии''' (глава 2.4 стр. 117) {{---}} 1998. {{---}} 656 с. {{---}} ISBN 5-03-002517-0
 +
* Харари Ф. '''Теория графов.''' глава 5 — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
  
==Литература==
+
[[Категория:Алгоритмы и структуры данных]]
*  Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
+
[[Категория:Связность в графах]]

Версия 17:02, 5 января 2017

Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как [math]k[/math]-связность и количество непересекающихся путей относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ориентированном или неориентированном графе, и подразумеваем ли реберную [math]k[/math]-связность и реберно непересекающиеся пути или же вершинную [math]k[/math]-связность и вершинно непересекающиеся пути.

Подготовка к доказательству

Для доказательства мы будем пользоваться развитой раннее теорией потоков. Кроме базовых определений нам потребуется понятие остаточной сети (иначе — дополнительной сети), а также теорема Форда-Фалкерсона.

Кроме того, потребуется лемма о целочисленности потока, которую сейчас и докажем:

Лемма (о целочисленности потока):
      Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.
Доказательство:
[math]\triangleright[/math]
Для доказательства достаточно рассмотреть алгоритм Форда-Фалкерсона для поиска максимального потока. Алгоритм делает примерно следующее (подробней — читай в соответствующей статье):
  1. В начале берем какой-нибудь поток за начальный (например, нулевой).
  2. В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.
  3. Повторяем пункт [math]2[/math] до тех пор, пока находится хоть какой-то путь в остаточной сети.
То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и не трудно видеть, что на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.
[math]\triangleleft[/math]

И, наконец, сделаем немного более осознанным в общем-то и так интуитивно понятное утверждение:

Утверждение:
Если в сети, где все пропускные способности ребер равны [math]1[/math], существует целочисленный поток величиной [math]L[/math] то существует и [math]L[/math] реберно непересекающихся путей.
[math]\triangleright[/math]
Считаем, что [math]u[/math] — источник, [math]v[/math] — сток.
В начале поймем, что если поток не нулевой, то существует маршрут из [math]u[/math] в [math]v[/math] лежащий только на ребрах с потоком равным [math]1[/math]. В самом деле, если бы такого маршрута не существовало, то можно было бы выделить множество вершин до которых такие маршруты из вершины [math]u[/math] существуют, не включающее [math]v[/math], и по нему построить разрез. Поток через такой разрез, очевидно равен нулю, видим противоречие (т.к. [math]f(U,V)=|f|[/math], смотри первую лемму).
Итак, найдем какой-нибудь маршрут из [math]u[/math] в [math]v[/math] лежащий только на ребрах где поток равен [math]1[/math]. Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к целочисленному потоку величиной [math]L-1[/math]. Ясно, что можно повторить тоже самое еще [math]L-1[/math] раз, и, таким образом мы выделим [math]L[/math] реберно непересекающихся маршрутов.
[math]\triangleleft[/math]

Теорема

Теперь сама теорема будет тривиальным следствием. В начале сформулируем и докажем реберную версию для случая ориентированного графа.

Теорема (Менгера о реберной двойственности в ориентированном графе):
Между вершинами [math]u[/math] и [math]v[/math] существует [math]L[/math] реберно непересекающихся путей тогда и только тогда, когда после удаления любых [math](L-1)[/math] ребер существует путь из [math]u[/math] в [math]v[/math].
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow[/math]

Как и прежде, пусть [math]u[/math] — источник, а [math]v[/math] — сток.
Назначим каждому ребру пропускную способность [math]1[/math]. Тогда существует максимальный поток, целочисленный на каждом ребре (по лемме).
По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в этом разрезе [math]L-1[/math] ребер, и тогда, раз [math]u[/math] и [math]v[/math] находятся в разных частях разреза и, существует путь из [math]u[/math] в [math]v[/math], то в разрезе останется хотя бы еще одно ребро. Это значит, что пропускная способность разреза и вместе с ним величина потока не меньше [math]L[/math]. А так как поток целочисленный, то это и означает, что найдется [math] L[/math] реберно непересекающихся путей.

[math]\Rightarrow[/math]

Существует [math] L[/math] реберно непересекающихся путей, а значит, удалив любые [math]L-1[/math] ребер хотя бы один путь останется не тронутым (принцип Дирихле). Это и означает, что существует путь из [math]u[/math] в [math]v[/math].
[math]\triangleleft[/math]
Теорема (Менгера о вершинной двойственности в ориентированном графе):
Между вершинами [math]u[/math] и [math]v[/math] существует [math]L[/math] вершинно непересекающихся путей тогда и только тогда, когда после удаления любых [math](L-1)[/math] вершин существует путь из [math]u[/math] в [math]v[/math].
Доказательство:
[math]\triangleright[/math]
Разобьем каждую вершину на две таким образом:
Menger-vertex.JPG
(все входящие ребра заходят в левую вершину, исходящие выходят из правой. между двумя новыми вершинами добавляем ребро)
Теперь задача практически сведена к первой теореме.
Необходимо лишь отметить, что если в старом графе пути вершинно пересекаются, то в новом графе пути необходимо реберно пересекаются и наоборот.
Кроме того, предложение "удалить в исходном графе любые [math]L[/math] вершин" можно заменять на "в новом графе можно удалить любые [math]L[/math] ребер" (достаточно выбирать вершины на концах этих ребер). Можно заменять и обратно, если учесть, что можно удалять ребра между парой вершин, которые раньше были одним целым.
[math]\triangleleft[/math]


См. также

Источники информации

  • Ловас Л., Пламмер М. — Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии (глава 2.4 стр. 117) — 1998. — 656 с. — ISBN 5-03-002517-0
  • Харари Ф. Теория графов. глава 5 — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)