На этом шаге рассмотрим ограничения на решение задачи о максимальном потоке.
Для корректности применения описанного метода нахождения максимального потока в сетях необходимо, чтобы в физической постановке задачи соблюдались следующие условия:
- Ограничение пропускной спосо6ности:
f[U, V] ≤ c[U, V],
где f[U, V] — поток от вершины U к вершине V,
c[U, V] — пропускная способность дуги от вершины U к вершине V. - Граф должен иметь ровно одну вершину-исток (в нее нет входящих дуг, а есть только исходящие из нее), и ровно одну вершину-сток (нет исходящих из нее дуг, а есть только входящие в нее).
- Сохранение потока: для любой вершины графа, кроме истока и стока, сумма потоков по всем входящим в вершину дугам равна сумме потоков по исходящим из нее дугам.
Для нашей задачи о нефтедобывающих вышках и нефтеперерабатывающих заводах не выполнено условие 2 — у нас два истока (вершины 1 и 2) и два стока (вершины 3 и 4). Для того чтобы обеспечить выполнение условия 2, в таких случаях искусственно добавляют исток и сток. Например, для нашей задачи исток — вершина 0 — общий (подземный) резервуар нефти, а сток — вершина 5 — общее "виртуальное" хранилище потребленной нефти. Тогда граф имеет вид, показанный на рис. 1:
Рис.1. Граф с вершинами сток и исток
Важно еще правильно определить веса введенных дуг, то есть "пропускные способности" труб от вершины 0 к вершинам 1 и 2 и от вершин 3 и 4 к вершине 5. В данной задаче корректно ввести понятие "неограниченных" весов. На практике эта переменная получает максимально возможное значение (maxlongint, например, в случае целочисленных весов c[i,j]).
На следующем шаге рассмотрим формальную постановку задачи о максимальном потоке.
