Изменения

|about=о целочисленности потока|statement=x&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, y вершины Gцелочисленный на каждом ребре.|proof=:Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, существует k вершинно непересекающихся пути из x реализация с помощью поиска в yглубину|алгоритм Форда-Фалкерсона]] для поиска максимального потока. Тогда все остальные Алгоритм делает примерно следующее (подробней {{---}} читай в соответствующей статье): :# В начале берем какой-нибудь поток за начальный (например, нулевой).:# В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути пересекают выбранные k следующим образом.:# Повторяем пункт <tex>2</tex> до тех пор, пока находится хоть какой-то путь в остаточной сети. а) существуют вершины:То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, принадлежащие первым k путями не трудно видеть, такиечто на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что любой новый путь проходит через одну из нихи докажет требуемое.б) на каждом из }} И, наконец, сделаем немного более осознанным в общем-то и так интуитивно понятное утверждение:{{Утверждение|statement=Если в сети, где все пропускные способности ребер равны <tex>1</tex>, существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей не более одной такой вершины .

Пусть: Считаем, существуют путичто <tex>u</tex> {{---}} источник, <tex>v</tex> {{---}} сток.: В начале поймем, что если поток не проходящие через одну нулевой, то существует маршрут из таких вершин <mathtex>u</tex> в <tex>v</tex> лежащий только на ребрах с потоком равным <tex>1</tex>x. В самом деле, u_1 ...q...p... u_nесли бы такого маршрута не существовало, yто можно было бы выделить множество вершин до которых такие маршруты из вершины <tex>u</mathtex>существуют, не включающее <tex>v<math/tex>x, v_1 и по нему построить разрез.Поток через такой разрез, очевидно равен нулю, видим противоречие (т.к.q..<tex>f(U,V)=|f|</tex>, смотри [[Разрез, лемма о потоке через разрез|первую лемму]]). v_m :Итак, yнайдем какой-нибудь маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах где поток равен <tex>1</mathtex> . Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к целочисленному потоку величиной <mathtex>L-1</tex>x, w_1 ...p... w_pЯсно, yчто можно повторить тоже самое еще <tex>L-1</mathtex> тогда последние 2 пути не пересекаются с первыми kраз, а по условию у нас всего k непересекающихся путейи, а не таким образом мы выделим <mathtex>k + 1L</mathtex>реберно непересекающихся маршрутов.

|about=Менгера о реберной двойственности в ориентированном графе|statement=Пусть G - конечный, неориентированный граф, Между вершинами <mathtex>\kappa(G) = ku</mathtex> и <mathtex>\Leftrightarrowv</mathtex> существует <tex> для всех пар вершин L<math/tex>xреберно непересекающихся путей тогда и только тогда, y \backepsilon Gкогда после удаления любых <tex>(L-1)</mathtex> ребер существует k вершинно непересекающихся путей путь из x <tex>u</tex> в y<tex>v</tex>.

Пусть<tex>\Leftarrow</tex> :Как и прежде, существует лишь пусть <tex>u</tex> {{---}} источник, а <tex>v<math/tex>m {{---}} сток. :Назначим каждому ребру пропускную способность < ktex>1</mathtex> вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти mсуществует максимальный поток, причем целочисленный на каждом ребре (по лемме можно удалить ). :По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в этом разрезе <mathtex>l \le mL-1</mathtex> вершин такребер, чтобы разорвать все добавленные пути и l из выбранных изначально.. Тогда удалив m вершин (l тогда, раз <tex>u</tex> и по одной из оставшихся <mathtex>m - lv</mathtex> путей) мы разорвем все пути из x находятся в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значитразных частях разреза и, предположение неверно. Прямое следствие доказано.Докажем обратное:Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить путь из <tex>u<math/tex>m в < ktex>v</mathtex> вершин так, чтобы граф потерял связностьто в разрезе останется хотя бы еще одно ребро. ПокажемЭто значит, что достаточно удалить k вершин, чтобы граф потерял связностьпропускная способность разреза и вместе с ним величина потока не меньше <tex>L</tex>. Возьмем все пути из x в yА так как поток целочисленный, они пересекут выбранные kто это и означает, причем по лемме можно выбрать не более k точек пересечения. Удалив все вершины пересечения и произвольные вершины из оставшихся что найдется <tex> L</tex> реберно непересекающихся путей (всего не более k) мы порвем все пути. Теорема доказана.

|about=Менгера о вершинной двойственности в ориентированном графе|statement=Пусть G - конечный, неориентированный граф, Между вершинами <mathtex>\lambda(G) = ku</mathtex> и <mathtex>\Leftrightarrowv</mathtex> для всех пар вершин существует <mathtex>xL</tex> вершинно непересекающихся путей тогда и только тогда, y \backepsilon Gкогда после удаления любых <tex>(L-1)</mathtex> вершин существует k реберно непересекающихся путей путь из x <tex>u</tex> в y<tex>v</tex>.