Упражнения с решениями Упражнение с решением 1
Допустим, мы выбираем некоторое ребро 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 ' является максимальным потоком. Итак, в любом случае после вычисления одного увеличивающего пути будет получен максимальный поток.
Еще по теме Упражнения с решениями Упражнение с решением 1:
- § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
- РЕШЕНИЕ
- РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
- ПРИНЯТИЕ РЕШЕНИЙ
- РЕШЕНИЯ КСУ
- Не избегайте принятия решений
- ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
- ЗАДАЧА: РЕШЕНИЕ
- Принять решение
- Управленческие решения
- Решение проблем
- КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
- Убеждения и решения
- Убеждения и решения
- НАЙДИТЕ РЕШЕНИЕ
- НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
- Получение информации и принятие решений
- Решение измениться
- Решение измениться