Глава 7. ПОТОКИ В СЕТЯХ

7.1. Введение

Если мы припишем каждой дуге ориентированного графа поток некоторого вещества, граф становится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с действительным или воображаемым движением товаров, информации или людей. В данной главе дается формальное определение понятия потока в сети и изучается структура потоков. Исследуются две основные задачи: задача максимизации суммарного потока между некоторыми двумя заданными вершинами при условии, что поток через каждую дугу ограничен сверху и снизу (например максимизации транспортного потока при ограниченной пропускной способности отдельных участков дорог), и задача нахождения ограниченных потоков минимальной стоимостью, когда каждой дуге приписана стоимость единицы потока. В разделе 7.9 рассматривается достаточно общий пример. Подробное исследование названных задач можно найти в работе [10] (см. библ. к гл. 1).

7.2. Основная терминология

При изучении потоков достаточно ограничиться рассмотрением ориентированных связных графов, не имеющих петедь. Такие графы будут называться сетями. (Потоки в несвязных графах могут изучаться при отдельном рассмотрении каждой компоненты, а поток в петле не влияет на распределение потока между

вершинами. Таким образом, класс графов, называемых сетями, является достаточно представительным для наших целей.) Чтобы отличить сеть от обычного ориентированного графа, мы будем обозначать ее через А, а не через Пусть задана сеть Потоком в сети называется целочисленная функция определенная на А. Целое число называется потоком по дуге а. Более точно, если то говорят, что поток направлен от и к при и от при

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

Вершины сети обычно классифицируются по их воздействию на поток (создают, поглощают или сохраняют поток). Чтобы формализовать классификацию, обозначим через множество дуг, для которых является начальной вершиной, а через множеств дуг, для которых является конечной вершиной. Тогда целое число определяемое соотношением

называется чистым потоком из относительно Будем далее писать просто если наличие очевидно из ионтекс а. Если в каждой дуге, то первая сумма есть просто общий поток, вытекающий из вершины а вторая — общий поток, вытекающий в вершину Если в некоторых дугах потоки отрицательны, то выделенные суммы не имеют названной интерпретации, но их разность по-прежнему представляет собой чистый поток из вершины Например, на рис. 7.1 множество состоит из дуг множество из дуг

Заметим, что чистый поток из вершины не изменится,

если мы изменим направление дуги и знак ее потока на противоположные. Следовательно, все потоки через дуги можно сделать неотрицательными, не изменяя чистого потока в любой вершине. Однако здесь более полезно оставить направление дуг неизменным и допустить в определенных случаях отрицательные потоки.

Сгруппируем теперь вершины сети в множества и следующим образом:

Элементы множеств и называются источниками, стоками и промежуточными вершинами соответственно. Интуитивно можно считать, что эти вершины соответственно создают, потребляют и сохраняют поток.

Сеть в целом сохраняет любой поток в том смысле, что Это легко видеть, записав следующее выражение:

и замечая, что каждая дуга сети входит точно один раз в каждую двойную сумму.

Рис. 7.1.

Рис. 7.2.

Пример классификации вершин сети рис. 7.2 дан в приведенной ниже таблице. Если

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

(см. скан)

Любой поток в сети можно преобразовать в поток, который имеет только один источник и один сток, увеличив количество вершин в сети. Например, добавим новую вершину и дуги ведущие от к каждому источнику сети. Этим дугам припишем поток

Аналогичным образом, добавим вторую вершину и дуги которые ведут от каждого стока к вершине и имеют поток

В результате получим сеть с одним источником и одним стоком. Рис. 7.3 показывает расширение сети, требуемое для приведения потока в сети рис. 7.2 к стандартной форме. Результирующий поток из в имеет величину 11.

Рис. 7.3.

Большая часть последующего материала относится именно к потокам с единственным источником и единственным стоком. Однако, учитывая возможность указанных выше преобразований, получаемые результаты можно распространить на потоки, имеющие несколько источников и стокор,