Потоки в сетях. Основная задача о максимальном потоке. Простые варианты задачи о максимальном потоке

ПОТОКИВСЕТЯХ

1. Введение

Одной из наиболее интересных и важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой конечной вершине t (стоку). При этом каждой дуге (х_i, х_j) графа G приписана некоторая пропускная способность q_ij, и эта пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге. Эта задача и ее варианты могут возникать во многих практических приложениях, например при определении максимальной интенсивности транспортного потока между двумя пунктами на карте дорог, представляемой графом. В этом примере решение задачи о максимальном потоке укажет также ту часть сети дорог, которая «насыщена» и образует «узкое место» в отношении потока между двумя указанными концевыми пунктами.

Метод решения задачи о максимальном потоке (от s к t) был предложен Фордом и Фалкерсоном , и их «техника пометок» составляет основу других алгоритмов решения многочисленных задач, являющихся простыми обобщениями или расширениями указанной задачи. Следующие возможные варианты задачи о максимальном потоке (от s к t) встречаются в литературе.

(I)  Допустим, что каждой дуге графа приписана не только пропускная способность q_ij, дающая верхнюю границу потока через дугу (х_i, х_j), но также «пропускная способность» r_ij, дающая нижнюю границу потока через дугу. В таком случае далеко не очевидно, что существует допустимое множество потоков, удовлетворяющих требованиям о максимальной и минимальной пропускных способностях дуг. Однако если (в общем случае) существует много таких потоков и если в дополнение к пропускным способностям заданы также стоимости единицы потока, протекающего по дуге, то возникает задача нахождения допустимого потока минимальной стоимости (от вершины s к вершине t).

(II)  Рассмотрим случай, когда ищутся максимальные потоки между каждой парой вершин. Хотя такая задача может быть решена как n (n — 1)/2 «отдельных» (от s к t) задач, но это очень трудоемкий процесс. При нахождении кратчайших цепей между каждой парой вершин графа было установлено, что нет необходимости решать каждую (от s к t) задачу о кратчайшей цепи индивидуально, и в настоящей задаче точно так же существует метод, который — для неориентированных графов — не предполагает обязательного решения задач о максимальных потоках для каждой пары вершин s и t.

III)   Если вместо одного источника и одного стока рассмотреть несколько заданных источников и стоков, причем между различными источниками и стоками протекают потоки различных продуктов, то задача