Maximum flow in parallel networks with connected arcs

Введение.

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

Однако несмотря на то, что известны быстрые, полиномиально вычислимые алгоритмы поиска максимального потока $–$ ранее было показано, что эти алгоритмы, как и иные классические алгоритмы на графах, в общем случае неприменимы для решения задач в сетях со связанными дугами [1]. Постановка задачи о максимальном потоке в сети со связанными дугами описана далее.

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

1. Постановка задачи. В классической постановке потоковых задач рассматриваются сети следующего вида.

Определение 1. Сетью назовем связный конечный ориентированный граф $G\left(X\mathrm{,}U\mathrm{,}f\mathrm{,}\rho \right)$, в котором $X$ $—$ множество вершин сети, $U$ $—$ множество дуг сети, $f : U\to X \times X$ $—$ отображение инцидентности, $\rho : U\to R_{+}=\left(0;+\infty \right)$ $—$ отображение, назначающее каждой из дуг $u$ пропускную способность $\left(\rho u\right)$.

Сети, удовлетворяющие определению 1 будем называть классическими сетями. Как и в [8], источник будем обозначать через $s$, сток через $t$, а все вершины сети $G\left(X\mathrm{,}U\mathrm{,}f\mathrm{,}\rho \right)$ из множества $X\backslash \left\{s\mathrm{,}t\right\}$ будем называть промежуточными.

Определение 2. Потоком в сети $G$ называется отображение $\phi$, ставящее в соответствие каждой из дуг $u$ значение из $\left[0; \rho \left(u\right)\right]$, удовлетворяющее в каждой промежуточной вершине $x$ соотношению неразрывности потока

$\sum _{u\in U^{-}\left(x\right)}\phi \left(u\right) =\sum _{ u\in U^{+}\left(x\right)}\phi \left(u\right)$

Величиной потока $\phi$ (обозначаемой через $VG\left(\phi \right)$ ) в сети $G$ назовем суммарную величину потока $\phi$ по дугам, входящим в сток, т.е.

$VG\left(\phi \right) =\sum _{u\in U^{-}\left(t\right)}\phi \left(u\right)$

Для классических сетей задача поиска величины максимального потока $VG$ решена Л. Фордом и Д. Фалкерсоном (см. [6]). Для ее решения используются алгоритмы, в том числе имеющие квадратичную от размеров сети вычислительную сложность (см. [7]).

Определение 3. Сеть со связанными дугами $—$ это сеть, множество дуг $U$ которой содержит такое подмножество дуг $U^s\subseteq U$, $\left|U^s\right|\ge 2$, называемое множеством связанных дуг. Для дуг из $U^s$ не задана пропускная способность $\rho \mathrm{<mo\; stretchy="false">(</mo>}u\mathrm{<mo\; stretchy="false">)</mo>}$, а задана суммарная пропускная способность $P\left(U^s\right)$. Сети со связанными дугами возникают естественным образом при рассмотрении сетей с ограничениями на достижимость (см. [2, 4]).

В общем случае может быть задано несколько множеств связанных дуг, причем они должны быть попарно непересекающимися, но в данной работе будем считать, что сеть $G$ содержит ровно одно множество связанных дуг.

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

Для того, чтобы стало возможным назначать поток связанным дугам, необходимо сначала определить пропускную способность каждой из связанных дуг $\rho \left(u\right), \rho \left(u\right)\ge \mathrm{0,} u\in U^s$, так, чтобы выполнялось соотношение

$\sum _{u\in U^s}\rho \left(u\right) \le P\left(U^s\right)$                                                                                     (1)

После назначения $\rho \left(u\right)$ для дуг множества $U^s$ сеть со связанными дугами может рассматриваться как классическая сеть, которую будем обозначать $G_{\rho }$, и на полученной сети уже можно рассматривать задачу о нахождении величины максимального потока $V{G}_{\rho }$.

Определение 4. Величиной максимального потока в сети со связанными дугами называют величину $VG = \max V{G}_{\rho }$, где $\max$ берется по всем возможным назначениям $\rho \left(u\right)$, $u\in U^s$.

Замечание. Ясно, что для нахождения $VG$ в сети со связанными дугами можно рассматривать только такие назначения пропускных способностей, для которых в (1) выполняется равенство.

Рассмотрим пример сети со связанными дугами и обсудим, как различные варианты назначения $\rho \left(u\right)$ связанным дугам влияют на $V{G}_{\rho }$.

