Постановка задачи. Одной из задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой вершине t

Одной из задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой вершине t (стоку). При этом каждой дуге (граф ориентированный) (ij) приписана некоторая пропускная способность C(i, j), определяющая максимальное значение потока, который может протекать по данной дуге. Со­держательных интерпретаций задачи достаточно много, и, бе­зусловно, они усилят и сделают более понятными сложные за­нятия по этой проблематике.

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

Одним из фундаментальных фактов теории потоков в сетях является классическая теорема о максимальном потоке и ми­нимальном разрезе. Разрезом называют множество дуг, удале­ние которых из сети приводит к «разрыву» всех путей, веду­щих из s в t. Пропускная способность разреза — это суммарная пропускная способность дуг, его составляющих. Разрез с мини­мальной пропускной способностью называют минимальным разрезом.

Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности минимального разре­за, разделяющего s и t, причем существует поток, достигающий этого значения.

Теорема устанавливает экви­валентность задач нахождения максимального потока и минима­льного разреза, однако не определяет метода их поиска.

Пример. Показана сеть (рис.10), источник — вершина 1, сток — вер­шина 6, в скобках у дуг указаны их пропускные способности. Минимальный разрез — дуги (1, 2) и (3, 4), следовательно, со­гласно теореме максимальный поток равен 4. Разрез определен путем простого перебора. Логика его «лобового» поиска очевид­на. Осуществляем перебор по дугам путем генерации всех воз­можных подмножеств дуг. Для каждого подмножества дуг проверяем, является ли оно разрезом. Если является, то вычисляем его пропускную способность и сравниваем ее с минимальным значением. При положительном результате сравнения запоми­наем разрез и изменяем значение минимума. Удачный выбор данных позволяет сделать программный код компактным, но очевидно, что даже при наличии различных отсечений в перебо­ре метод применим только для небольших сетей. Однако, как найти максимальный поток, т. е. его распределение по дугам, по-прежнему открытый вопрос.

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

Пример. Рядом с пропуск­ными способностями дуг указаны потоки, построенные на этих дугах. На рисунке по­ток через сеть равен 10 и найдена увели­чивающаяся цепочка, выделенная «жирны­ми» линиями. Обра­тите внимание на ориентацию дуг, входящих в цепочку. По данной цепочке можно пропустить поток, равный 1, пропуск­ная способность дуги (5, 6). Изменяем суммарный поток, его значение становится равным 11. Поток увеличен, необходимо продолжить поиск увеличивающихся цепочек; если окажется, что построить их нельзя, то результирующий поток максима­лен. Заметим, что для данного примера это значение потока окончательное. Обратите внимание на то, как изменен поток на дугах сети в зависимости от их ориентации.

рис.10

рис.11