50
правок
Изменения
Нет описания правки
==Подготовка к доказательству==
Для доказательства мы будем пользоваться развитой раннее [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуется понятие [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе {{- --}} дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]].
Кроме того, потребуется лемма о целочисленности потока, которую сейчас и докажем:
|statement= Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.
|proof=
:Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]] для поиска максимального потока. Алгоритм делает примерно следующее (подробней {{- --}} читай в соответствующей статье):
:''1.'' В начале берем какой-нибудь поток за начальный (например, нулевой).
}}
И, наконец, сделаем немного более осознаным в общем-то и так интуитивно-понятное утверждение:
{{Утверждение
|statement=Если в сети, где все пропускные способности ребер равны 1, существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей.
|proof=
: Считаем, что <tex>u</tex> {{- --}} источник, <tex>v</tex> {{--- }} сток.
: В начале поймем, что если поток не нулевой, то существует маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах с потоком равным 1. В самом деле, если бы такого маршрута не существовало, то можно было бы выделить множество вершин до которых такие маршруты из вершины <tex>u</tex> существуют, не включающее <tex>v</tex>, и по нему построить разрез. Поток через такой разрез, очевидно равен нулю, видим противоречие (т.к. <tex>f(U,V)=|f|</tex>, смотри [[Разрез, лемма о потоке через разрез|первую лемму]]).
:<tex>\Leftarrow</tex>
:Как и прежде, пусть <tex>u</tex> {{- --}} источник, а <tex>v</tex> {{--- }} сток.
:Назначим каждому ребру пропускную способность 1. Тогда существует максимальный поток, целочисленный на каждом ребре (по лемме).
:По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в этом разрезе <tex>L-1</tex> ребер, и тогда, раз <tex>u</tex> и <tex>v</tex> находятся в разных частях разреза и, существует путь из <tex>u</tex> в <tex>v</tex>, то в разрезе останется хотя бы еще одно ребро. Это значит, что пропускная способность разреза и вместе с ним величина потока не меньше <tex>L</tex>. А так как поток целочисленный, то это и означает, что найдется <tex>\exists L</tex> реберно непересекающихся путей.
:<tex>\Rightarrow</tex>
:существует <tex>\exists L</tex> реберно непересекающихся путей, а значит, удалив любые <tex>L-1</tex> ребер хотя бы один путь останется не тронутым (принцип Дирихле). Это и означает, что существует путь из <tex>u</tex> в <tex>v</tex>.
}}
</includeonly>
==Смотри См. также==
*[[Теорема Менгера, альтернативное доказательство]]
* [[wikipedia:Menger's theorem | Wikipedia {{---}} Menger's theorem ]]
==Литература==
* Ловас Л., Пламмер М. {{---}} '''Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии''' (глава 2.4 стр. 117) {{---}} 1998. {{---}} 656 с. {{---}} ISBN 5-03-002517-0 * Харари Ф. '''Теория графов.''' глава 5 — М.: Мир, 1973. (глава 2Изд. 3, М.: КомКнига, 2006.4 стр— 296 с. 117)
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]
