Глава 1. История изучения теории потоков

Начало исследований

Впервые проблемы связанные с пересылкой потоков в сетях были рассмотрены Канторовичем в 1933 году. (Более того – он рассматривал более общую задачу с движением потока жидкостей различных типов (multicommodity flows)). Основы теории потоков были заложены в период с ноября 1954 по декабрь 1955 года исследователями корпорации RAND (Санта-Моника, Калифорния). Проследим за развитием теории потоков в хронологическом порядке по отчетам RAND.

Первый отчет «Максимальный поток в сети» датируется 19м ноября 1954 года. Авторы отчета – Форд (Ford) и Фалкерсон (Fulkerson), доказали теорему о максимальном потоке и минимальном разрезе для неориентированных графов: значение максимального потока в сети равно минимальной пропускной способности разреза. (Разрезом в сети называется разбиение множества ее вершин на два непересекающихся класса, таких что источник и сток лежат в разных классах. Пропускной способностью разреза называется сумма пропускных способностей ребер, концы которых лежат в разных классах.) В 1955 году в работе Робахера (Robacher) было упомянуто, что впервые эту теорему доказал Фалкерсон.

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

Более того, авторы заметили, что задача о максимальном потоке является частным случаем задачи линейного программирования, а стало быть, может быть решена симплекс-методом Данцига (Danzig). В отчете от 1 января 1955 года, Данциг и Фалекрсон показали, что теорема о максимальном потоке и минимальном разрезе может быть выведена из теоремы о сильной двойственности для задач линейного программирования (в работе упоминалось, что этот факт установлен Хоффманом (Hoffman)). Более того, было доказано существование максимального целочисленного потока, для сетей пропускные способности которых являются целочисленными. Следствием этого факта является известная теорема Менгера (Menger) о непересекающихся путях. 1 апреля 1955 года Данциг и Фалкерсон описали простой способ вычисления максимального потока основанный на симплекс-методе. 26 мая 1955 года Робахер независимо доказал теорему о максимальном потоке и минимальном разрезе, сведя ее к теореме Менгера.

Эвристика Болдырева

До тех пор пока существующие алгоритмы вычисления максимального потока основывались на симплекс-методе, одной из важнейших задач в теории потоков было построение комбинаторного алгоритма решения этой задачи. 3 июня 1955 года в Нью-Йорке на встрече Американского Общества Исследования Операций Болдырев сделал доклад (опубликованный затем как отчет RAND от 5 августа 1955 года) об эвристическом алгоритме нахождения максимального потока. Метод Болдырева является так называемым «жадным алгоритмом»: он пытается послать как можно больше потока из источника, до тех пор, пока не обнаружится критическая вершина (т.е. такая вершина из которой невозможно передать поток далее). Такая ситуация устраняется путем возвращения избыточного потока в источник. По словам Болдырева, основные достоинства его метода заключались в том, что:

1) Решение задачи о максимальном потоке может быть получены достаточно быстро, даже для сетей со сложной структурой.

2) Метод нахождения потока может быть описан в простых терминах, без специальной технической подготовки.

3) Существуют простые методы проверки решения на правильность.

4) Метод не требует использования больших вычислительных мощностей.

«Техника решения формулируется как простая игра, которой можно обучить десятилетнего ребенка», утверждал Болдырев.

Однако, данный метод является эмпирическим, не использует технику перебора с возвратом, и не гарантирует нахождения оптимального решения. Однако, это не смущало Болдырева, поскольку основным применением своего алгоритма он видел транспортные сети. В своей статье 1955 года он привел пример транспортной сети с 41 вершиной и 85 дугами, для которой его алгоритм посчитал верное решение менее чем за тридцать минут. В заключении статьи Болдырев пишет: «Возникает вопрос о систематическом, формальном обосновании; всесторонней математической базе для эмпирицизма и интуиции, и о связи данной техники с другими процессами, такими как многошаговые решающие процессы (multistage decision process), предложенные Беллманом. Все это остается для будущих исследований».

Отчет Харриса-Росса

В своем первом отчете о максимальных потоках, Форд и Фалкерсон упомянули, что задача о максимальном потоке была сформулирована Харрисом следующим образом: Рассмотрим транспортную сеть железных дорог, соединяющих два города через некоторое число промежуточных городов. Пусть также каждая дорога, соединяющая два города, имеет некоторую пропускную способность. Найти максимальный поток в данной сети, учитывая условие консервативности (т.е. для любого промежуточного города величина потока, пришедшая в город равна величине потока вышедшего из города).

Позднее в своей книге «Потоки в сетях» (1962), Форд и Фалкерсон дали более точную ссылку: в 1955 году Харрис, в соавторстве с Россом, сформулировали простую модель для трафика в транспортных сетях, и рассматривали эту задачу (прим. – задачу о минимальном разрезе). Речь идет о секретном отчете Харриса и Росса «Фундаментальный метод оценки пропускных способностей транспортных сетей», датированном 24 октября 1955, и предназначенном для ВВС США. В отличие от Форда и Фалкерсона, центральной задачей для Харриса и Росса была задача о минимальном разрезе. А ее применением: нахождение слабых мест в системе железных дорог СССР. (А именно, минимальному разрезу здесь соответствует минимальный набор транспортных путей, уничтожение которого нанесет критический ущерб транспортному сообщению СССР).