Задача о максимальном потоке
В теории оптимизации задачи максимального потока включают поиск допустимого потока через сеть потоков , который обеспечивает максимально возможный расход.
Задачу максимального потока можно рассматривать как частный случай более сложных задач сетевого потока, таких как задача циркуляции . Максимальное значение st-потока (т. е. потока от источника s к стоку t) равно минимальной пропускной способности st-среза (т. е. среза, отделяющего s от t) в сети, как указано в max-flow min- теорема о разрезе .
Задача о максимальном потоке впервые была сформулирована в 1954 г. Т.Э. Харрисом и Ф.С. Россом как упрощенная модель советского железнодорожного движения. [1] [2] [3]
В 1955 году Лестер Р. Форд-младший и Делберт Р. Фулкерсон создали первый известный алгоритм — алгоритм Форда-Фалкерсона . [4] [5] В своей статье 1955 г. [4] Форд и Фулкерсон написали, что проблема Харриса и Росса формулируется следующим образом (см. [1] , стр. 5):
Рассмотрим железнодорожную сеть, соединяющую два города через ряд промежуточных городов, где каждому звену сети присвоен номер, представляющий его пропускную способность. Предполагая стационарное состояние, найти максимальный поток из одного заданного города в другой.
Она была поставлена перед авторами весной 1955 г. Т. Е. Харрисом, который совместно с генералом Ф. С. Россом (в отставке) сформулировал упрощенную модель движения железнодорожного транспорта и выделил именно эту проблему как центральную, предложенную модель [11].
