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

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

граница выглядит разумно; однако при больших C она становится слишком слабой.

Чтобы понять, насколько плохо может сложиться ситуация, рассмотрим граф на рис. 7.2, но со следующими пропускными способностями: ребра (5, v), (5, u), (v, t) и (u, t) имеют пропускную способность 100, а у ребра (u, v) пропускная способность равна 1 (рис. 7.6). Легко увидеть, что максимальный поток равен 200: f (e) = 100 для ребер (5, v), (5, u), (v, t) и (u, t), а для ребра (u, v) он равен 0. Этот поток может быть получен в результате серии из двух увеличений, использующих пути с узлами 5, u, t и 5, v, t. Но подумайте, насколько плохо поведет себя алгоритм Форда-Фалкерсона при аномальном выборе увеличивающих путей. Допустим, мы начинаем с уве- личивающего пути P1, содержащего узлы 5, u, v, t в указанном порядке (рис. 7.6). Для этого пути bottleneck(P1, f) = 1. После увеличения имеем f (e) = 1 для ребра e = (u, v), поэтому в остаточном графе появляется обратное ребро. Для следующего увеличивающего пути выбирается путь P2 путь P2 из узлов 5, v, u, t в таком порядке. При втором увеличении мы также получаем bottleneck(P2f) = 1. После второго увеличения имеем f (e) = 0 для ребра e = (u, v), поэтому ребро снова находится в остаточном графе. Далее P1 и P2 поочередно выбираются для увеличения. В этом случае для того, чтобы добраться до желаемого потока с величиной 200, потребу- ется 200 увеличений. Именно эта граница была доказана в (7.4), так как в данном примере C = 200.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Чтобы хорошо говорить, учитесь хорошо писать
  2. Выбор линейного мышления - это выбор прожить жизнь в танце частиц.
  3. Выбор есть. Он существует всегда. Сознание - это выбор.
  4. То, что хорошо для одного, не всегда хорошо для другого.
  5. Статья 277. Повреждение путей сообщения и транспортных средств
  6. поиск путей утверждения в обществе правозаконности.
  7. 2. Договоры об эксплуатации подъездных путей и о подаче и уборке вагонов
  8. МОЧЕВЫВОДЯЩИХ ПУТЕЙ ИНФЕКЦИЯ См. статью УРЕТРИТ. МУРАШКИ ПО ТЕЛУ См. статью ОНЕМЕНИЕ.
  9. Пришло время преодолеть свою зависимость от одного пути и осознать, что есть много путей, ведущих к истине.
  10. Хорошо
  11. Оранжевый: "Хорошо!"
  12. Оранжевый: "Хорошо!"
  13. ХОРОШИЕ ИГРЫ