Пример 1. На рис. 1 изображена сеть со связанными дугами. Здесь и далее в примерах связанные дуги изображены стрелками со штриховыми линиями, а несвязанные дуги $—$ стрелками со сплошными линиями. Пропускные способности дуг указаны на рисунке, а $P\left(U^s\right) =3$.

Рис. 1. Сеть с двумя связанными дугами

Если для верхней связанной дуги $u_1=\left(1;2\right)$ с рис. 1 назначить $\rho \left(u_1\right)=2$, а для нижней связанной дуги $u_2 =\left(1;3\right)$ назначить $\rho \left(u_2\right) = 1$, то будет получена сеть, изображенная на рис. 2, для которой величина максимального потока равна $2$.

Рис. 2. Неоптимальное назначение пропускных способностей связанных дуг

Однако для сети, изображенной на рис. 1, существует оптимальное назначение пропускных способностей дуг, при котором достигается максимальный поток величиной в $3$, а именно, такое назначение, что $\rho \left(u_1\right) =1$, $\rho \left(u_2\right) =2$ (рис. 3).

Рис. 3. Оптимальное назначение пропускных способностей связанных дуг

Ясно, что существует бесконечное количество способов назначения для $u\in U^s$, а значит, и бесконечное количество классических сетей, которые могут быть получены из сети со связанными дугами. Тогда задача поиска максимального потока величиной $VG$ для сети со связанными дугами $G$ формулируется как задача нахождения такого назначения пропускных способностей связанным дугам, при котором будет получена сеть, максимальный поток в которой является наибольшим по величине среди максимальных потоков всех возможных сетей, которые могут быть получены из $G$ путем назначения для дуг $U^s$.

Сеть, изображенная на рисунке 1, примечательна тем, что при любом назначении пропускных способностей, при котором $\rho \left(u_1\right)\ne 1$ и $\rho \left(u_2\right)\ne 2$ будет получена классическая сеть, величина максимального потока в которой не будет равна $VG$.

Однако существуют сети со связанными дугами, из которых может быть получено более одной классической сети, имеющей $V{G}_{\rho }= VG$. Например, если для сети, изображенной на рис. 1, суммарная пропускная способность $P\left(U^s\right)=10$, то при любых назначениях, при которых одновременно $\rho \left(u_1\right)>1$ и $\rho \left(u_2\right)>2$, будет $V{G}_{\rho } = VG$. Кроме того, при назначении не всей суммарной пропускной способности, а только $\rho \left(u_1\right)=1$ и $\rho \left(u_2\right) =2$ из $P\left(U^s\right) = 10$, остаточная (неиспользованная) пропускная способность $P_{\text{res}}\left(U^s\right)$ составит $7$, а максимальный поток величины $VG$ все равно будет получен. Но также ясно, что при любом $\rho \left(u_1\right)>8$ или $\rho \left(u_2\right)>9$ величина максимального потока получаемой классической сети $V{G}_{\rho }\ne VG$.

В сетях со связанными дугами проявляется «нелокальность» влияния назначений пропускных способностей. Приведенный ниже пример раскрывает данную проблему.

Пример 2. Пусть дуги сети (рис. 4), не принадлежащие множеству связанных дуг, имеют пропускные способности, равные $1$, а $P\left(U^s\right)=1$, где $U^s$ состоит из дуг $1$ - $2$ и $3$ - $5$.

Рис. 4. Сеть со связанными дугами 1-2 и 3-5

При назначении пропускной способности по дуге $3$ - $5$ величиной $1$ используется вся пропускная способность связанных дуг, а поток в данной сети осуществим лишь по пути $1$ - $3$ - $5$ (рис. 5) и является максимальным потоком. Возможность назначения ненулевого потока по дуге $1$ - $2$ заблокирована, однако величина максимального потока в полученной сети не равна $VG$.

Рис. 5. Блокирующий поток в сети со связанными дугами

Однако если произвести назначение пропускной способности величиной $1$ по дуге $1$ - $2$, то по дугам $1$ - $2$, $2$ - $5$, $1$ - $3$, $3$ - $4$, $4$ - $6$ (рис. 6) станет осуществимым максимальный поток величиной $V{G}_{\rho }=VG=2$.

Рис. 6. Максимальный поток в сети со связанными дугами

