Задача о наибольшем кратном потоке в делимой сети и ее частные случаи

В статье рассматривается задача о наибольшем кратном потоке в сети произвольной натуральной кратности $k$. Определяется три типа дуг в сети: обычная дуга, кратная дуга, мультидуга. Каждая кратная и мультидуга представляет собой объединение $k$ связанных дуг, согласованных между собой. Задаются правила построения сети.
Вводится понятие делимой сети и ряд связанных определений. Отмечается важная особенность делимых сетей – возможность разделить их на $k$ частей, согласованных на связанных дугах кратных и мультидуг, таким образом, что каждая часть является обычной транспортной сетью.
Основным результатом статьи является выделение следующих подклассов задачи о наибольшем кратном потоке в делимой сети.

• Делимая сеть с ограничениями на мультидуги. Если в $k-1$ части делимой сети имеется только одна вершина, являющаяся концом мультидуги, то задача о наибольшем потоке полиномиально разрешима.
  
• Делимая сеть со слабыми ограничениями на мультидуги. Если в $s$ частях делимой сети ($1\leq s<k-1$) имеется только одна вершина, являющаяся концом мультидуги, а в остальных частях таких вершин несколько, то размерность задачи о наибольшем кратном потоке может быть понижена до $k-s$.
  
• Делимая сеть параллельной структуры. Пусть компонента делимой сети, состоящая из всех кратных дуг, может быть разделена на субкомпоненты, содержащие ровно по одной вершине-началу мультидуги. Пусть при этом каждая пара субкомпонент пересекается только в источнике сети $x_0$. Если $k=2$, то задача о максимальном кратном потоке разрешима за полиномиальное время. Если $k\geq3$, то задача $NP$-полна.

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