223
правки
Изменения
Нет описания правки
{{В разработке}}
Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как ''k-связность'' и ''количество непересекающихся путей'' относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ''ориентированном'' или ''неориентированном'' графе, и подразумеваем ли ''реберную k-связность'' и ''реберно непересекающиеся пути'' или же ''вершинную k-связность'' и ''вершинно непересекающиеся пути''.
==Подготовка к доказательству==
<=
Тогда существует максимальный поток, целочисленный на каждом ребре(по лемме).
По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку (и этот разрез минимален среди всех возможных разрезов). По условию "после удаления <tex>\forall L-1</tex> (и в частности тех, что находятся в нашем разрезе) ребер все еще<tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>", значит пропускная способность разреза <tex>\geqslant L = |f|</tex>. А т.к. так как поток целочисленный , то это и означает, что <tex>\exists L</tex> реберно непересекающихся путей (чуть позже дадим аккуратное объяснение этому).
=>
<tex>\exists L</tex> реберно непересекающихся путей, а значит удалив любых <tex>L-1</tex> ребер хотя бы один путь останется останется не тронутым (принцип Дирихле). Это и означает <tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>.
}}
Небольшой комментарий к доказательству <= :
Если в сети, где все пропускные способности равны 1 существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей. Поясним это: найдем какой-нибудь маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах где поток равен 1. Такой маршут обязательно существуеют, пока величина потока больше 0 (нетрудно показать, что иначе придем к противоречию). Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к потоку величиной <tex>L-1</tex>. Ясно, что таким образом мы неизбежно выделим <tex>L</tex> реберно непересекающихся маршрутов, что и требуется.
//все остальные теоремы
==Смотри также==
*[[Теорема Менгера, альтернативное доказательство]]
==Литература==
* Ловас Л., Пламмер М. '''Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии''' 1998. 656 с. ISBN 5-03-002517-0 (глава 2.4 стр. 117)
[[Категория:Связность в графах]]
