Транспортные сети

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

Если каждый вентиль обладает свойством, что пропускная способность входящих труб равна пропускной способности исходящих труб, то задача, как таковая, отсутствует: мы просто-напросто заполняем все трубы до упора. В противном случае заполненными оказывают­ся не все трубы, однако, нефть течет по трубам, управляемая настройками вентилей, установ­ленных на пересечениях труб, и эти настройки подобраны таким образом, что объем нефти, поступающей на каждое пересечение, равен объему вытекающей из него нефти. Однако из описанного логического равновесия на пересе­чениях следует необходимость равновесия сети

РИСУНОК 22.5. ПОТОКИ В СЕТИ

Транспортная сеть есть взвешенная сеть, в которой мы интерпретируем веса ребер как пропускные способности (вверху). Наша цель заключается в том, чтобы вычислить второе множество весов ребер, ограниченное пропускными способностями, которые мы называем потоками. Нижняя диаграмма служит иллюстрацией наших соглашений, касающиеся вычерчивания сетей потоков. Ширина каждого ребра пропорциональна его пропускной способности; объем потока в каждом ребре показан в виде заштрихован­ной части; поток всегда направлен на странице сверху вниз из единственного истока вверху в единственный сток внизу; пересечения (такие как ребра 1-4 и 2-3 в рассматриваемом примере) не представля­ют вершин, если не обозначены таковыми. За исключением стока и истока, входной поток равен выходному потоку в каждой вершине' например, в вершине 2 имеются две единицы входного потока (из вершины 0) и две единицы выходного потока (по одной единице в вершину 3 и вершину 4).