Этот пример отражает не только свойство нелокальности изменений, происходящих при назначениях пропускных способностей в сети со связанными дугами, но также заставляет обратить внимание, на то, что несмотря на одинаковые пропускные способности (а соответственно, и возможность внести одинаковый вклад в формирование максимального потока), связанные дуги $1$ - $2$ и $3$ - $4$ неравноценны и любое назначение ненулевой пропускной способности по дуге $3$ - $4$ приводит получению сети, величина максимального потока в которой не равна $VG$.

Может показаться, что найденный максимальный поток равен сумме пропускных способностей дуг любого из минимальных разрезов данной сети (например, разреза, состоящего из дуг $1$ - $2$ и $1$ - $3$ ). Но для сетей со связанными дугами понятие минимального разреза не имеет смысла, так как для каждой из связанных дуг, взятой в отдельности, пропускная способность не определена. Минимальный разрез может быть определен лишь для классических сетей, полученных из сети со связанными дугами.

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

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

Определение 5. Параллельная сеть $—$ сеть, содержащая только простые пути, ведущие из источника в сток, которые не имеют общих вершин, отличных от источника и стока (см. [5]).

Представленная ранее сеть (см. рис. 4) не удовлетворяет приведенному определению 5, поскольку простые пути $1$ - $3$ - $5$ и $1$ - $3$ - $4$ - $5$ из источника $1$ в сток $5$ в пересечении по вершинам содержат не только источник и сток, но и общую промежуточную вершину $3$. Из определения 5 следует, что

$\left(\forall x\in X\left\{\backslash s\mathrm{,}t\right\}\right){\text{\hspace{1em}deg}}_{+}x =de{g}_{-}x = 1$                                                         (2)

${\mathrm{deg}}_{-}s = {\mathrm{deg}}_{+}t = p\mathrm{,}$                                                                                (3)

где ${\mathrm{deg}}_{+}z$, ${\mathrm{deg}}_{-}z$ $—$ полустепени захода и исхода вершины $z$ ( $z\in X$ ) соответственно, а $p$ $—$ количество параллельных путей.

Если сеть $G\left(X\mathrm{,}U\mathrm{,}f\mathrm{,}\rho \right)$ удовлетворяет определению 1, а именно,

 $c\left(G\right) = 1$                                                                                                  (4)

где $c\left(G\right)$ $—$ число компонент связности графа $G$, то следствия (2) и (3) $—$ необходимые и достаточные условия, при выполнении которых $G$ является параллельной сетью.

Из условий (2), (3), (4) определение того, является ли сеть параллельной, осуществимо за линейное от размеров сети (количества дуг и вершин сети) время путем модифицированного обхода в глубину (см. [3]).

Замечание. Определение 4 сформулировано для сетей с одним источником и одним стоком, но может быть распространено и на сети с несколькими источниками и стоками. Если при объединении всех источников в один источник и объединении всех стоков в один сток будет получена параллельная сеть, то будем считать исходную сеть параллельной (для такой сети условия (2), (3), (4) должны быть сформулированы с учетом нескольких источников и стоков).

Примером параллельной сети с одним множеством связанных дуг является сеть, изображённая на рис. 7.

Рис. 7. Параллельная сеть со связанными дугами

Пример 3. Пропускные способности несвязанных дуг указаны на рис. 7, $P\left(U^s\right)=12$. Если для этой сети, назначить ненулевую пропускную способность величины $4$ для связанных дуг по пути $1$ - $2$ - $3$ - $4$, а для остальных связанных дуг установить пропускную способность в $0$, то будет получена сеть, изображенная на рис. 8, для которой $V{G}_{\rho }= 4$.

Рис. 8. Параллельная сеть с ненулевыми пропускными способностями пути 1-2-3-4

Если при назначении пропускных способностей для этой же сети установить ненулевую пропускную способность только для связанных дуг пути $1$ - $5$ - $6$ - $7$ - $4$ величины $6$, а для остальных связанных дуг назначить нулевую пропускную способность, то будет получена классическая сеть, изображенная на рис. 9. Величина максимального потока в полученной сети составит $6$.

Рис. 9. Параллельная сеть с ненулевыми пропускными способностями пути 1-5-6-7-4

Если при назначении пропускных способностей для этой же сети установить для связанных дуг $9$ - $10$, $5$ - $6$, $6$ - $7$ пропускную способность величины $4$, а для остальных связанных дуг нулевую пропускную способность, то будет получена классическая сеть, изображенная на рис. 10, у которой $V{G}_{\rho }=VG = 8$.

Рис. 10. Параллельная сеть с VGρ = VG

