Выбор хороших увеличивающих путей

В предыдущем разделе было показано, что любой выбор увеличивающего пути приводит к возрастанию величины потока; так мы пришли к границе C для количества увеличений, где. При относительно небольших C такая граница выглядит разумно; однако при больших C она становится слишком слабой.

Чтобы понять, насколько плохо может сложиться ситуация, рассмотрим граф на рис. 7.2, но со следующими пропускными способностями: ребра (s, v), (s, u), (v, t) и (u, t) имеют пропускную способность 100, а у ребра (u, v) пропускная способность равна 1.

Допустим, мы начинаем с увеличивающего пути P1, содержащего узлы s, u, v, t в указанном порядке. Для этого пути bottleneck(P1, f ) = 1. После увеличения имеем f (e) = 1 для ребра e = (u, v), поэтому в остаточном графе появляется обратное ребро.

Для следующего увеличивающего пути выбирается путь P2 путь P2 из узлов s, v, u, t в таком порядке. При втором увеличении мы также получаем bottleneck(P2,f ) = 1. После второго увеличения имеем f (e) = 0 для ребра e = (u, v), поэтому ребро снова находится в остаточном графе.

Далее P1 и P2 поочередно выбираются для увеличения. В этом случае для того, чтобы добраться до желаемого потока с величиной 200, потребуется 200 увеличений. Именно эта граница была доказана в (7.4), так как в данном примере C = 200.