Задача о максимальном потоке

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

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

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

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

Задача о потоках с выигрышами. Во всех рассмотренных выше случаях неявно допускалось, что поток на входе дуги такой же, как и на выходе. Если рассмотреть граф, в котором выходной поток дуги равен ее входному потоку, умноженному на некоторое неотрицательное число, то задачу о максимальном потоке называют задачей о потоках с выигрышами. В такой задаче потоки могут «порождаться» и «поглощаться» самим графом, так что поток, входящий в , и поток, покидающий , могут изменяться совершенно независимо.