О потоках в сетях с барьерной достижимостью

1. Сети с барьерной достижимостью

Графы и сети с барьерной достижимостью были введены в рассмотрение в работах [2, 3, 5]. Напомним, что такое граф с барьерной достижимостью.

На графе с барьерной достижимостью множество дуг $U$ состоит из трех непересекающихся подмножеств $U_N$ $—$ нейтральных дуг, $U_{\uparrow }$ $—$ «увеличивающих» дуг, $U_B$ $—$ барьерных дуг. Последние два множества не равны пустому множеству. Для каждой барьерной дуги графа $u$ задана ее высота (высота барьера) $—$ натуральное число $h_u$. Опишем, какие пути являются допустимыми на графе с барьерной достижимостью.

С каждым отрезком пути $\mu$ на графе с барьерной достижимостью связана характеристика этого отрезка пути ${\chi }_{\mu }\mathrm{<mo\; stretchy="false">(</mo>}i\mathrm{<mo\; stretchy="false">)</mo>}$, $i{\in }_{+}$, которая определена индуктивно следующим образом:

${\chi }_{\mu }\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo><mo>=</mo>0<mo>;</mo>}$, (1)

${\chi }_{\mu }i+\left\{\begin{array}{l}\\ \\ \end{array}\right.\begin{array}{cc}{\chi }_{\mu }i& если \mu i+\in U_N\\ {\chi }_{\mu }i+\mathrm{1,}& \text{если }\mu i+\in U_{\uparrow }\\ {\chi }_{\mu }i-h_{\mu i+}\mathrm{,}& \text{если }\mu i+\in U_B\text{ и }{\chi }_{\mu }i\ge h_{\mu i+}\mathrm{.}\end{array}\mathrm{.}$ (2)

Третья строка в (2), в частности, означает, что в случае ${\chi }_{\mu }\mathrm{<mo\; stretchy="false">(</mo>}i\mathrm{<mo\; stretchy="false">)</mo><mo><</mo>}{h}_{\mu \mathrm{<mo\; stretchy="false">(</mo>}i+\mathrm{1<mo\; stretchy="false">)</mo>}}$ барьерная дуга закрыта для прохождения путем $\mu$.

Выписанные требования на допустимость пути на графе с барьерной достижимостью в терминах характеристики ${\chi }_{\mu }\mathrm{<mo\; stretchy="false">(</mo>}i\mathrm{<mo\; stretchy="false">)</mo>}\ge h_{\mu \mathrm{<mo\; stretchy="false">(</mo>}i+\mathrm{1<mo\; stretchy="false">)</mo>}}$ можно воспринимать «энергетически». Начиная движение по пути $\mu$, перемещаемая по сети единица вещества обладает нулевой энергией (п. 1.), при прохождении по нейтральной дуге её энергия не изменяется (см. (1)), при прохождении по увеличивающей дуге она увеличивается на $1$ (см. (2)), барьерная дуга доступна для прохождения, только, если накопленная энергия не меньше, чем высота барьера, а после прохождения по барьерной дуге накопленная энергия уменьшается на величину равную высоте барьера (см. (2)).

Классическая задача о стационарном потоке в сети (см. [6]) $—$ это задача о транспортировке вещества из источника сети в сток по путям на графе, ведущим из источника в сток, таким образом, чтобы на каждой из дуг величина потока не превышала пропускную способность дуги $\rho \mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$ (см. (3), и чтобы в каждой промежуточной вершине сети выполнялось условие сохранения потока (суммарный поток по всем дугам, приходящим в вершину, должен быть равен суммарному потоку по все выходящим из неё дугам (см. (4)). Таким образом, поток в сети является функцией $\phi \mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$, определенной на дугах сети и удовлетворяющей двум условиям:

$\phi \mathrm{<mo\; stretchy="false">(</mo>}U\mathrm{<mo\; stretchy="false">)</mo>}\le \rho \mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>,}u\in U\mathrm{,}$  (3)

$\sum _{u\in U_{+}x}\phi u\sum _{u\in U_{-}x}\phi ux\in X_{\text{вн}}$,  (4)

здесь $U_{+}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$, $U_{-}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ $—$ множества входящих и исходящих, соответственно, дуг вершины $x$, а $X_{\text{вн}}$ $—$ множество внутренних вершин сети, не являющихся источниками и стоками. В результате осуществляется транспортировка вещества по путям сети, ведущим из источника в сток.

Понятно, что такое определение потока для сети с барьерной достижимостью не подходит, поскольку мы должны учитывать, что транспортировка вещества из источника в сток должна осуществляться из источника в сток только по допустимым путям и при этом должны выполняться условия сохранения потока в промежуточных вершинах сети. Ясно, что условия классические условия сохранения потока Форда$–$ Фалкерсона (условия (3), (4)) не содержат никаких требований на допустимость путей, по которым осуществляется транспортировка. Эту коллизию в работе [2] авторы разрешали следующим образом. По исходному графу строили его развертку, на которой кроме исходных вершин графа, имелись слои их двойников (слои соответствовали уровням накопленной энергии), а дугам исходного графа на развертке соответствовали дуги, построение которых определялось типом исходной дуги и высотой барьерных дуг. (Подробно о развертке графа см. в [5]).

Поскольку одной дуге исходного графа на развертке соответствует целый набор дуг, возникает задача «переноса» пропускной способности исходной на построенные из неё дуги развертки. Наделив все эти дуги пропускной способностью породившей их дуги, мы получаем сеть, на которой потоки проходят по допустимым путям. Однако при переносе построенного потока на исходную сеть может нарушаться условие (3).

Вариант нахождения допустимого потока в сетях с ограничениями на достижимость, учитывающий соблюдение условия (3), был предложен Я. М. Ерусалимским и В. А. Скороходовым в [4]. В этой работе было введено понятие графов со связанными дугами, состоящее в том, что на графе имеются выделенные непустые непересекающиеся подмножества дуг. Для дуг из таких подмножеств определена их суммарная пропускная способность (а не пропускная способность каждой дуги). Это позволило предложить эвристический алгоритм, позволяющий распределять суммарную пропускную способность связанных дуг в пропускную способность каждой из дуг с целью нахождения потока, который можно было бы истолковать как допустимый поток на исходном графе с барьерной достижимостью.

Связанными на развертке объявлялись подмножества дуг, построенных из одной дуги исходного графа. Фактически, задача нахождения максимального потока в сети с барьерной достижимостью сводилась к отысканию такого варианта раздачи пропускных способностей, в результате которого пропускная способность полученной развертки была максимальной. Понятно, что задача раздачи пропускных способностей является $NP$ =полной, а предложенный авторами алгоритм раздачи пропускных способностей, названный «алгоритмом прорыва», является эвристическим (см., например, [1]).

2. Поток в сети с барьерной достижимостью как вектор=функция

Попробуем определить, что такое поток в сети с барьерной достижимостью, не используя для этого переход к развертке. Для этого нам потребуется пересмотреть основное понятие $—$ поток в сети.

Определение   Потоком в сети с барьерной достижимостью будем называть вектор=функцию ${\mathrm{<mo>\{</mo>}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>\}</mo>}}_{0\le i\le M}$, определенную на множестве дуг графа, каждая координата которой принимает неотрицательные значения, и для которой выполнены следующие условия:

${\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^M}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}\le \rho \mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>,}u\in U\mathrm{.}$ (5)

