1) Решение задачи о максимальном потоке может быть получены достаточно быстро, даже для сетей со сложной структурой.
2) Метод нахождения потока может быть описан в простых терминах, без специальной технической подготовки.
3) Существуют простые методы проверки решения на правильность.
4) Метод не требует использования больших вычислительных мощностей.
«Техника решения формулируется как простая игра, которой можно обучить десятилетнего ребенка», утверждал Болдырев.
Однако, данный метод является эмпирическим, не использует технику перебора с возвратом, и не гарантирует нахождения оптимального решения. Однако, это не смущало Болдырева, поскольку основным применением своего алгоритма он видел транспортные сети. В своей статье 1955 года он привел пример транспортной сети с 41 вершиной и 85 дугами, для которой его алгоритм посчитал верное решение менее чем за тридцать минут. В заключении статьи Болдырев пишет: «Возникает вопрос о систематическом, формальном обосновании; всесторонней математической базе для эмпирицизма и интуиции, и о связи данной техники с другими процессами, такими как многошаговые решающие процессы (multistage decision process), предложенные Беллманом. Все это остается для будущих исследований».
§1.3. Отчет Харриса-Росса
В своем первом отчете о максимальных потоках, Форд и Фалкерсон упомянули, что задача о максимальном потоке была сформулирована Харрисом следующим образом: Рассмотрим транспортную сеть железных дорог, соединяющих два города через некоторое число промежуточных городов. Пусть также каждая дорога, соединяющая два города, имеет некоторую пропускную способность. Найти максимальный поток в данной сети, учитывая условие консервативности (т.е. для любого промежуточного города величина потока, пришедшая в город равна величине потока вышедшего из города).
Позднее в своей книге «Потоки в сетях» (1962), Форд и Фалкерсон дали более точную ссылку: в 1955 году Харрис, в соавторстве с Россом, сформулировали простую модель для трафика в транспортных сетях, и рассматривали эту задачу (прим. – задачу о минимальном разрезе). Речь идет о секретном отчете Харриса и Росса «Фундаментальный метод оценки пропускных способностей транспортных сетей», датированном 24 октября 1955, и предназначенном для ВВС США. В отличие от Форда и Фалкерсона, центральной задачей для Харриса и Росса была задача о минимальном разрезе. А ее применением: нахождение слабых мест в системе железных дорог СССР. (А именно, минимальному разрезу здесь соответствует минимальный набор транспортных путей, уничтожение которого нанесет критический ущерб транспортному сообщению СССР).
§1.4. Метод Форда-Фалкерсона
Теорема Форда и Фалкерсона о связи минимального потока и максимального разреза позволяет обосновать следующий общий метод решения задачи о максимальном потоке. Идея состоит в том, что произвольный поток в сети можно дополнить до максимального. По произвольному потоку f рассмотрим «остаточную сеть» этого потока. Ребрами сети будут исходные ребра графа с пропускной способностью cf(uv) = c(uv) – f(uv), а также обратные ребра с пропускной способностью cf(uv) = f(vu). Метод Форда и Фалкерсона состоит в нахождении в остаточной сети произвольного пути из источника в сток, и дополнении существующего потока (изначально нулевого) вдоль этого пути. Теорема о максимальном потоке и минимальном разрезе позволяет обосновать тот факт, что в случае если такого пути не существует, то поток является максимальным.
В оригинале этот метод был сформулирован в 1956 без использования «остаточной сети», однако его описание в терминах обычной сети очень громоздко, поэтому мы его здесь не приводим. Термин «остаточная сеть» появился позднее, и в настоящее время является одним из основных инструментов исследователей в области потоков.
§1.5. Алгоритм Эдмондса-Карпа
Однако, в общем случае метод Форда и Фалкерсона не является корректным. Существует пример сети с иррациональными пропускными способностями, для которой алгоритм Форда и Фалкерсона не остановится (будет работать «бесконечное время»). Для сетей с целочисленными пропускными способностями время работы составляется O(UVE), где U – максимальная пропускная способность, V – количество вершин и E количество ребер в сети. Сети с рациональными пропускными способностями могут быть сведены к целочисленному случаю путем домножения на наибольший общий делитель знаменателей всех дробей.
В 1969 году Эдмондсом и Карпом была предложена модификация этого алгоритма, позволяющая получить гарантированное время O(VE^2) работы алгоритма следующим способом: на каждом шаге путь из источника в сток нужно выбирать не произвольный, а кратчайший. В этом случае удается доказать оценку O(VE) на число фаз работы алгоритма. Искомая оценка следует из того, что в неориентированном графе возможно найти расстояние между двумя вершинами за время O(E).
§1.6. Дальнейшие улучшения алгоритма построения максимального потока
В 1970 году Дициц опубликовал принципиально новый алгоритм нахождения максимального потока, основанный на поиске псевдомаксимального ("блокирующего") потока во вспомогательной сети.
Блокирующий поток – это поток, величину которого невозможно улучшить путем лишь увеличения потока вдоль отдельных ребер. Строить такой поток Диниц предлагал при помощи классического алгоритма поиска «в ширину».
Другое направление исследований – улучшенные алгоритмы для нахождения максимального потока в сети с целочисленными пропускными способностями. Метод, предложенный Эдмондсом и Карпом в 1972 году (и независимо Диницом в 1973) получил название метода масштабирования пропускных способностей (capacity scaling). Идея метода проста: поток в сети с пропускными способностями, равными половине пропускных способностей исходной сети, мы легко можем получить поток в исходной сети путем умножения его значения на 2. Отдельно нужно обрабатывать ребра с нечетными пропускными способностями. Полученный алгоритм имеет время работы O(nm log U), где n – число вершин сети, m – число ребер, U – максимальная пропускная способность.
Карзанову в 1974г удалось, с помощью модификации алгоритма Диница, добиться оценки быстродействия O(n^3). Им также впервые было введено понятие “предпотока”. В 1978г Малхотри, Кумару м Махешвари (Malhotra, Kumar, Maheshwari) удалось повторить этот результат, однако их алгоритм отличался от алгоритма Карзанова.
Лучший из известных на сегодняшний день алгоритмов был предложен в 1997 году Гольдбергом и Рао (Goldberg, Rao). В качестве вспомогательной процедуры алгоритм использует структуру данных, полученную Гольдбергом и Тарьяном (Tarjan).
В заключение приведем сводную хронологическую таблицу результатов, полученных для задачи о максимальном потоке (везде далее n – число вершин сети, m – число ребер, U – максимальная пропускная способность ребер сети)
Глава 2. Теория паросочетаний
§2.1. Паросочетание в двудольном графе
Основы теории паросочетаний в двудольных графах были заложены Фробениусом (сформулировавшим их в терминах матриц и детерминантов) и Кёнигом. В статье Кёнига (1915г), представленной ранее в Венгерской Академии Наук он описал способ построение двудольного графа по произвольной матрице (a_ij): вершины графа соответствуют строкам и столбцам матрицы, при этом ребро между строкой i и столбцом j существует в том и только том случае, когда a_ij не равно нулю.
Ранее, в апреле 1914 года на Конгрессе Философии Математики в Париже, Кёниг представил теорему о том, что любой регулярный граф без циклов нечетной длины является двудольным.
Впервые, задача близкая к задаче о паросочетании была рассмотрена Кёнигом в 1916 году. Он доказал, что если требуется расположить на квадратной доске размера n*n (при этом часть клеток доски может отсутствовать) фишки в количестве k*n (при этом на одной клетке может лежать более одной фишки), таким образом что в каждой строке и в каждом столбце находится ровно по k фишек, то такую конфигурацию можно получить путем объединения k конфигураций, для каждой из которой в каждом столбце и каждой строке находится ровно одна фишка.
§2.2.Теорема Фробениуса
В 1917 году Фробениус доказал следующую теорему: пусть в матрице A = (a_ij) размера n*n выполнено следующее условие: для любой перестановки p выполнено условие a_1p(1)*..*a_np(n) = 0, то для некоторого числа k найдутся k строк и n – k + 1 столбцов матрице А, такие что любой элемент, лежащий на пересечении этих строк и столбцов, равен нулю. Используя построение Кёнига, этот результат можно переформулировать в терминах двудольных графов: для любого двудольного графа G = (V, E), множество вершин которого разбито на доли V1 и V2, такие, что |V1| = |V2| = n, существует совершенное паросочетение в том и только том случае, когда невозможно выбрать k вершин из V1 и n – k + 1 вершин из V2, таких что между этими вершинами не существует ни одного ребра. Что особенно ценно, Фробениус представил простое комбинаторное доказательство этой теоремы.
§2.3.Теорема Менгера о непересекающихся путях и теорема Кёнига о паросочетании
В 1927 году тополог Карл Менгер сформулировал и доказал следующую теорему. Пусть в неориентированном графе G = (V, E) заданы подмножества P, Q множества вершин V. Тогда максимальное число непересекающихся путей из P в Q равно минимальному размеру множества W вершин, такого что каждый путь из P в Q пересекает W.
Интересно, что первоначально теорема была сформулирована в топологических терминах: компактах и регулярных кривых. Позднее, в 1932 году Кёниг обнаружил в доказательстве Менгера неточность. В марте 1931 года на встрече Математического общества Lorand Eotvos в Будапеште, Кёниг представил новый результат, послуживший основой для доказательства теоремы Менгера: мощность максимального паросочетания в двудольном графе равняется минимальному количеству вершин, необходимых для покрытия всех ребер. (По определению, вершина покрывает все ребра, соседние с данной вершиной, и только их). Кёниг ссылался на результаты, полученные Фробениусом, однако не отметил, что его теорема может быть получена из теоремы Фробениуса. Напротив, в основе доказательства полученного Кёнигом лежит принцип дополнения вдоль чередующихся путей (ставший затем фундаментальным в теории паросочетаний). Опубликованы эти результаты были в 1932 году.