Вещественные числа как пропускные способности
Наконец, прежде чем двигаться дальше, зададимся вопросом, насколько критичным было предположение о целочисленности пропускных способностей (речь не идет о (7.4), (7.5) и (7.14), где оно было очевидно необходимо).
А если пропускные способности будут задаваться вещественными числами? Где в доказательстве мы использовали тот факт, что пропускные способности являются целыми числами?
Да, использовали, и он был весьма критичен: утверждение (7.2) использовалось для доказательства того, что в (7.4) величина потока увеличивается по крайней мере на 1 при каждом шаге.
С вещественными пропускными способностями следует учесть, что величина потока может возрастать со все более малыми приращениями; следовательно, пропадает гарантия конечности количества итераций цикла.
И эта проблема оказывается очень серьезной, потому что при аномальном выборе увеличивающего пути алгоритм Форда–Фалкерсона с вещественными пропускными способностями может выполняться бесконечно.
Однако можно доказать, что теорема о максимальном потоке и минимальном разрезе (7.12) остается истинной даже в том случае, если пропускные способности являются вещественными числами.
Утверждение (7.9) предполагало лишь то, что поток f не имеет пути s–t в остаточном графе Gf, чтобы сделать вывод о существовании разреза s–t с равной величиной. Очевидно, для любого потока f с максимальной величиной остаточный граф не содержит пути s–t; в противном случае величину потока можно было бы увеличить.
Следовательно, чтобы доказать (7.12) для случая вещественных пропускных способностей, достаточно показать, что в каждой потоковой сети существует максимальный поток.
Конечно, при любом практическом применении потоков пропускные способности будут целыми или вещественными числами.
Однако проблема аномального выбора увеличивающего пути может проявиться даже с целыми пропускными способностями: из-за нее алгоритм Форда–Фалкерсона может потребовать огромного количества итераций.
В следующем разделе показано, как выбрать увеличивающие пути так, чтобы избежать потенциально нежелательного поведения алгоритма.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу