223
правки
Изменения
Нет описания правки
{{В разработке}}
Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как ''k-связность'' и ''количество непересекающихся путей'' относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ''ореинтированномориентированном'' или ''неореинтированномнеориентированном'' графе, и подразумеваем ли ''реберную связность'' и ''реберно непересекающиеся пути'' или же ''вершинную связность'' и ''вершинно непересекающиеся пути''.
==Подготовка к доказательству==
Для доказательства мы воспользуемся развитой [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуются понятия [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]]. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:
{{Лемма
}}
==Теорема==Теперь сама теорема будет тривиальным следствием. В начале сформулируем реберную версию для случая ореинтированного ориентированного графа.
{{Теорема
|about=Менгера о реберной двойственности в ореинтированном ориентированном графе
|statement=Между вершинами <tex>u</tex> и <tex>v\; \exists L</tex> реберно непересекающихся путей <tex>\Leftrightarrow</tex> после удаления <tex>\forall L-1</tex> ребер <tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>.
|proof=