${\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0,}0\le i\le h_u\mathrm{,}u\in U_B$, (6)

${\displaystyle \sum _{u\in U_N\cup \cap U_{+}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}}}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}+{\displaystyle \sum _{u\in \mathrm{<mo\; stretchy="false">(</mo>}{U}_{\uparrow }\cap U_{+}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}}}{\phi }_{i-1}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}+{\displaystyle \sum _{u\in U_B\cap U_{+}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}}}{\phi }_{i+h_u}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{u\in U_{-}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}}}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$, 7)

Ясно, что при этом выполняется и условие (8):

${\displaystyle \sum _{u\in U_{+}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}}}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{u\in U_{-}\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}}}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>,}x\in X_{\text{âí}}\mathrm{,}0\le i\le M\mathrm{.}$ (8)

Условие (5) $—$ аналог условия (3), условие (6) $—$ учет высот барьеров, условие (7) $—$ условие сохранения потока как вектор=функции во внутренних вершинах сети (аналог условия (4)).

Для того чтобы понять смысл сказанного выше, рассмотрим сеть, приведенную на рис. 1. Около дуг выписаны их пропускные способности. Знаком « $+$ » помечена увеличивающая дуга. В сети есть две барьерные дуги $\mathrm{<mo\; stretchy="false">(</mo>3<mo>;</mo>6<mo\; stretchy="false">)</mo>}$ $—$ высоты $4$ и $\mathrm{<mo\; stretchy="false">(</mo>3<mo>;</mo>7<mo\; stretchy="false">)</mo>}$ $—$ высоты $2$. Если эту сеть рассматривать без ограничений на достижимость, то величина максимального потока в сети равна $3$, и он реализуем следующим потоком: $\phi \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>1<mo>;</mo>2<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>3}$; $\phi \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>2<mo>;</mo>3<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>3}$; $\phi \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>3<mo>;</mo>7<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>2}$; $\phi \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>7<mo>;</mo>8<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>2}$; $\phi \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>3<mo>;</mo>6<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>1}$; $\phi \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>7<mo>;</mo>8<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>1}$ $\phi \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>3<mo>;</mo>4<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>0}$; $\phi \mathrm{<mo\; stretchy="false">(</mo>4<mo>;</mo>5<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>0}$; $\phi \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>5<mo>;</mo>2<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>0}$;

