Журнал вычислительной математики и математической физики, 2021, T. 61, № 8, стр. 1390-1400

ВВЕДЕНИЕ

Работа основана на результатах из [1] и является дальнейшим развитием построений в [2]. Классическая задача о максимальном потоке в ориентированной сети была определена и изучена в работе [1]. Она является обобщением модели Т.Е. Харриса и Ф.С. Росса [3]. Основной результат о максимальном потоке и минимальном разрезе был получен Л. Фордом и Д. Фалкерсоном [4]. Ими же был предложен базовый алгоритм процесса расстановки пометок для определения максимального потока в сети, одновременно определяющего соответствующий минимальный разрез [1].

В [5] изучалась максимальная величина потока как функция пропускных способностей дуг, которую можно использовать для построения метода последовательного улучшения решения в поставленной ниже минимаксной задаче подавления сети связи по аналогии с методом покоординатного спуска. В [6] изучалась задача синтеза многополюсной сети при заданной нижней границе потоковой функции сети, показывающей величины максимальных потоков между всеми парами узлов в сети, по критерию взвешенной стоимости пропускной способности дуг. В [7] изучалась задача построения максимального динамического потока, который учитывает, помимо пропускных способностей, еще и время прохождения соответствующей дуги. Предложенный метод ее решения был позднее модифицирован (см. [1]) для решения задачи построения максимального потока минимальной стоимости из источников в стоки, которая обобщает классическую транспортную задачу на произвольные сети.

Приложение классической задачи о максимальном потоке может состоять в производной задачи минимизации максимального потока в сети связи за счет уменьшения пропускной способности дуг противником в линейной постановке, поставленной и изученной в настоящей работе. Это приводит в общем случае к задаче минимизации пропускной способности минимального разреза, которая сводится к последовательности задач математического программирования. Поскольку множество разрезов можно отождествить с множеством всех подмножеств множества узлов сети, то полученная задача эквивалентна дискретной задаче на булевой решетке и может быть решена методами субмодулярного программирования, развитыми в работах Р.В. Хачатурова [8].

1. ДВУХПОЛЮСНАЯ МОДЕЛЬ ПОДАВЛЕНИЯ СЕТИ СВЯЗИ

По аналогии с моделью “нападение–оборона” на сети (см. [2]), рассмотрим задачу подавления нападением системы связи обороны на ориентированном графе $G$, состоящем из множества вершин $N = \left\{ i \right\}$ и множества ориентированных ребер $L = \left\{ {(i,j)} \right\}$ без контуров с одним источником $s$ и стоком $t$, далее этот граф будем называть орграфом $G$. Стратегия нападения $u$ принадлежит множеству

Напомним, что сечением называется такое разбиение множества вершин $N = S \cup T$, $s \in S$, $t \in T$, что любой путь из $s$ в $t$ имеет дугу, ведущую из $S$ в $T$. Обозначим множество таких дуг через $L(S,T)$. Пропускной способностью дуги $(i,j)$, следуя [9], будем считать величину

где ${{c}_{{ij}}}$ – исходная пропускная способность, ${{u}_{{ij}}}$ – количество однородного бесконечно-делимого ресурса подавления связи, назначенного нападением на дугу $(i,j)$, ${{a}_{{ij}}}$ – его эффективность. Пропускной способностью разреза назовем величину

Минимальным разрезом называется разрез минимальной пропускной способности. Согласно утверждению теоремы Форда–Фалкерсона (см. [1, c. 24]) максимальный поток в сети из источника $s$ в сток $t$ равен пропускной способности минимального разреза

что можно взять за определение величины ${v}$ в дальнейших построениях.

Рассмотрим минимаксную задачу минимизации максимального потока (1.4) на множестве (1.1). В силу представления (1.4) для максимального потока она сводится к нахождению наименьшей из величин

С учетом (1.2) можно считать, что выполняются дополнительные ограничения Тогда задача (1.5), (1.6) становится линейной и может быть легко решена алгоритмически на основании условий оптимальности, полученных в непрерывном случае в работе [10, c. 167]. Тогда легко может быть определена выпуклая убывающая кусочно-линейная функция ${{{v}}_{S}} = {{{v}}_{S}}(U)$.

