38
правок
Изменения
м
Нет описания правки
Рассмотрим множество <tex> S = \lbrace v \in V : \exists\, s \leadsto v \text{ in } G_f \rbrace </tex> и <tex> T = V \setminus S</tex>.
Разбиение <tex> \langle S, T \rangle</tex> является разрезом, так как по <tex> (2) </tex> в <tex> G_f </tex> не существует <tex> s \leadsto t</tex>.
По [[Разрез,_лемма_о_потоке_через_разрез|лемме о потоке через разрез]] <tex> f(S, T) = |f| </tex>. Также <tex> \forall u \in S, v \in T</tex> известно, что <tex>f(u, v) = c(u, v) </tex>, так как иначе вершина <tex> v </tex>
должна была бы принадлежать множеству <tex> S </tex>. Поэтому <tex> c(S, T) = f(S, T) = |f| </tex>.
