Изменения

Перейти к: навигация, поиск

Теорема Форда-Фалкерсона

3 байта добавлено, 23:15, 21 декабря 2010
м
Нет описания правки
|proof=
<tex> (1)\Rightarrow (2)</tex>
 
Докажем от противного. Предположим, что в <tex> G_f </tex> существует какой-нибудь путь <tex>p = s \leadsto t</tex>.
Тогда рассмотрим <tex> f + f_p </tex>. По [[Лемма_о_сложении_потоков|лемме о сумме потоков]] <tex> f + f_p </tex> тоже является потоком в сети <tex> G </tex>,
<tex> (2) \Rightarrow (3) </tex>
 
Рассмотрим множество <tex> S = \lbrace v \in V : \exists\, s \leadsto v \text{ in } G_f \rbrace </tex> и <tex> T = V \setminus S</tex>.
Разбиение <tex> S </tex> и <tex> T </tex> является разрезом, так как не существует <tex> s \leadsto t</tex>.
<tex> (3) \Rightarrow (1) </tex>
 
Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \le c(S, T)</tex>, поэтому <tex> f </tex> максимален
}}
38
правок

Навигация