Для того, чтобы сравнить полученные варианты назначений потоков (рис. 8$–$10) для каждого из путей ${\mu }_i$, $i \in \left\{1,\dots \mathrm{,}p\right\}$ из $s$ в $t$, определим две характеристики $—$ кратность связанных дуг $\delta \mathrm{<mo\; stretchy="false">(</mo>}{\mu }_i\mathrm{<mo\; stretchy="false">)</mo>}$ и пропускную способность по несвязанным дугам $—$ $\tilde{\rho }\left({\mu }_i\right)$ следующим образом:

$\delta \left({\mu }_i\right)=\left|U^s\cap {\mu }_i\right|\tilde{\rho }\left({\mu }_i\right)\text{ = }\min \rho \left(u\right), u\in \left\{{\mu }_i\backslash U^s\right\}$

Необходимо отметить, что в приведенных выше примерах (рис. 8$–$10), «цена» прохождения потока в отношении использования $P\mathrm{<mo\; stretchy="false">(</mo>}{U}^s\mathrm{<mo\; stretchy="false">)</mo>}$ по разным путям различна. Для того, чтобы организовать поток величины $x$ ( $x\le \tilde{\rho }\left({\mu }_i\right)$ ) по пути $1$ - $2$ - $3$ - $4$, потребуется использовать $3\cdot x$ пропускной способности из $P\left(U^s\right)$ $—$ по $x$ на каждую из трех дуг этого пути. Поток величины $x$ по пути $1$ - $5$ - $6$ - $7$ - $4$ потребует уже задействования суммарной пропускной способности величиной $2\cdot x$ из $P\mathrm{<mo\; stretchy="false">(</mo>}{U}^s\mathrm{<mo\; stretchy="false">)</mo>}$. Путь $1$ - $8$ - $9$ - $10$ - $11$ - $4$ является самым выгодным по отношению использования $P\left(U^s\right)$ $—$ прохождение потока величиной $x$ по этому пути требует назначения пропускной способности величины $x$ по единственной связанной дуге в этом пути $9$ - $10$.

Таким образом, поток, проходящий по пути с меньшим числом связанных дуг, т.е. с меньшей кратностью $\delta \left({\mu }_i\right)$, получает меньшую «цену» в отношении использования $P\left(U^s\right)$. На основе этого принципа строится алгоритм поиска максимального потока для параллельных сетей с одним множеством связанных дуг, который описан далее.

3. Алгоритм нахождения максимального потока в параллельной сети с одним множеством связанных дуг

Алгоритм нахождения максимального потока в параллельной сети с одним множеством связанных дуг состоит из следующих шагов.

Шаг 1. Пронумеровать параллельные пути ${\mu }_i$ в неубывающем по $\delta \left({\mu }_i\right)$ порядке. В случае, если $\delta \left({\mu }_i\right)=\delta \left({\mu }_{i+1}\right)$ ($i<p$), доупорядочить так, чтобы $\tilde{\rho }\left({\mu }_i\right) \ge \tilde{\rho }\left({\mu }_{i+1}\right)$.

Шаг. 2. Положить $P_{\text{res}}\left(U^s\right):= P\left(U^s\right)$.

Шаг. 3. Положить, что пропускная способность всех путей $\rho \left({\mu }_i\right):= 0$.

Шаг. 4. Производить перебор путей в порядке возрастания их порядковых номеров и для каждого из путей перейти на шаг 5. По завершении перебора путей перейти на шаг 7.

Шаг. 5. Если $\delta \left({\mu }_i\right)=0$, то $\rho \left({\mu }_i\right) :=\tilde{\rho }\left({\mu }_i\right)$ и перейти на шаг 4; иначе перейти на шаг 6.

Шаг. 6. Вычислить ${\rho }_p:=P_{\text{res}}\left(U^s\right)/\delta \left({\mu }_i\right)$. Если ${\rho }_p\ge \tilde{\rho }\left({\mu }_i\right)$, то $P_{\text{res}}\left(U^s\right):=P_{\text{res}}\left(U^s\right)-\tilde{\rho }\left({\mu }_i\right)\cdot \delta \left({\mu }_i\right)$, присвоить всем связанным дугам пути ${\mu }_i$ пропускную способность, равную $\tilde{\rho }\left({\mu }_i\right)$ и $\rho \left({\mu }_i\right):-\tilde{\rho }\left({\mu }_i\right)$, а также перейти на шаг 4; иначе присвоить всем связанным дугам пути ${\mu }_i$ пропускную способность, равную ${\rho }_p$ и $\rho \left({\mu }_i\right):= {\rho }_p$, установить $P_{\text{res}}\left(U^s\right)=0$ и перейти на шаг 7.

