Вещественные числа как пропускные способности

Наконец, прежде чем двигаться дальше, зададимся вопросом, насколько критич- ным было предположение о целочисленности пропускных способностей (речь не идет о (7.4), (7.5) и (7.14), где оно было очевидно необходимо).
Для начала стоит заметить, что если разрешить использование рациональных чисел в качестве про- пускных способностей, ситуация не станет более общей, потому что мы можем определить наименьшее общее кратное всех пропускных способностей и умножить их все на это значение, чтобы получить эквивалентную задачу с целочисленными пропускными способностями.

А если пропускные способности будут задаваться вещественными числами? Где в доказательстве мы использовали тот факт, что пропускные способности являются целыми числами? Да, использовали, и он был весьма критичен: утверждение (7.2) использовалось для доказательства того, что в (7.4) величина потока увеличи- вается по крайней мере на 1 при каждом шаге. С вещественными пропускными способностями следует учесть, что величина потока может возрастать со все более малыми приращениями; следовательно, пропадает гарантия конечности количества итераций цикла. И эта проблема оказывается очень серьезной, потому что при ано- мальном выборе увеличивающего пути алгоритм Форда-Фалкерсона с вещественными пропускными способностями может выполняться бесконечно.

Однако можно доказать, что теорема о максимальном потоке и минимальном разрезе (7.12) остается истинной даже в том случае, если пропускные способности являются вещественными числами. Утверждение (7.9) предполагало лишь то, что поток f не имеет пути s-t в остаточном графе G, чтобы сделать вывод о существова- нии разреза s-t с равной величиной. Очевидно, для любого потока f с максимальной величиной остаточный граф не содержит пути s-t; в противном случае величину потока можно было бы увеличить. Следовательно, чтобы доказать (7.12) для слу- чая вещественных пропускных способностей, достаточно показать, что в каждой потоковой сети существует максимальный поток.

Конечно, при любом практическом применении потоков пропускные способ- ности будут целыми или вещественными числами. Однако проблема аномального выбора увеличивающего пути может проявиться даже с целыми пропускными спо- собностями: из-за нее алгоритм Форда-Фалкерсона может потребовать огромного количества итераций.

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

7.3.

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

Еще по теме Вещественные числа как пропускные способности:

  1. Предъявление вещественных доказательств
  2. Как усилить способности к восприятию
  3. ПРАВО ЗАЛОГА ИЛИ ВЕЩЕСТВЕННОГО ОБЕСПЕЧЕНИЯ
  4. Как развить свои способности к ясно-знанию
  5. Как развить свои способности к ясно-слышанию
  6. Глава 7. Совершенствуясь с годами Как с возрастом развиваются способности
  7. 16. Помните, что подражательная способность ребенка также естественна, как и творческая
  8. Развитие способностей и психических процессов Я развиваю свои способности
  9. 2. Гармоническое развитие – это когда хотя бы в одной способности не утрачивается связь с другими способностями
  10. Как восполнить дефицит навыков и способностей к восприятию и передаче информации (коммуникативности) у потерпевшего и свидетеля
  11. § 3. Содержание и форма произведения. Произведение и его вещественная оболочка (п. 1534-1536)
  12. Расчет числа сущности
  13. Расчет числа личности