Предположим, что $L(S,N{{\backslash }}S) = \left\{ {({{i}_{k}},{{j}_{k}}){\kern 1pt} \left| {{\kern 1pt} k = 1,\; \ldots ,\;n = {{n}_{S}}} \right.} \right\}$. Введем обозначения

Предположим, не уменьшая общности, что Приведем для полноты изложения соответствующий алгоритм: до тех пор, пока $U > 0$. Все неопределенные в алгоритме ${{u}_{k}}$ полагаются равными нулю.

Предположим, что имеет место неравенство

где положено по определению Тогда в результате работы алгоритма получим решение

Функция ${{{v}}_{S}} = {{{v}}_{S}}(U)$ при этом равна

где Пусть $N{\text{'}} = N{{\backslash }}(s \cup t)$, тогда ${{w}_{{S'}}} = {{{v}}_{{S' \cup s}}}$, $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$, и функция ${{w}_{{S'}}}$ определена на булевой решетке, отождествляемой с множеством всех подмножеств $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$, и для определения ее минимума можно воспользоваться методами субмодулярного программирования из [8]. Для этого достаточно условия субмодулярности функции ${{w}_{{S{\text{'}}}}}$, $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$, которое состоит в выполнении неравенства Мы докажем более слабое утверждение о субмодулярности функции ${{w}_{{S'}}}$, $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$, в случае ${{a}_{{ij}}} \equiv a$, которое позволит нам сконструировать нетривиальные нижние оценки в методе последовательных расчетов из [8]. Этот метод является модификацией метода максимизации субмодулярных функций из [11].

Теорема 1. Предположим, что ${{a}_{{ij}}} \equiv a$. Тогда функция ${{w}_{{S'}}} = {{{v}}_{{S' \cup s}}}$, $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$, является субмодулярной.

Пусть ${{\bar {w}}_{{S'}}} = {{{\bar {v}}}_{{S' \cup s}}}$, $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$, где

Доказательство основано на следующих леммах.

Лемма 1. Функция ${{\bar {w}}_{{S'}}}$, $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$, является субмодулярной.

Доказательство. Равенство (1.11) для функции ${{\bar {w}}_{{S'}}} = {{{\bar {v}}}_{{S' \cup s}}}$, $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$, имеет вид

и справедливо в силу того, что левая часть (1.13) содержит в силу (1.12), кроме всех слагаемых правой части, еще

Лемма 2. Предположим, что ${{a}_{{ij}}} \equiv a$. Тогда справедлива формула

Доказательство. Равенство (1.14) следует из (1.9) в силу (1.10), которое в условиях леммы будет иметь вид

Последнее равенство здесь справедливо по определению величин ${{b}_{k}}$, в силу которого справедливо равенство

Следствие 1. Из (1.14) немедленно следует, что в условиях леммы задача минимизации максимального потока (1.4) на множестве (1.1) имеет тривиальное решение в виде минимального сечения для исходной сети, которое можно найти при помощи алгоритма Форда–Фалкерсона из [1].

Пример 1. Рассмотрим орграф $G$ из [2], состоящий из множества вершин $N = \left\{ {1,\;2,\;3,\;4,\;5} \right\}$, $s = 1$, $t = 5$ и множества ориентированных ребер $L = \left\{ {(1,2),(1,3),(2,4),(3,4),(2,5),(3,5),(4,5)} \right\}$, представленный на фиг. 1. Предположим, что ${{c}_{{ij}}} \equiv c = 1$, ${{a}_{{ij}}} \equiv a = 1$, $U = 2$. Требуется решить минимаксную задачу подавления и определить минимальное значение максимального потока.

Решение. Используя алгоритм расстановки пометок Форда–Фалкерсона из [1], найдем максимальный поток ${v} = 2$ в исходной неподавленной сети и соответствующий минимальный разрез $S{\kern 1pt} * = s$, $T{\kern 1pt} * = S{\kern 1pt} *{\kern 1pt} \backslash {\kern 1pt} s$, которому соответствует множество дуг $L(S{\kern 1pt} *,T{\kern 1pt} *) = \left\{ {(1,2),(1,3)} \right\}$. Минимальное значение максимального потока в подавленной сети по формуле (1.14) будет равно нулю. Решение (1.8) минимаксной задачи имеет вид

Доказательство теоремы 1. Из (1.13) получим в силу (1.15), что справедливо неравенство

Откуда следует, что

В этом можно убедиться, анализируя различные варианты упорядочивания величин ${{\bar {w}}_{A}}$, ${{\bar {w}}_{B}}$, ${{\bar {w}}_{{A \cup B}}}$, ${{\bar {w}}_{{A \cap B}}}$, входящих в (1.13) и рассматривая соответствующие диапазоны $U$, на которые разбиваются значения $aU$. В силу (1.14) это эквивалентно неравенству

что и доказывает субмодулярность функции ${{w}_{{S'}}} = {{{v}}_{{S' \cup s}}}$, $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$.

Контрпример субмодулярности в основном случае.  Рассмотрим единичный квадрат на плоскости и пронумеруем его вершины следующим образом: . Множество дуг совпадает с ребрами с направлением от меньшего номера к большему: $L = \left\{ {(0,1),(0,2),(1,3),(2,3)} \right\}$. Положим ${{c}_{{ij}}} \equiv {{a}_{{ij}}} > 0$ и $U = 1$. Рассмотрим неравенство, определяющее субмодулярность для $S{\text{'}} = \left\{ 1 \right\},\left\{ 2 \right\},\left\{ {1,\;2} \right\}$:

Отсюда после преобразования получим что неверно при любых достаточно малых ${{a}_{{01}}},{{a}_{{02}}} > 0$.

Следствие 2. Из доказанной теоремы в силу результатов [8] следует, что для любых $W,{{W}_{1}} \subset W \subset {{W}_{2}},$ справедлива нижняя оценка ${{\underline {v} }_{W}} \geqslant \max ({{\underline p }_{1}},{{\underline p }_{2}})$, где

а ${{x}_{ - }} = \min (x,0)$ – нижняя срезка величины $x$.

В случае, когда условие ${{a}_{{ij}}} \equiv a$ не выполняется, можно воспользоваться верхней оценкой ${{\bar {{\rm M}}}_{S}}(U)$ функции ${{{\rm M}}_{S}}(U)$, построенной следующим образом. Для любого подмножества дуг $L{\text{'}} \subseteq L$ определим функцию ${{{\rm M}}_{{L'}}}(U)$ аналогично функции ${{{\rm M}}_{S}}(U) = {{{\rm M}}_{{L(S,N\backslash S)}}}(U)$ в (1.10).

Лемма 3. Функция ${{{\rm M}}_{S}}(U) = {{{\rm M}}_{{L(S,N\backslash S)}}}(U)$ является монотонно неубывающей по включению $L{\text{'}} \supseteq L(S,N{{\backslash }}S)$, т.е.

Доказательство. Поскольку (1.10), которое принято за определение ${{{\rm M}}_{{L'}}}(U)$, является значением функции

то ${{{\rm M}}_{S}}(U) = {{{\rm M}}_{{L(S,N\backslash S)}}}(U)$ можно определить равенством откуда и следует требуемое неравенство.

Для любых $W,{{W}_{1}} \subset W \subset {{W}_{2}},$ в (1.16) положим

Тогда в качестве верхней оценки ${{\bar {{\rm M}}}_{{{{W}_{1}},{{W}_{2}}}}}(U)$ функции ${{{\rm M}}_{W}}(U)$ можно взять Соответствующая нижняя оценка ${{\underline {v} }_{W}}$ функции ${{{v}}_{W}}$ будет иметь вид или с учетом неотрицательности функции ${{{v}}_{w}}$.

В результате оценки (1.16) остаются справедливыми в общем случае, когда условие ${{a}_{{ij}}} \equiv a$ не выполняется, если заменить функции ${{{v}}_{w}}$ их нижними оценками (1.17), и могут быть использованы в методе ветвей и границ для решения задачи минимизации функции ${{w}_{{S'}}} = {{{v}}_{{S' \cup s}}}$ на булевой решетке $S{\kern 1pt} {\text{'}} \subseteq N{\kern 1pt} {\text{'}}$ в общем случае. Характерно, что построенные оценки зависят от ограничивающих $w$ множеств ${{W}_{1}} \subset {{W}_{2}}$ и будут улучшаться при сближении ${{W}_{1}}$, ${{W}_{2}}$ в процессе работы метода ветвей и границ.

Для проверки практической сходимости метода ветвей и границ в основном случае была проведена серия численных экспериментов. Максимальное количество дуг во всех примерах было равно количеству вершин без единицы $\left| L \right| = \left| N \right| - 1 = 15$. Параметры для каждой дуги в каждом примере устанавливаются случайным образом в пределах $1 \leqslant {{a}_{{ij}}} \leqslant 2$, $1 \leqslant {{c}_{{ij}}} \leqslant 3$, $(i,j) \in L$. Во всех примерах коэффициенты генерировались исходя из равномерного распределения в указанных диапазонах. Объем выборки составлял 500 задач (примеров). Рассчитывалась доля финальных вершин поискового орграфа, использованных комбинированным алгоритмом (в процентах), показывающая, насколько алгоритм сокращает полный перебор всех вариантов, количество которых для данной задачи равно мощности множества всех подмножеств множества $N$, т.е. ${{2}^{{\left| N \right|}}}$. Результаты показали, что доля финальных вершин поискового ортграфа, использованных алгоритмом (в среднем по выборке), составляет 59.22%. В некоторых экспериментах доля финальных вершин не превосходила 1%. Но были и такие случаи, в которых происходил полный перебор. На фиг. 2 представлен график процента сокращения полного перебора всех вариантов в зависимости от количества дуг (вершин) в основном случае.

2. МНОГОПОЛЮСНАЯ МОДЕЛЬ ПОДАВЛЕНИЯ СЕТИ СВЯЗИ

Более общей является задача минимизации взвешенной суммы максимальных потоков между произвольными узлами связи $i,j \in N$

Обычно полагают по определению ${{{v}}_{{ii}}}(u) = \infty $, $i \in N$. Симметрическая потоковая функция удовлетворяет неравенству ([3, с. 248]) Здесь $i = {{l}_{0}},\;{{l}_{1}}, \ldots ,\;{{l}_{k}} = j$ – любой набор узлов, связывающий вершины $i$, $j$ в исходной сети.

Поскольку основные результаты относительно потоковой функции ${{{v}}_{{ij}}}(u)$, приведенные в [1], получены для неориентированных сетей, то в этом разделе будет рассматриваться неориентированная сеть. Для того чтобы свести задачу о максимальном потоке на неориентированной сети к ориентированной, достаточно заменить каждое неориентированное ребро $[i,j] \in L$ с пропускной способностью ${{c}_{{ij}}}$ парой взаимно противоположных дуг $(i,j)$, $(j,i)$ с той же пропускной способностью каждая [1].

Рассмотрим задачу минимизации взвешенной суммы значений потоковой функции

на множестве (1.1). Здесь ${{\alpha }_{{ij}}} \geqslant 0$, $i > j$, – веса, отражающие ценность соответствующих потоков в иерархии сети.

В силу представления (3.1) для максимальных потоков она сводится к нахождению наименьшей из величин

Здесь $\bar {S} = ({{S}_{{ij}}},\;i > j)$.

С учетом (1.2) можно считать, что выполняются дополнительные ограничения (1.6). Тогда задача (3.4), (1.6) становится линейной и может быть записана в виде

Задача (3.5) тривиальна и может быть легко решена при помощи алгоритма, приведенного в разд. 1. Для этого следует подставить в (3.5) выражения (1.3)

и привести подобные; это дает где ${{{\rm A}}_{{ij}}} = {{{\rm A}}_{{ij}}}(\bar {S}) \geqslant 0$, $[i,j] \in L$, – соответствующие коэффициенты.

За основу схемы ветвления метода ветвей и границ возьмем метод Гомори-Ху [1] построения эквивалентного связанного дерева разрезов при фиксированном $u \in Y$, у которого по определению множество вершин $N$ то же, что и у исходной сети, а множество ребер представляет подмножество $L{\kern 1pt} ' \subset L$ из $\left| N \right| - 1$ ребер. При этом ребром связываются два узла $i,j \in N$, если они лежат по разные стороны ровно одного из построенных в ходе работы алгоритма $\left| N \right| - 1$ разрезов исходной сети, а пропускная способность ребра равна максимальному потоку ${{{v}}_{{ij}}}(u)$, определенному в (1.3). Там же показано, что максимальный поток между любыми двумя узлами $i,j \in N$, если они не связаны ребром в дереве разрезов, равен минимуму потоков в единственном пути $i = {{l}_{0}},\;{{l}_{1}},\; \ldots ,\;{{l}_{k}} = j$, связывающем $i$, $j$

Отсюда следует, что потоковая функция принимает не более $\left| N \right| - 1$ значений.

Опишем это построение, следуя (см. [1, с. 250]), поскольку оно будет играть ключевую роль в предлагаемой схеме ветвления. Произвольным образом выберем два узла $i$, $j$ и решим задачу о максимальном потоке между ними. При этом решении будет выделен минимальный разрез $(X,\bar {X})$ между ними, который символически изображается двумя макроузлами $X$, $\bar {X}$, соединенными ребром пропускной способности ${{{v}}_{{ij}}}(u)$.

Этот процесс продолжаем дальше. На каждом этапе построения из диаграммы дерева на этом этапе выбирается некоторое множество $Z$, состоящее более чем из одного узла. В этом дереве имеется некоторое количество дуг, прикрепленных к $Z$. Все те множества, которые можно достичь через какую-нибудь из этих дуг, для следующей задачи о максимальном потоке сожмем в единственный макроузел. При этом складываются пропускные потоки ребер, сжимаемых в одно макроребро. Проделаем это для каждого ребра, прикрепленного к $Z$. В полученной сети $(Z{\kern 1pt} {\text{'}},L{\text{'}})$ решим задачу о максимальном потоке между какими-нибудь двумя узлами $l,k \in Z$. При этом решении будет выделен минимальный разрез $(V,\bar {V})$ между ними, который символически изображается двумя макроузлами $V$, $\bar {V}$, соединенными ребром пропускной способности ${{{v}}_{{kl}}}(u)$. Остальные макроузлы предыдущей сети прикрепляются к $V$, если они лежат в части разреза, содержащей $V$и к $\bar {V}$в противном случае. Этот процесс повторяется до тех пор, пока каждый макроузел не будет состоять из одного узла. Возвращаясь к исходной сети, получаем некоторый набор разрезов $\bar {S} = ({{S}_{{ij}}},\;i > j)$, фигурирующий в (3.5).

Поскольку при некотором $u \in Y$ каждый разрез предположительно может быть максимальным, то предлагаемая процедура ветвления повторяет описанный процесс с той разницей, что на каждом шаге выбирается не максимальный, а произвольный разрез соответствующего макроузла. Кроме того, деление каждого макроузла можно начать с той точки, которая выбиралась на предыдущем шаге деления, добавляя к ней каждый раз только одну новую точку. Тогда на каждом шаге ветвления будет построено некоторое поддерево $L{\text{'}} \subset L$ ребер $[i,j]$, неполных наборов разрезов $\bar {S}{\kern 1pt} {\text{'}} = ({{S}_{{ij}}},\;[i,j] \in L{\text{'}})$ и максимальных потоков, определяемых в результате решения соответствующих задач (3.5) для уже построенного поддерева $L{\text{'}}$. Получим соответствующие нижние оценки для всех достижимых из $\bar {S}{\text{'}}$ полных наборов $\bar {S}$. При этом для непосредственно не связанных узлов $i$, $j$ в поддереве $L{\text{'}} \subset L$ соответствующее слагаемое в (3.5) заменяется нулем, либо более точно – на выражение

в соответствии со свойством (3.2) потоковой функции. Здесь $i = {{l}_{0}},\;{{l}_{1}}, \ldots ,\;{{l}_{k}} = j$ есть единственный путь, связывающий узлы i,  j  в построенном поддереве $L{\text{'}} \subset L$. Правда, при этом полученная задача (3.5), (3.9) является $NP$-трудной и для ее решения в свою очередь придется построить, вообще говоря, также экспоненциальный метод решения. Этот метод основан на упорядочивании всех величин ${{с}_{{L({{S}_{{ij}}},N\backslash {{S}_{{ij}}})}}}(u)$ для узлов $i$, $j$, связанных непосредственно ребром $[i,j]$ в построенном поддереве $L{\text{'}} \subset L$ меньшей размерности, которое мы обозначаем той же буквой, что и множество его ребер, имея в виду, что множество узлов восстанавливается по ним однозначно.

3. СЛУЧАЙ ПОСТОЯННЫХ КОЭФФИЦИЕНТОВ ЭФФЕКТИВНОСТИ ПОДАВЛЕНИЯ

В случае ${{a}_{{ij}}} \equiv a$ можно, используя следствие 1, сконструировать приближенный алгоритм последовательного распределения ресурса типа (1.7) для решения многополюсной задачи подавления сети связи. Вначале, используя алгоритм Гомори-Ху, строится произвольное дерево разрезов для исходной сети, которое позволяет вычислить начальную потоковую функцию для всех пар $i,j \in N$при помощи (3.8). Затем в порядке, определяемом весами ${{\alpha }_{{ij}}} \geqslant 0$, $i > j$, подавляется разрез за разрезом дерева разрезов, пока не закончится однородный ресурс. Это напоминает метод “северо-западного угла” в [12, с. 222], нахождения опорного плана транспортной задачи. Отсюда необходимый объем для подавления всей сети не превышает величины

где $\bar {S}$ – набор из $\left| N \right| - 1$ разрезов дерева разрезов. На самом деле необходимое количество ресурса меньше этой величины за счет синергетического эффекта, состоящего в том, что при подавлении очередного разреза некоторые его ребра, входящие в предыдущие разрезы, были подавлены ранее.

Пример 2. Построить какой-нибудь набор $\bar {S}$ сечений Гомори-Ху для исходной многополюсной сети в примере 1, считая ее неориентированной, найти решение полученной вспомогательной задачи (3.5) методом “северо-западного сечения” и при помощи алгоритма (1.8).

Решение. На фиг. 3 приведены полученные разрезы для примера 1. На фиг. 4 представлено само дерево разрезов для примера 1, а на фиг. 5 – дерево разрезов после полного подавления разреза $(\left\{ 1 \right\},\;\left\{ {2,\;3,\;4,\;5} \right\})$, соответствующего паре узлов $(1,\;5)$, пропускной способностью ${{с}_{{L({{S}_{{15}}},N\backslash {{S}_{{15}}})}}} = 2$ и имеющимся ресурсом $U = 2$. Это соответствует решению

Из сравнений фиг. 4, 5 можно увидеть синергетический эффект, состоящий в том, что после подавления сечения, соответствующего паре узлов $(1,\;5)$, косвенно снизилась пропускная способность сечений, соответствующих парам узлов $(2,\;5)$ и $(3,\;5)$.

В этом примере вспомогательная задача (3.5) для построенного набора $\bar {S}$ разрезов после выбора минимальных разрезов в формуле (3.8) для непосредственно не связанных узлов и приведения подобных имеет вид

Она в данном случае имеет то же решение, полученное с помощью алгоритма (1.8), что и найденное методом “северо-западного угла”, которое в свою очередь совпало с решением двухполюсной задачи в примере 1.

ЗАКЛЮЧЕНИЕ

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

Более общей является задача минимизации взвешенной суммы максимальных потоков между произвольными узлами связи в многополюсной сети, изученной во второй части работы. За основу схемы ветвления метода ветвей и границ принят метод Гомори-Ху построения эквивалентного связанного дерева разрезов. Поскольку основные результаты относительно потоковой функции получены для неориентированных сетей, то во второй части изучалась неориентированная сеть. Для того чтобы свести задачу о максимальном потоке на неориентированной сети к ориентированной, достаточно, как известно, заменить каждое неориентированное ребро парой взаимно противоположных дуг с той же пропускной способностью каждая. Получены соответствующие нижние оценки, необходимые для реализации метода ветвей и границ. Правда, при этом полученная задача становится нелинейной.

В случае постоянных коэффициентов эффективности подавления предложен приближенный алгоритм последовательного распределения ресурса для решения многополюсной задачи подавления сети связи. Вначале, используя алгоритм Гомори-Ху, строится какое-нибудь дерево разрезов для исходной сети, которое позволяет вычислить начальную потоковую функцию для всех пар узлов. Затем в порядке, определяемом весами, подавляется разрез за разрезом дерево разрезов, пока не кончится однородный ресурс. Это напоминает метод “северо-западного угла” нахождения опорного плана транспортной задачи. Приводится пример его работы.

Авторы выражают признательность И.А. Лесику за проведение численных экспериментов и анализ результатов.