Ясно, что этот поток не является допустимым в этой сети с барьерной достижимостью (энергия вещества, протекающего по барьерным дугам, равна $0$ ). При этом дуги $\mathrm{<mo\; stretchy="false">(</mo>2<mo>;</mo>3<mo\; stretchy="false">)</mo>}$, $\mathrm{<mo\; stretchy="false">(</mo>3<mo>;</mo>4<mo\; stretchy="false">)</mo>}$, $\mathrm{<mo\; stretchy="false">(</mo>4<mo>;</mo>5<mo\; stretchy="false">)</mo>}$, $\mathrm{<mo\; stretchy="false">(</mo>5<mo>;</mo>2<mo\; stretchy="false">)</mo>}$ недогружены этим потоком.

Рис. 1. Сеть с барьерной достижимостью

В таблице 1, приведен пример потока как вектор=функции, заданной на дугах этой сети с барьерной достижимостью (рис. 1).

Таблица 1.

Легко проверить, что приведенный поток удовлетворяет условиям (5)(7) и, значит, является потоком в сети с барьерной достижимостью.

Таблица 1 позволяет понять, что происходит в этой сети с барьерной достижимостью. Из источника в каждый момент времени поступает $2$ =единицы вещества с энергетическим уровнем равным нулю, эта порция вещества перемешается по сети и «закручивается» на контуре, две единицы вещества совершают двойную прокрутку, одна единица вещества совершает двойную прокрутку по контуру, а вторая $—$ четырехкратную. Таким образом, на дугах контура возникает ситуация, которую мы назвали наложением потока.

Таблица 2.

Рассмотрим еще один поток в этой сети, заданный таблицей 2. Таблица позволяет понять, что происходит в этой сети с барьерной достижимостью для этого потока. Из источника в каждый момент времени поступает $\mathrm{2,4}$ единицы вещества с энергетическим уровнем равным нулю, эта порция вещества перемешается по сети и «закручивается» на контуре, две единицы вещества совершают двойную прокрутку, а $\mathrm{0,4}$ единицы из них (из $\mathrm{2,4}$ ) $—$ четырехкратную.

Ясно, что поток, заданный таблицей 1, не является максимальным, а поток, заданный таблицей 2, является максимальным потоком в этой сети с барьерной достижимостью (хотя оба потока полностью загружают дугу $\mathrm{<mo\; stretchy="false">(</mo>2<mo>;</mo>3<mo\; stretchy="false">)</mo>}$, образующую разрез в этой сети.

Замечание 1 Понятно, что обычную сеть можно считать сетью с барьерной достижимостью, у которой $U_N\mathrm{<mo>=</mo>}U$, $U_B\mathrm{<mo>=</mo>}{U}_{\uparrow }\mathrm{<mo>=</mo>}\varnothing$. При этом вектор=функция потока такова, что для каждой дуги сети ${\phi }_1\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\phi }_2\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\dots \mathrm{<mo>=</mo>}{\phi }_M\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0}$, а функция ${\phi }_0\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$ представляет собой обычный поток в сети в соответствии с классическим определением потока (см. [6]).

Замечание 2 Если вектор=функция ${\mathrm{<mo>\{</mo>}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>\}</mo>}}_{0\le i\le M}$ $—$ поток в сети с барьерной достижимостью (см. определение 0.2), то функция $\phi$, определенная на множестве дуг сети равенством

$\phi \mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^M}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$

является обычным потоком в этой сети без ограничений на достижимость.

Замечание 3 Если вектор=функция ${\mathrm{<mo>\{</mo>}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>\}</mo>}}_{0\le i\le M}$ $—$ поток в сети с барьерной достижимостью (см. определение), то функция $\phi$, определенная на множестве дуг сети равенством

$\phi \mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^M}{\phi }_i\mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$

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

Действительно, увеличим пропускную способность каждой из дуг $\mathrm{<mo\; stretchy="false">(</mo>1<mo>;</mo>2<mo\; stretchy="false">)</mo>}$, $\mathrm{<mo\; stretchy="false">(</mo>3<mo>;</mo>6<mo\; stretchy="false">)</mo>}$ и $\mathrm{<mo\; stretchy="false">(</mo>6<mo>;</mo>8<mo\; stretchy="false">)</mo>}$ на единицу. Величина максимального потока в этой сети с барьерной достижимостью не изменится (приведенный в таблице 2 поток останется максимальным), а величина максимального потока в этой сети без ограничений на достижимость увеличится на единицу.

Рассмотрению эффектов падения величины максимального потока в сети при введении ограничений на достижимость посвящена статья [7].