|
Пусть в ориентированной сети S = (N, U) от источника к стоку протекает поток, величина которого равна V. Поскольку пропускная способность каждой дуги с (i, j) является величиной конечной, то максимальная величина допустимого потока всей сети тоже ограничена. Максимальный поток сети определяется на основе одного из основных понятий теории сетей — понятия разреза. Введем понятие разреза.
Множество вершин N сети S = (N, U) можно разбить на два непересекающихся подмножества Np и , которые соединяются между собой дугами, образующими множество Up. Причем исток s принадлежит множеству узлов Np, а сток t принадлежит множеству узлов . Тогда величина потока из множества Np в множество , протекающего по дугам Up не может быть больше, чем сумма пропускных способностей дуг этого множества, что можно записать таким образом.
Этот барьер для потока, отделяющий множество узлов Np от множества узлов , называется разрезом и обозначается (Np, ). Разрез представляет такое множество дуг Up, исключение которых отделяет_вход от выхода сети, и, следовательно, отделяет множество Np от сети S = (N, U) таким образом, что существование потока в таком случае невозможно, и тогда V=0. Причем начало дуги разреза принадлежит множеству Np , а конец — . Таким образом в разрез входят дуги, соединяющие вершины этих множеств.
Величина максимального потока от источника s к стоку t ограничена сверху величиной разреза C(Np, ), определяемой суммой пропускных способностей всех входящих в него дуг множества Up и, следовательно, VC(Np, ). Минимальным разрезом сети называется разрез, имеющий минимальную величину.
В соответствии с теоремой о максимальном потоке и минимальном разрезе, сформулированной Фордом и Фалкерсоном, величина максимального потока Vmax от входа s (источника) в выход t (сток) равна величине минимального разреза, отделяющего
вход и выход сети и, следовательно, .
Рассматриваемые сети являются сетями с ограниченной пропускной способностью, что имеет распространение в реальной жизни. Это послужило поводом к появлению и постановке задач о максимальном потоке, связанных с определением максимально допустимой величины Упри соблюдении условий, записанных в виде системы уравнений и неравенств.
В сформулированной выше задаче для сохранения потока автомобилей, например, через перекресток (3) необходимо, чтобы поступающие потоки автомобилей к этой вершине (3) (1, 3) и (2, 3) равнялись величине потока, вытекающего из этой вершины (3, 4), что можно записать
(1,3) + (2,3) = (3,4)
или (1,3) + (2,3)-(3,4) = 0.
Аналогичные уравнения можно записать для остальных вершин сети. Поскольку задача заключается в определении максимально возможного потока в сети, то необходимо последовательно вычислить потоки через все разрезы и выбрать из них минимальный.
Рассмотренные алгоритм и примеры моделирования позволяют решать аналогичные по своей природе задачи по бесперебойному снабжению потоками электричества, топлива (газа, мазута), воды, продовольственными и непродовольственными товарами населенных пунктов и таким образом предупредить появление критических ситуаций в городах и поселках нашей страны.
|