Шаг. 7. Вычислить величину максимального потока, просуммировав $\rho \left({\mu }_i\right)$. Завершить работу алгоритма.

Этот алгоритм имеет полиномиальную вычислительную сложность от размеров сети, так как подсчет количества связанных дуг для каждого из путей осуществим за линейное время, а сортировка путей по кратностям связанных дуг за полиномиальное $—$ c помощью известных алгоритмов сортировки, таких как сортировка бинарным деревом, сортировка слиянием, имеющих квадратичную вычислительную сложность (см. [3]).

Замечание 1.

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

2.Доупорядочение последовательности путей в случае $\delta \left({\mu }_i\right) = \delta \left({\mu }_{i+1}\right)$ по условию $\tilde{\rho }\left({\mu }_i\right) \ge \tilde{\rho }\left({\mu }_{i+1}\right)$ может существенно ускорить выполнение алгоритма, когда суммарной пропускной способности связанных дуг недостаточно, чтобы обеспечить наличие ненулевого потока на каждом из параллельных путей.

Пример 4. Применим вышеописанный алгоритм к сети, изображенной на рис. 11, для которой $P\left(U^s\right)=5$, а пропускные способности дуг из $\left\{U\backslash U^s\right\}$ указаны на рис. 11 рядом с каждой из дуг.

Рис. 11. Параллельная сеть

Обозначим пути из $s$ в $t$ на рис. 11 как $p_1\mathrm{,}\dots \mathrm{,}{p}_5$ в порядке сверху вниз. Шаг 1 алгоритма предполагает вычисление $\delta \left(p_i\right)$ и $\tilde{\rho }\left(p_i\right)$. Для рис. 11 значения $\delta \left(p_i\right)$ путей и значения $\tilde{\rho }\left(p_i\right)$ равны

$\delta \left(p_1\right)=3,\delta \left(p_2\right)=2,\delta \left(p_3\right)=0,\delta \left(p_4\right)=2,\delta \left(p_5\right)=0,$

$\delta \left(p_1\right)=0,\delta \left(p_2\right)=2,\delta \left(p_3\right)=1,\delta \left(p_4\right)=1,\delta \left(p_5\right)=1.$

Тогда по завершении шага 1 алгоритма порядок выбора путей будет следующим:

${\mu }_1=p_3\mathrm{,}{\mu }_2=p_5\mathrm{,}{\mu }_3=p_2\mathrm{,}{\mu }_4=p_4\mathrm{,}{\mu }_5=p_1\mathrm{,}$

при этом пути $p_3$, $p_5$ и $p_2$, $p_4$ попарно равны по $\delta \left({\mu }_i\right)$, поэтому были доупорядочены по $\tilde{\rho }\left({\mu }_i\right)$.

На шаге 2 $P_{\text{res}}\left(U^s\right):=5$. На шаге 3 пропускные способности всех путей $\rho \left({\mu }_1\right)\dots \mathrm{,}\rho \left({\mu }_5\right)$ обнуляются. В цикле, начинающемся на шаге 4, пути ${\mu }_1$ и ${\mu }_2$ будут получать пропускные способности величиной $1$ на шаге 5, поскольку не имеют в своем составе связанных дуг. Для пути ${\mu }_3$ на шаге 5 будет определена пропускная способность величиной в $\tilde{\rho }\left({\mu }_3\right)=2$, поскольку ${\rho }_p\ge \tilde{\rho }\left({\mu }_3\right)$, а $P_{\text{res}}\left(U^s\right)$ на данном шаге станет равным $1$.

Для пути ${\mu }_4$ на шаге 5 будет израсходована вся остаточная пропускная способность $P_{\text{res}}\left(U^s\right)$, за счет которой связанным дугам этого пути будет назначена пропускная способность ${\rho }_p\mathrm{<mo>=</mo>0,5}$, после чего произойдет переход на шаг 7 с подсчетом величины максимального потока и завершение работы алгоритма, следовательно путь ${\mu }_5$ не будет обработан в цикле и назначенная для него на шаге 3 пропускная способность останется равной $0$. Итак, по результатам работы алгоритма максимальный поток для параллельной сети со связанными дугами с рис. 11 будет равен $\mathrm{4,5}$.

Заключение.

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

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