Упражнения с решениями Упражнение с решением 1

Имеется направленный граф G = (V, E) с положительной целочисленной пропуск- ной способностью ce каждого ребра e, источником 5 V и стоком t ^ V. Также задан целочисленный максимальный поток s-t в G, определяемый величиной потока f по каждому ребру e.

Допустим, мы выбираем некоторое ребро e E и увеличиваем его пропускную способность на одну единицу. Покажите, как найти максимальный поток в получен- ном графе за время O(m + n), где m — количество ребер в G, а n — количество узлов.

Решение

Важно заметить, что времени O(m + n) недостаточно для вычисления нового мак- симального потока «с нуля», поэтому нужно как-то использовать заданный поток f Интуитивно понятно, что даже после увеличения пропускной способности ребра e на 1 поток f не может сильно отдалиться от максимума; в конце концов, сеть из- менилась не так уж значительно.

На самом деле нетрудно показать, что максимальная величина потока может увеличиться не более чем на 1.

(7.68) Рассмотрим потоковую сеть G', полученную увеличением пропускной способности e на 1. Величина максимального потока в G' равна либо v(f), либо v(f) + 1.

Доказательство. Величина максимального потока в G' равна минимум v( f), так как f остается действительным потоком в сети. Кроме того, он еще и является целочисленным, поэтому достаточно показать, что величина максимального потока в G' не превышает v( f) + 1.

Согласно теореме о максимальном потоке и минимальном разрезе, в исходной потоковой сети G существует разрез s-t (A, B) с пропускной способностью v(f). Зададимся вопросом: какова пропускная способность (A, B) в новой потоковой сети G'? Все ребра, пересекающие (A, B), имеют в G' ту же пропускную способность, что и G, с возможным исключением e (если e пересекает (A, B)). Но ce возрастает только на 1, поэтому пропускная способность (A, B) в новой потоковой сети G' не превышает v( f) + 1. ■

Утверждение (7.68) предполагает естественный алгоритм. Начиная с действи- тельного потокаf в G', мы пытаемся найти один увеличивающий путь от s к t в оста- точном графе Gf Поиск выполняется за время O(m + n). Теперь возможен один из двух вариантов: может быть, найти увеличивающий путь не удастся, и тогда мы знаем, что f является максимальным потоком. В противном случае увеличение проходит успешно с поучением потока f' с величиной не менее v(f ) + 1. В этом случае согласно (7.68) мы знаем, что f ' является максимальным потоком. Итак, в любом случае после вычисления одного увеличивающего пути будет получен максимальный поток.

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

Еще по теме Упражнения с решениями Упражнение с решением 1:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
  17. Получение информации и принятие решений
  18. Решение измениться
  19. Решение измениться