223
правки
Изменения
Нет описания правки
Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как ''k-связность'' и ''количество непересекающихся путей'' относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ''ориентированном'' или ''неориентированном'' графе, и подразумеваем ли ''реберную k-связность'' и ''реберно непересекающиеся пути'' или же ''вершинную k-связность'' и ''вершинно непересекающиеся пути''.
|statement=Если в сети, где все пропускные способности ребер равны 1, существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей.
|proof=
:В начале поймем, что если поток не нулевой, то существует маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах с потоком равным 1. .В самом деле, если бы такого маршрута не существовало, то можно было бы выделить множество вершин до которых такие маршруты существуют, не включающее <tex>u</tex>, и по нему построить разрез.Поток через такой разрез, очевидно равен нулю, противоречие (<tex>f(S,T)=|f|</tex>, смотри [[Разрез, лемма о потоке через разрез|первую лемму]]).
:Итак, найдем какой-нибудь маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах где поток равен 1. Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к целочисленному потоку величиной <tex>L-1</tex>. Ясно, что можно повторить тоже самое еще <tex>L-1</tex> раз, и, таким образом мы выделим <tex>L</tex> реберно непересекающихся маршрутов.
|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=
}}
<includeonly>
Теоремы для неореинтированного графа формулируются идентично, а их докозательства сводятся к своим ориентированным двойникам путем замены каждого ребра на две дуги:
==Смотри также==
*[[Теорема Менгера, альтернативное доказательство]]
