Часть 5. Алгоритмы на графах. Для разреженных сетей и сетей с малыми целочисленными значениями пропускных способностей ребер, свойство 22.6 на самом деле дает верхнюю границу выполнения

Для разреженных сетей и сетей с малыми целочисленными значениями пропускных способностей ребер, свойство 22.6 на самом деле дает верхнюю границу выполнения любой реализации алгоритма Форда-Фалкерсона, пригодную для практического применения.

Следствие. Время, необходимое для нахождения максимального потока, равно O(VEM), оно же для разреженных сетей равно O(V²M).

Доказательство: Это утверждение непосредственно следует из фундаментального ре­зультата, утверждающего, что обобщенный поиск на графе линейно зависит от размера представления графа (свойство 18.12). Как уже говорилось выше, если мы использу­ем реализацию бахромы в виде очереди с приоритетами, мы учитываем это обстоя­тельство, вводя дополнительный коэффициент lgV ■

Это доказательство фактически устанавливает тот факт, что сомножитель М можно заменить отношением наибольшей и наименьшей пропускной способности в сети (см. упражнение 22.35). Когда это отношение мало, граница подсказывает нам, что любая ре­ализация алгоритма Форда-Фалкерсона обнаруживает максимальный поток за время, пропорциональное времени, затрачиваемому (например) в худшем случае на решение задачи нахождения всех кратчайших путей. Существует множество ситуаций, когда про­пускные способности и в самом деле низкие, так что сомножитель М можно не учиты­вать. В разделе 22.4 мы рассмотрим соответствующий пример.

Когда М велико, граница V ЕМъ худшем случае также велика; но это наиболее пес­симистический вариант, поскольку мы получили его перемножением границ всех случа­ев, которые вытекают из придуманных нами примеров. Фактические затраты для сетей, встречающихся на практике, обычно намного ниже.

С теоретической точки зрения наша ближайшая цель состоит в том, чтобы опреде­лить, используя приблизительную субъективную классификацию, предложенную в разде­ле 17.8, можно ли найти решение задачи о максимальном потоке в сетях с большими це­лочисленными весами (решаемой при использовании алгоритма с полиномиальным временем выполнения). Только что найденные границы не решают этой проблемы, по­скольку максимальный вес М = 2^т может возрастать экспоненциально с увеличением V и E С практических позиций мы нуждаемся в более надежных гарантиях производитель­ности. Возьмем типовой пример из практики, предположим, что мы используем 32-раз­рядные целые числа (т = 32) для представления весов. В графе со многими сотнями вер­шин и тысячами ребер по свойству 22.6 мы должны будем выполнять сотни триллионов (10¹²) операций при прогоне алгоритма вычисления аугментального пути. Если сеть со­держит миллионы вершин, то этот вопрос требует дальнейших исследований, поскольку мы не только не можем иметь дело с весами, величина которых достигает порядка 2^1000000, но еще и потому, что значения V³ и VE настолько велики, что любые границы при этом теряют всякий смысл. Мы же заинтересованы в том, чтобы найти полиномиальные гра­ницы для ответа на вопрос о возможности использования соответствующей модели и на­хождения более точных границ, соответствующих ситуации, с которой мы можем столк­нуться на практике.

Свойство 22.6. носит общий характер: оно применимо к любой реализации алгорит­ма Форда-Фалкерсона. Универсальная природа этого алгоритма предоставляет нам дос­таточную гибкость, чтобы можно было рассматривать целый ряд простых реализаций, преследуя цель улучшить рабочие характеристики алгоритма. Мы надеемся, что конкрет-