Журнал вычислительной математики и математической физики, 2023, T. 63, № 3, стр. 517-530

1. ВВЕДЕНИЕ

Область теоретических и прикладных задач о стабильных договорах явилась предметом интенсивного изучения в математической экономике, теории игр и комбинаторной оптимизации, и ей посвящены многочисленные работы нескольких последних десятилетий. Отправной точкой многих исследований послужила классическая работа Гейла и Шепли [1] о стабильных марьяжах (SM).

Согласно одной из распространенных формулировок этой задачи имеется двудольный граф $G = (V,E)$, и для каждой вершины $v$ задан (строгий) линейный порядок ${{ < }_{v}}$ на инцидентных ребрах. (В [1] рассматриваются полные двудольные графы, но это не существенно. В популярной интерпретации ребра в $G$ представляют возможные союзы персон разного пола, а порядок ${{ < }_{v}}$ – предпочтения персоны $v$: если для ребер $e = vu$ и $e{\kern 1pt} ' = vw$ выполняется $e{{ < }_{v}}e{\kern 1pt} '$, то $v$ предпочитает союз с $u$ союзу с $w$.) В задаче требуется найти паросочетание (matching) $M \subseteq E$, являющееся стабильным относительно всех этих порядков. Это означает, что для любого ребра $e$ из $E - M$ есть ребро $e{\kern 1pt} ' \in M$ такое, что $e$ и $e{\kern 1pt} '$ имеют общую вершину $v$, и при этом выполняется $e{\kern 1pt} '{{ < }_{v}}e$. Было показано, что стабильное паросочетание в двудольном графе всегда существует, и оно может быть построено комбинаторным алгоритмом с линейной верхней оценкой числа действий (временнóй сложностью) $O(n + m)$, где $n$ и $m$ – число вершин и ребер в $G$ соответственно.

В последующих работах многих авторов были исследованы различные обобщения задачи SM. Укажем два направления обобщений, связанные с графами (оставляя в стороне постановки, в которых в договорах могут участвовать более двух агентов, или предпочтения агентов задаются другими способами). Одно из них – переход от двудольного к произвольному графу $G$. Соответствующий аналог задачи SM, известный под названием задачи о стабильном размещении пар соседей по комнатам (stable roommates problem), был исследован Ирвингом в работе [2], где был дан алгоритм линейной сложности для построения стабильного паросочетания в $G$ либо доказательства его несуществования. Важные дополнительные структурные и алгоритмические результаты были представлены в [3].

Другой тип обобщений, который более важен для нас, оставляет граф $G = (V,E)$ двудольным, но добавляет числовые параметры. Среди задач этого типа весьма общей выглядит задача о стабильном распределении (stable allocation problem – SA), введенная Бейу и Балински [4]. Здесь распределением считается назначение каждому ребру $e \in E$ величины $x(e) \geqslant 0$, не превышающей предписанной пропускной способности $c(e)$, и при этом сумма назначений по ребрам, инцидентным вершине $v \in V$, не должна превышать предписанной “квоты” $q(v)$. (В случае задачи SM, все $c(e)$ и $q(v)$ равны единице, а $x(e)$ принимает значение 0 или 1. В общем случае задачи SA, число $x(e)$ на ребре $e = uv$ может пониматься, например, как размер участия “работника” $u$ в “работе” $v$.) В [4] доказывается разрешимость SA при любых неотрицательных вещественных $c,\;q$ (давая целочисленное $x$ при целочисленных $c,\;q$) и предложен сильно полиномиальный алгоритм решения, т.е. имеющий временнýю сложность, зависящую только от размеров графа и выражающуюся полиномом от $n$ и $m$. Дин и Мунши [5] описали улучшенную версию алгоритма из [4], которая строит решение за время $O(nm)$; более того, они показали, что можно добиться даже временнóй оценки $O(m{\kern 1pt} \log n)$, если применить для ряда процедур мощные структуры данных, такие как динамические и самонастраивающиеся деревья Слейтора и Таржана [6], [7]. (Это дает теоретическое ускорение, но алгоритм такого рода громоздкий и едва ли может быть применен для практических целей.)

В свою очередь задача SA может быть представлена как частный случай задачи о стабильном потоке (SF). Последняя была сформулирована Флейнером в 2010-е годы в работе [8] (как обобщение задачи Островского [9] для ациклических сетей с единичными пропускными способностями ребер). В ней задана сеть, состоящая из ориентированного графа $G = (V,E)$ с пропускными способностями $c(e) \geqslant 0$ ребер $e \in E$ и двумя выделенными вершинами (“терминалами”) $s$ и $t$. Для каждой внутренней вершины $v \in V - \{ s,t\} $ заданы линейный порядок на входящих ребрах и линейный порядок на выходящих ребрах. (Допустимый) поток – это неотрицательная вещественная функция $f$ на ребрах, удовлетворяющая верхним ограничениям по пропускным способностям и имеющая нулевые эксцессы для всех внутренних вершин, где под эксцессом в вершине ${v}$ понимается разность ${\text{e}}{{{\text{x}}}_{f}}(v)$ между общим потоком по входящим ребрам и общим потоком по выходящим ребрам в $v$. (Внутреннюю вершину можно интерпретировать как “игрока”, “торговца” или “агента”, который, получая некоторый объем однородного продукта по входящим ребрам, посылает его далее по выходящим ребрам, руководствуясь своей функцией полезности, зависящей от указанных порядков на ребрах.) Поток считается стабильным, если он не допускает локальных улучшений, использующих “ненасыщенные” пути; точное определение будет дано в разд. 2.

Между задачами SA и SF есть тесная связь. Задача SA с двудольным графом $G = ({{V}_{1}} \sqcup {{V}_{2}},{\kern 1pt} E)$ сводится к SF с графом, получаемым из $G$ (с ребрами, ориентированными от ${{V}_{1}}$ к ${{V}_{2}}$) путем добавления терминалов $s$ и $t$, ребер $(s,u)$ с пропускными способностями $q(u)$ для вершин $u$ из доли ${{V}_{1}}$, и ребер $(v,t)$ с пропускными способностями $q(v)$ для вершин $v$ из доли ${{V}_{2}}$.

С другой стороны, Флейнер [8] показал, что задача SF с графом $G = (V,E)$ может быть сведена к задаче SA с графом, получаемым расщеплением вершин в $G$ и добавлением $O({\kern 1pt} {\text{|}}V{\kern 1pt} {\text{|}}{\kern 1pt} )$ новых ребер. В результате было установлено существование стабильного потока для любой сети (и целочисленного стабильного потока при целочисленном $c$), и возможность построения такого потока при помощи алгоритмов для SA, получая временнýю сложность того же порядка.

Впоследствии появились прямые алгоритмы нахождения стабильного потока. Недавно Чех и Матушке [10] предложили прямой алгоритм для сети с одним источником и одним стоком, который имеет сложность $O(nm)$ и основан на комбинации идей метода увеличивающих путей Форда и Фалкерсона для задачи о максимальном потоке и метода “отсроченных принятий” (deferred aceptance), восходящего к Гейлу и Шепли [1].

В настоящей работе предлагается альтернативный алгоритм построения стабильного потока в сети $N = (G,S,T,c)$ с произвольными множествами источников $S$ и стоков $T$ при условии отсутствия ребер, входящих в источники или выходящих из стоков. Алгоритм прямой и чисто комбинаторный (не апеллирует к задаче SA и не использует сложных структур данных), он основан на методе предпотоков. Напомним, что предпотоком в сети называется неотрицательная функция на ребрах, ограниченная пропускными способностями и имеющая неотрицательные эксцессы во всех внутренних вершинах. (Это понятие было введено в [11] и использовалось в алгоритме нахождения максимального потока в сети.) Заметим, что предпотоки уже применялись ранее в работе [12] для построения стабильного потока в сети с целочисленными пропускными способностями за псевдополиномиальное время (линейно зависящее от суммы пропускных способностей ребер).

Алгоритм имеет базовую и модифицированную (ускоренную) версии. Обе начинаются с построения некоторого стабильного предпотока, и на каждой последующей итерации текущий стабильный предпоток перестраивается с целью избавления от положительных эксцессов во внутренних вершинах. Как только эксцессы всех внутренних вершин обнулятся, будет построен искомый стабильный поток (причем целочисленный при целочисленном $c$). Базовый алгоритм конечен при любых неотрицательных вещественных пропускных способностях $c$. Модифицированный алгоритм сильно полиномиальный; он использует дополнительные преобразования предпотоков и строит стабильный поток с временнóй сложностью $O(nm)$ (подобно алгоритму в [10]).

Мы затем рассматриваем более общую задачу для сети $N = (G,S,T,c)$, в которой для каждой внутренней вершины $v$ заданы два параметра $\beta (v) \geqslant 0$ и $\gamma (v) \geqslant 0$ и требуется найти стабильный “квазипоток” $f$ с ограничениями вида $ - \beta (v) \leqslant {\text{e}}{{{\text{x}}}_{f}}(v) \leqslant \gamma (v)$. (Это превращается в стабильный поток при $\beta ,\gamma = 0$.) Показывается, что такой “квазипоток” существует и также может быть найден за время $O(nm)$. (В приложениях число $\gamma (v)$ можно понимать как разрешение “агенту” $v$ распоряжаться по своему усмотрению частью полученного продукта в размере, не превышающем $\gamma (v)$, а число $\beta (v)$ – привлекать “со стороны” дополнительный продукт в размере не более $\beta (v)$.)

Данная статья организована следующим образом. В разд. 2 приводятся основные определения и точные формулировки задач SF и SA. В разд. 3 излагается базовый алгоритм нахождения стабильного потока в сети методом предпотоков и показывается его конечная сходимость (предложение 1). Модифицированная версия алгоритма, имеющая временнýю сложность $O(nm)$, описывается в разд. 4. Раздел 5 содержит обобщения полученных результатов на предпотоки и квазипотоки с ограниченными эксцессами (предложения 3 и 4). В заключительном разд. 6 обсуждаются три дополнительных свойства: 1) максимум величин (т.е. суммарных эксцессов в стоках) для стабильных предпотоков достигается на стабильном потоке; 2) стабильные потоки в фиксированной сети имеют одинаковые величины; и 3) стабильные потоки образуют решетку. (Свойства в п. 2 и 3 показываются в [8] через сведение к соответствующим свойствам в задаче SA; мы описываем прямые конструкции.)

2. ОПРЕДЕЛЕНИЯ И ПОСТАНОВКИ

Мы рассматриваем сеть $N = (G,S,T,c)$, состоящую из ориентированного графа $G = (V,E)$ (без петель и кратных ребер), выделенных непересекающихся подмножеств вершин $S$ (источники) и $T$ (стоки), называемых также терминалами, и функции $c:E \to {{\mathbb{R}}_{ + }}$ пропускных способностей ребер. (Здесь и далее ${{\mathbb{R}}_{ + }}$ и ${{\mathbb{Z}}_{ + }}$ – множества неотрицательных вещественных и неотрицательных целых чисел соответственно.) Для вершины $v \in V$ обозначим через ${{\delta }^{{{\text{in}}}}}(v)$ и ${{\delta }^{{{\text{out}}}}}(v)$ множества ребер входящих в $v$ и выходящих из $v$ соответственно. Для большей простоты нашего изложения мы предполагаем, что выполняется

Определение 1. Функция $f:E \to {{\mathbb{R}}_{ + }}$ называется допустимой (относительно $c$), если она удовлетворяет ограничениям $f(e) \leqslant c(e)$ для всех ребер $e \in E$. Определим эксцесс для $f$ в вершине $v \in V$ как

Путь в $G$ – это последовательность $P = ({{v}_{0}},{{e}_{1}},{{v}_{1}}, \ldots ,{{e}_{k}},{{v}_{k}})$, где ${{e}_{i}}$ – ребро, соединяющее вершины ${{v}_{{i - 1}}}$ и ${{v}_{i}}$. Ребро ${{e}_{i}}$ в $P$ называется прямым (forward), если ${{e}_{i}} = {{v}_{{i - 1}}}{{v}_{i}}$, и обратным (backward), если ${{e}_{i}} = {{v}_{i}}{{v}_{{i - 1}}}$. (Мы обозначаем ребро, выходящее из $u$ и входящее в $v$ как $uv$, вместо обычного $(u,v)$). Путь называется ориентированным (directed), если все его ребра прямые, и называется простым (simple), если все его вершины различны. Противоположный (обратный) путь $({{v}_{k}},{{e}_{k}},{{v}_{{k - 1}}}, \ldots ,{{e}_{1}},{{v}_{0}})$ обозначается через ${{P}^{{ - 1}}}$. Путь из вершины $u$ в вершину $v$ может быть назван $u{\kern 1pt} - {\kern 1pt} v$ путем. Если не оговорено противное, то, говоря о пути, мы считаем его нетривиальным, т.е. имеющим по крайней мере одно ребро.

Для допустимой функции $f$ ребро $e$ с $f(e) = c(e)$ ($f(e) < c(e)$; $f(e) = 0$) называется насыщенным (соответственно, ненасыщенным; свободным (от $f$)). Путь считается ненасыщенным, если таковы все его ребра.

В рассматриваемой нами задаче каждая внутренняя вершина $v$ сети $N$ снабжена линейным (полным строгим) порядком $ < _{v}^{ - }$ на множестве ${{\delta }^{{{\text{in}}}}}(v)$ и линейным порядком $ < _{v}^{ + }$ на множестве ${{\delta }^{{{\text{out}}}}}(v)$. Они интерпретируются как “отношения предпочтения”, а именно, $e < _{v}^{ - }e{\kern 1pt} '$ означает, что вершина (“агент”) $v$ предпочитает ребро $e$ ребру $e{\kern 1pt} '$; в этом случае мы также будем говорить, что $e$ расположена в ${{\delta }^{{{\text{in}}}}}(v)$ раньше или левее $e{\kern 1pt} '$, а $e{\kern 1pt} '$ – позже или правее $e$. В соответствии с порядком $ < _{v}^{ - }$ множество ${{\delta }^{{{\text{in}}}}}(v)$ организуется в виде списка (double-linked list); таким образом, первый (последний) элемент в списке наиболее (соответственно, наименее) предпочтительный. И аналогично для порядка $ < _{v}^{ + }$.

Определение 2. Поток $f$ в сети $N$ с указанными порядковыми оснащениями для внутренних вершин называется стабильным, если каждый ненасыщенный ориентированный путь $P = ({{v}_{0}},{{e}_{1}},{{v}_{1}}, \ldots ,{{e}_{k}},{{v}_{k}})$ удовлетворяет по крайней мере одному из следующих двух условий (где допускается случай ${{v}_{0}} = {{v}_{k}}$):

Нас интересует задача о стабильном потоке (SF): найти стабильный поток для сети $N$. Флейнер [8] установил, что эта задача всегда разрешима, а также имеет место свойство целочисленности: если сеть $N = (G = (V,E),S,T,c)$ целочисленная (т.е. $c \in \mathbb{Z}_{ + }^{E}$), то существует целочисленный стабильный поток.

Это доказывалось путем редукции задачи SF для $N$ к задаче о стабильном распределении (SA) на двудольном графе $G{\kern 1pt} ' = (V{\kern 1pt} ',E{\kern 1pt} ')$ с весами $c{\kern 1pt} '(e) \geqslant 0$ ребер $e \in E{\kern 1pt} '$ и “квотами” $q(v) \geqslant 0$ вершин $v \in V{\kern 1pt} '$. (Строго говоря, в [8] рассматривался случай, когда ${\text{|}}S \cup T{\kern 1pt} {\text{|}} = 2$, и условие (2.1) не накладывается, но указанные свойства верны и для нашего случая.) При этом редукция линейна по размерам, а именно: ${\text{|}}V{\kern 1pt} '{\text{|}} = 2{\text{|}}V{\text{|}}$ и ${\text{|}}E{\kern 1pt} '{\kern 1pt} {\text{|}} < {\text{|}}E{\kern 1pt} {\text{|}} + 2{\text{|}}V{\kern 1pt} {\text{|}}$, и сохраняет целочисленность: $c{\kern 1pt} '$ и $q$ целочисленные при целочисленном $c$. Задача SA была введена и исследована в [4], где были доказаны ее разрешимость для любой сети и свойство целочисленности и предложен сильно полиномиальный алгоритм решения.

Как было отмечено во введении, в [5] показано, что при использовании продвинутых структур данных, т.н. динамических и самонастраивающихся деревьев, задачу о стабильном распределении в графе с $n$ вершинами и $m$ ребрами можно решить с временнóй сложностью $O(m\log n)$ (а без использования таких структур можно добиться оценки $O(nm)$). Это, в силу указанной редукции, приводит к аналогичной оценке алгоритмической сложности и для задачи SF. Прямой алгоритм для SF в случае ${\text{|}}S{\kern 1pt} {\text{|}} = {\text{|}}T{\kern 1pt} {\text{|}} = 1$, предложенный в [10], имеет сложность $O(nm)$.

В настоящей работе предлагается альтернативный прямой алгоритм нахождения стабильного потока в произвольной сети $N = (G,S,T,c)$ (при условии (2.1)), основанный на методе предпотоков. В следующем разделе мы описываем базовую версию алгоритма (конечную при любом $c$), а в разд. 4 – модифицированную версию (с временнóй сложностью $O(nm)$).

3. БАЗОВЫЙ АЛГОРИТМ

Алгоритм нахождения стабильного потока в сети $N = (G = (V,E),S,T,c)$ состоит из последовательности итераций; как правило (но не всегда) итерация имеет две фазы: балансирование (balancing) и достройка (pushing) (подобно структуре этапа (большой итерации) в алгоритме построения максимального потока в [11]). Каждая итерация преобразует один блокирующий предпоток в другой, и процесс завершается, когда текущий предпоток становится потоком. Подчеркнем, что термин “блокирующий” заимствован из языка в [11] и имеет иной смысл, чем тот, что обычно понимают в задачах о стабильности.

Определение 3. Для предпотока $f$ в сети $N$ скажем, что вершина $v$ эксцессная, если ${\text{e}}{{{\text{x}}}_{f}}(v) > 0$. Предпоток $f$ называется блокирующим, если каждый ориентированный путь из $S$ в $T$ имеет насыщенное ребро. Если к тому же всякий ориентированный путь, идущий из эксцессной внутренней вершины в $T$ имеет насыщенное ребро, то мы называем $f$ полностью блокирующим.

Замечание 1. Полностью блокирующий предпоток не обязательно стабильный, и наоборот. В то же время всякий стабильный поток является блокирующим (и автоматически полностью блокирующим). В целом уже в ранжированной ациклической сети построение стабильного потока выглядит более сложной задачей, чем построение блокирующего потока. Последняя решается на этапе алгоритма в [11] за время $O({{n}^{2}})$, что быстрее, чем $O(nm)$ в алгоритме разд. 4 для SF.

4. МОДИФИЦИРОВАННЫЙ АЛГОРИТМ

В изложенном выше базовом алгоритме число итераций, на которых граф $\Gamma $ не меняется, может быть очень большим (как показывает пример в разд. 3); для удобства здесь и далее мы включаем разбиение $({{E}^{ + }},{{E}^{ - }})$ в описание $\Gamma $. В этом разделе мы описываем модифицированную версию, для которой число изменений предпотока $f$ при постоянном $\Gamma = ({{V}_{\Gamma }};{{E}^{ + }},{{E}^{ - }})$ имеет порядок $O(n)$. Это эквивалентно тому, что $O(n)$ изменений $f$ приводят к событию $S$, $F$ или $M$ (включая тот случай, когда некоторое активное ребро закрывается и становится критическим).

Путь в $\Gamma $ назовем правильным, если все активные ребра в нем прямые, а все критические ребра обратные. Последовательность итераций с постоянным $\Gamma $ назовем большой итерацией. Она начинается с выбора эксцессной вершины ${{v}_{0}}$ в $(G,f)$, и порядок обработки вершин уточняется следующим образом (полагая, что ${{v}_{0}}$ принадлежит $\Gamma $).

(A) Если при балансировании очередной эксцессной вершины $v$, состоящем в уменьшении $f$ в критическом ребре $u{v}$ (которое сохраняется в $\Gamma $), выясняется, что вершина $u$ внутренняя и имеет пустое активное ребро (и тогда все ребра в ${{\delta }^{{{\text{out}}}}}(u)$ насыщенные или закрытые (ср. (C3)б), ввиду чего достройка в $u$ невозможна), то переходим к балансированию в вершине $u$.

(B) Если при достройке в вершине $u$, состоящей в увеличении $f$ в активном ребре $e = uw$ выясняется, что вершина $w$ внутренняя и имеет непустое активное ребро $wz$, то далее производится достройка в $w$, а если $\tilde {e}(w) = \{ \emptyset \} $, то переходим к балансированию в $w$. При этом балансировании, если критическим ребром становится то же самое ребро $e = uw$, то оно закрывается и перестает быть активным в $u$, в результате чего граф $\Gamma $ изменяется, и большая итерация заканчивается.

Из этих уточнений следует, что последовательность обрабатываемых вершин и ребер образует правильный путь $P = ({{v}_{0}},{{e}_{1}},{{v}_{1}}, \ldots ,{{e}_{i}},{{v}_{i}}, \ldots )$. Для очередной вершины ${{v}_{k}}$ в $P$ возможны следующие особые ситуации:

(Q1) ${{v}_{k}}$ совпадает с ранее пройденной вершиной ${{v}_{i}}$;

(Q2) ${{v}_{k}}$ является терминалом.

Рассмотрим эти ситуации более подробно. В результате изменения $f$ на ${{e}_{1}}, \ldots ,{{e}_{k}}$ эксцессы всех вершин в $P$, кроме ${{v}_{k}}$, обнуляются.

1. В случае (Q1) выделяем правильный простой цикл $C = ({{v}_{i}},{{e}_{{i + 1}}}, \ldots ,{{v}_{k}})$. Подобно тому, как это делается для ротаций в алгоритмах для стабильных $b$-матчингах, распределениях, и др., мы изменяем $f$ вдоль $C$ на максимальную возможную величину $\Delta $, равную минимуму величин $f(e)$ для $e \in {{E}_{C}} \cap {{E}^{ - }}$ и величин $c(e{\kern 1pt} ') - f(e{\kern 1pt} ')$ для $e{\kern 1pt} ' \in {{E}_{C}} \cap {{E}^{ + }}$, увеличивая $f$ на $\Delta $ в прямых ребрах и уменьшая на $\Delta $ в обратных ребрах цикла $C$. В результате некоторое ребро в $C$ насыщается или освобождается, и происходит событие $M$ (вместе с $S$ или $F$), завершая большую итерацию. При этом эксцессы всех вершин сохраняются, и можно видеть, что предпоток $f$ продолжает быть стабильным и полностью блокирующим.

2. В случае (Q2) мы запоминаем $P$ (где теперь эксцессы всех внутренних вершин нулевые) и, в предположении сохранения $\Gamma $, продолжаем большую итерацию, выбирая новую эксцессную вершину ${v}_{0}^{'}$ в $(G,f)$ и строя новый правильный путь $P{\kern 1pt} ' = ({v}_{0}^{'},e_{1}^{'},{{{v}}_{1}}, \ldots )$. Рассмотрим возможные варианты.

а) Если путь $P{\kern 1pt} '$ зацикливается, то действуем, как указано в 1, и заканчиваем большую итерацию.

б) Если $P{\kern 1pt} '$ встречает предыдущий путь $P$ (ведущий в терминал) в вершине ${v}_{r}^{'} = {{{v}}_{i}}$, то объединяем $P{\kern 1pt} '$ с $P$, получая дерево $\mathcal{T}$ (с корнем в некотором источнике $s \in S$ или “антикорнем” в стоке $t \in T$); при этом все внутренние вершины в $\mathcal{T}$, кроме ${v}_{r}^{'}$, имеют нулевой эксцесс. Продолжаем большую итерацию с новой эксцессной вершиной ${v}_{0}^{{''}}$ в $(G,f)$.

в) Если же $P{\kern 1pt} '$ попадает в терминал, отличный от терминала в $P$, то запоминаем $P{\kern 1pt} '$ (помимо $P$) и продолжаем с новой эксцессной вершиной.

г) В общем случае каждый новый построенный путь, если он не зацикливается и не попадает в новый терминал, встречается либо с деревом $\mathcal{T}$ с корнем в $S$, либо с деревом $\mathcal{T}{\kern 1pt} '$ с антикорнем в $T$, и мы добавляем этот путь к данному дереву.

В результате при сохранении $\Gamma $ (в частности, при отсутствии зацикливания) получаем следующее: в $\Gamma $ построены несколько непересекающихся правильных деревьев ${{\mathcal{T}}_{1}}, \ldots ,{{\mathcal{T}}_{k}}$ с корнями в $S$ и деревьев $\mathcal{T}_{1}^{'}, \ldots ,\mathcal{T}_{\ell }^{'}$ с антикорнями в $T$, и все внутренние вершины в $G$, не лежащие в этих деревьях, имеют нулевые эксцессы.

При этом число изменений предпотока $f$ равно $\left| {{{E}_{{{{\mathcal{T}}_{1}}}}}} \right| + \cdots + \left| {{{E}_{{{{\mathcal{T}}_{k}}}}}} \right| + \;{\text{|}}{{E}_{{\mathcal{T}_{1}^{'}}}}{\text{|}} + \cdots + \;{\text{|}}{{E}_{{\mathcal{T}_{\ell }^{'}}}}{\text{|}} \simeq O(n)$. Осталось объяснить, как избавляться от этих деревьев.

Предположим $\ell \ne 0$, и обозначим $Z$ множество эксцессных вершин в $\mathcal{T}_{1}^{'}$ (это в точности множество точек ветвления в $\mathcal{T}_{1}^{'}$). Обойдя $\mathcal{T}_{1}^{'}$, выделим в нем минимальное поддерево $W$ с антикорнем в $t \in T$, содержащее $Z$, и перенумеруем ребра в $W$ в топологическом порядке ${{w}_{1}}, \ldots ,{{w}_{p}}$ (так, что если ${{w}_{j}}$ лежит на пути, соединяющем ${{w}_{i}}$ с $t$, то $i < j$). Перебирая ребра в этом порядке, изменяем $f$ в них естественным образом, получая одно из двух: либо (i) эксцессы всех вершин в $\mathcal{T}_{1}^{'} - \{ t\} $ становятся нулевыми, либо (ii) некоторое промежуточное ребро становится насыщенным или свободным, что заканчивает большую итерацию.

Аналогично действуем и с другими деревьями $\mathcal{T}_{i}^{'}$ и ${{\mathcal{T}}_{j}}$.

Таким образом, общая работа с деревьями осуществляется за время $O(n)$ и заканчивается либо событием $M$ (вместе с $S$ или $F$), либо избавлением от всех эксцессных внутренних вершин в $G$, и, следовательно, получением стабильного потока $f$. В течение большой итерации каждое ребро в $\Gamma $ рассматривается не более $O(1)$ раз. Поэтому временнáя сложность большой итерации – $O(n)$. Этот факт вместе с (3.2) приводят к следующему результату.

Предложение 2. Модифицированный алгоритм находит стабильный поток $f$ в сети $N = (G = (V,E),S,T,c)$ за время $O(nm)$ (причем $f$ целочисленный при целочисленном $c$).

Замечание 3. С достаточной уверенностью можно сказать, что данный алгоритм может быть ускорен до формальной временнóй оценки $O(m{\kern 1pt} \log n)$ путем применения структур данных как в [6], [7] для операций на графе $\Gamma $ (таких как выделение и перестройку компонент и циклов в $\Gamma $, агрегированное изменение предпотока на циклах и деревьях, и др.), в том же духе, как подобного рода процедуры для подграфа “слабых ребер” ускоряются в алгоритме [5]. Мы оставляем проработку этих технических деталей за рамками данной статьи, сохраняя достаточную простоту и практическую применимость изложенного выше метода.

5. ОБОБЩЕНИЯ

Задача о стабильном потоке в сети $N = (G = (V,E),S,T,c)$ может быть обобщена путем введения для каждой внутренней вершины $v$ верхней границы $\gamma (v) \in {{\mathbb{R}}_{ + }}$ разрешенного эксцесса в $v$. (Как и прежде мы предполагаем условие (2.1).)

Определение 4. Предпоток $f:E \to {{\mathbb{R}}_{ + }}$ в $N$ назовем $\gamma $-предпотоком, если он допустимый (т.е. $f \leqslant c$) и удовлетворяет ограничениям

В прикладных интерпретациях можно понимать ограничения в (5.1) как разрешение “агенту” $v$ не передавать далее весь продукт, доставленный по входящим ребрам-каналам $e \in {{\delta }^{{{\text{in}}}}}(v)$, а откладывать в запас (или отправлять “на сторону”) часть полученного продукта в размере, не превышающем $\gamma (v)$.

Мы называем $\gamma $-предпоток стабильным, если для каждого ненасыщенного ориентированного $u{\kern 1pt} - {\kern 1pt} v$ пути $P$ верно по крайней мере одно из двух: а) вершина $v$ внутренняя, и $P$ удовлетворяет (2.3) (при ${{v}_{k}} = v$), т.е. $P$ доминируется в $v$; или б) вершина $u$ внутренняя, и $P$ сильно доминируется в $u$, что означает выполнение (2.2) (при ${{v}_{0}} = u$) и отсутствие эксцесса в $u$: ${\text{e}}{{{\text{x}}}_{f}}(u) = 0$. При $\gamma = 0$ это превращается в определение стабильного потока.

Обобщение полученных выше результатов на $\gamma $-предпотоки выглядит так.

Предложение 3. Для сети $N = (G = (V,E),S,T,c)$ и вектора $\gamma \in \mathbb{R}_{ + }^{{V - (S \cup T)}}$ стабильный $\gamma $-предпоток существует и может быть найден за время $O(nm)$.

Доказательство. Данная задача сводится к задаче о стабильном потоке в расширенной сети $N{\kern 1pt} '$ с графом $G{\kern 1pt} ' = (V,E{\kern 1pt} ')$, полученным из $G$ добавлением для каждой внутренней вершины $v$ ребра $vt$ пропускной способности $c(vt): = \gamma (v)$, которое ставится в конец порядка на ${{\delta }^{{{\text{out}}}}}(v)$, а именно, $e < _{v}^{ + }vt$ для всех $e \in \delta _{G}^{{{\text{out}}}}(v)$. Здесь $t$ – выделенный сток в $T$. Пусть $f{\kern 1pt} '$ – стабильный поток для $N{\kern 1pt} '$, и $f$ – его ограничение на $G$. Тогда $f$ – это $\gamma $-предпоток, и его стабильность следует из стабильности $f{\kern 1pt} '$. (Действительно, если $P$ – ненасыщенный ориентированный $u{\kern 1pt} - {\kern 1pt} v$ путь в $G$, который, будучи рассмотрен как путь в $G{\kern 1pt} '$, доминируется в $u$, то выполняется $f{\kern 1pt} '(ut) = 0$, и мы получаем ${\text{e}}{{{\text{x}}}_{f}}(u) = 0$.) Предложение доказано.

Мы можем обобщить задачу далее, вводя для каждой внутренней вершины $v$, помимо $\gamma (v)$ как выше, границу $\beta (v) \in {{\mathbb{R}}_{ + }}$ для величины $ - {\text{ex}}(v)$. Иначе говоря, мы рассматриваем допустимую (по $c$) функцию $f:E \to {{\mathbb{R}}_{ + }}$, удовлетворяющую

Назовем $(\beta ,\gamma )$-квазипоток стабильным, если для каждого ненасыщенного ориентированного $u{\kern 1pt} - {\kern 1pt} v$ пути $P$ верно по крайней мере одно из двух: а) вершина $u$ внутренняя, и $P$ сильно доминируется в $u$ (относительно $\gamma $) в том смысле, что выполняется (2.2) (при ${{v}_{0}} = u$), и эксцесс в $u$ неположительный (и не менее $ - \beta (u)$); или б) вершина $v$ внутренняя, и $P$ сильно доминируется в $v$ (относительно $\beta $), что означает выполнение (2.3) (при ${{v}_{k}} = v$) и неотрицательный эксцесс в $v$ (не более $\gamma (v)$). При $\beta = \gamma = 0$ получаем определение стабильного потока.

Для данного обобщения справедливо

Предложение 4. Для сети $N = (G = (V,E),S,T,c)$ и векторов $\beta ,\gamma \in \mathbb{R}_{ + }^{{V - (S \cup T)}}$ стабильный $(\beta ,\gamma )$-квазипоток существует и может быть найден за время $O(nm)$.

Доказательство. Рассмотрим задачу о стабильном потоке в расширенной сети $N{\kern 1pt} '$ с графом $G{\kern 1pt} ' = (V{\kern 1pt} ',E{\kern 1pt} ')$, полученным из $G$: а) расщеплением каждой внутренней вершины $v$ на две копии $v{\kern 1pt} '$ и ${v}{\kern 1pt} '{\kern 1pt} '$, где ${v}{\kern 1pt} '$ наследует входящие ребра из ${{\delta }^{{{\text{in}}}}}(v)$, а $v{\kern 1pt} '{\kern 1pt} '$ – выходящие ребра из ${{\delta }^{{{\text{out}}}}}({v})$ (с теми же пропускными способностями и порядками на них); б) добавлением ребра ${v}{\kern 1pt} '{v}{\kern 1pt} '{\kern 1pt} '$ большой пропускной способности; и в) добавлением ребра ${v}{\kern 1pt} 't$ пропускной способности $c({v}{\kern 1pt} 't): = \gamma (v)$ и ребра $sv{\kern 1pt} '{\kern 1pt} '$ пропускной способности $c(sv{\kern 1pt} '{\kern 1pt} '): = \beta (v)$, где $v{\kern 1pt} 't$ и $sv{\kern 1pt} '{\kern 1pt} '$ полагаются менее приоритетными, чем ребро $v{\kern 1pt} 'v{\kern 1pt} '{\kern 1pt} '$, и где $s$ и $t$ – выделенные источник и сток соответственно. Пусть $f{\kern 1pt} '$ – стабильный поток для $N{\kern 1pt} '$, и $f$ – его “образ” в $G$. Можно проверить, что $f$ – это $(\beta ,\gamma )$-квазипоток в $N$, и его стабильность следует из стабильности $f{\kern 1pt} '$. Здесь существенен тот факт, что для каждой внутренней вершины $v \in V$ по крайней мере одно из значений $f{\kern 1pt} '(sv{\kern 1pt} '{\kern 1pt} ')$ и $f{\kern 1pt} '(v{\kern 1pt} 't)$ должно быть нулевым (что следует из рассмотрения ненасыщенного пути $(v{\kern 1pt} ',v{\kern 1pt} 'v{\kern 1pt} '{\kern 1pt} ',v{\kern 1pt} '{\kern 1pt} ')$). Предложение доказано.

6. ДОПОЛНИТЕЛЬНЫЕ ЗАМЕЧАНИЯ

В этом заключительном разделе указываются три дополнительных интересных свойства стабильных потоков и предпотоков. Как и выше, мы рассматриваем ориентированную сеть $N = (G = (V,E),S,T,c)$ c линейными порядками на ${{\delta }^{{{\text{in}}}}}(v)$ и ${{\delta }^{{{\text{out}}}}}(v)$ для внутренних вершин $v \in V - (S \cup T)$ (и при условии (2.1)).

I. Для предпотока $f$ в сети $N = (G,S,T,c)$ будем считать величиной $f$ суммарный эксцесс в стоках: ${\text{val}}(f): = {\text{e}}{{{\text{x}}}_{f}}(T)$ ($ = \sum\nolimits_{t \in T} \,{\text{e}}{{{\text{x}}}_{f}}(t)$). Справедливо следующее свойство:

Действительно, если $f$ не является потоком (т.е. имеет эксцессную внутреннюю вершину), то $f$ перестраивается в стабильный поток $f{\kern 1pt} '$ применением последовательности итераций базового алгоритма. Каждое балансирование не изменяет значений в ребрах, входящих в $T$, а достройка может только увеличивать эти значения, что дает требуемое свойство (6.1).

II. Что касается величин стабильных потоков, то, обобщая классические результаты для стабильных марьяжей, стабильных двудольных b-матчингов и др., Флейнер [8, Sec. 4] установил, что:

Как следствие, ${\text{val}}(f) = {\text{val}}(g)$. Свойство (6.2) доказывалось в [8] (где рассматривались двухполюсные сети и допускались произвольные ребра, инцидентные терминалам) путем сведения к соответствующему свойству для стабильных распределений. Для наших сетей можно дать прямое и наглядное доказательство.

А именно, свяжем с функцией $f - g$ соответствующее разложение по путям и циклам. Более точно, поскольку $f$ и $g$ не имеют эксцессных внутренних вершин, можно образовать семейство $\mathcal{C}$, состоящее из простых путей и циклов $C$ с весами $\Delta (C) > 0$ так, чтобы выполнялось следующее:

(i) для каждого $C \in \mathcal{C}$ его прямые ребра $e$ удовлетворяют $f(e) > g(e)$, а обратные ребра $e'$ удовлетворяют $f(e{\kern 1pt} ') < g(e{\kern 1pt} ')$;

(ii) для каждого ребра $e \in E$ сумма весов $\Delta (C)$ по путям/циклам $C$, содержащим $e$, равна ${\text{|}}f(e) - g(e){\kern 1pt} {\text{|}}$;

(iii) каждый путь в $\mathcal{C}$ соединяет два разных терминала, а каждый цикл содержит не более одного терминала.

Предположим, $f$ и $g$ не совпадают на некотором ребре $e$, инцидентном терминалу, и рассмотрим случай, когда $e$ выходит из источника $s \in S$ (т.е. $e \in {{\delta }^{{{\text{out}}}}}(s)$). Для определенности положим $f(e) > g(e)$. Тогда имеется $C \in \mathcal{C}$, содержащее $e$ (как прямое ребро); при этом либо а) $C$ – путь из $s$ в $t \in T$, либо б) $C$ – путь из $s$ в $s{\kern 1pt} ' \in S$ (возможно, $s{\kern 1pt} ' = s$).

В случае а) имеется последовательность $s = {{v}_{0}},{{v}_{1}}, \ldots ,{{v}_{k}} = t$ вершин в $C$ (где $k$ нечетное), для которой часть $C$ от ${{v}_{{i - 1}}}$ до ${{v}_{i}}$ имеет только прямые ребра при нечетном $i$, и только обратные ребра при четном $i$. Тогда

(Такие пути фигурируют в конкатенации ${{P}_{1}} \cdot Q_{2}^{{ - 1}} \cdot {{P}_{3}} \cdot Q_{4}^{{ - 1}} \cdot \ldots \cdot Q_{{k - 1}}^{{ - 1}} \cdot {{P}_{k}}$ для $C$, где ${{Q}^{{ - 1}}}$ обозначает путь, обратный пути $Q$.) Обозначим ${{p}_{i}}$ ($p_{i}^{'}$) первое (соответственно, последнее) ребро в ${{P}_{i}}$, и обозначим ${{q}_{j}}$ ($q_{j}^{'}$) первое (соответственно, последнее) ребро в ${{Q}_{j}}$. Можно видеть, что

Теперь применим (6.3) и (6.4), двигаясь шаг за шагом по последовательности путей ${{P}_{1}},{{Q}_{2}},{{P}_{3}} \ldots $. Так как ${{P}_{1}}$ начинается в источнике ${{{v}}_{0}} = s$ и является ненасыщенным для $g$, и так как выполняется $g(q_{2}^{'}) > 0$, то из стабильности $g$ следует, что $q_{2}^{'} < _{{{{{v}}_{1}}}}^{ - }p_{1}^{'}$. Тогда из стабильности $f$, ненасыщенности ${{Q}_{2}}$ для $f$, неравенства $f({{p}_{3}}) > 0$, и свойства, что ${{Q}_{2}}$ не доминируется в ${{{v}}_{1}}$ (в силу $f(p_{1}^{'}) > 0$), получаем ${{p}_{3}} < _{{{{{v}}_{2}}}}^{ + }{{q}_{2}}$. И так далее. Дойдя до пути ${{Q}_{{k - 1}}}$, получаем ${{p}_{k}} < _{{{{{v}}_{{k - 1}}}}}^{ + }{{q}_{{k - 1}}}$. Но тогда последний путь ${{P}_{k}}$ (который заканчивается в стоке ${{{v}}_{k}} = t$ и является ненасыщенным для $g$) не доминируется в начальной вершине ${{{v}}_{{k - 1}}}$, вопреки стабильности $g$.

В случае б) рассуждения схожи. Здесь мы имеем дело с конкатенацией путей вида ${{P}_{1}},Q_{2}^{{ - 1}}, \ldots ,{{P}_{{k - 1}}},Q_{k}^{{ - 1}}$ (при четном $k$). При этом последний путь ${{Q}_{k}}$ начинается в источнике ${{{v}}_{k}} = s{\kern 1pt} '$, является ненасыщенным для $f$, и не доминируется в концевой вершине ${{{v}}_{{k - 1}}}$ (в силу $f(p_{{k - 1}}^{'}) > 0$ и $q_{k}^{'} < _{{{{{v}}_{{k - 1}}}}}^{ - }p_{{k - 1}}^{'}$), что противоречит стабильности $f$. По соображениям симметрии, случаи несовпадений $f$ и $g$ в ребре, входящем в $T$, также невозможны. Этим заканчивается доказательство (6.2).

III. Предыдущая конструкция может быть продолжена. А именно, рассмотрим два стабильных потока $f$ и $g$ в сети $N = (G,S,T,c)$. Пусть $H$ – подграф в $G$, порожденный ребрами в $A: = \{ e:f(e) > g(e)\} $ и $B: = \{ e:g(e) > f(e)\} $, и назначим ребрам $e$ в $H$ веса $\omega (e): = {\text{|}}f(e) - g(e){\kern 1pt} {\text{|}}$. Согласно (6.2), $H$ не содержит терминальных вершин. Более того, $\omega $ раскладывается в неотрицательную линейную комбинацию характеристических функций простых правильных циклов (и тем самым $\omega $ может рассматриваться как “циркуляция”).

Здесь мы говорим, что (не обязательно простой) цикл $C$ в $H$ является правильным, если все прямые ребра в нем принадлежат $A$, а обратные принадлежат $B$. Для вершины ${v}$ в таком цикле обозначим ${{\Pi }_{C}}({v})$ множество пар подряд идущих ребер, инцидентных ${v}$ и следующих в направлении цикла. Назовем пару $\pi \in {{\Pi }_{C}}({v})$ особой, если $\pi $ содержит ребро как из $A$, так и из $B$ (эквивалентно, оба ребра в $\pi $ либо входят в ${v}$, либо выходят из ${v}$). В этом случае скажем, что пара $\pi = (e,e{\kern 1pt} ')$ левая, если $e$ предпочтительнее для ${v}$, чем $e{\kern 1pt} '$; иначе пара называется правой. Рассуждая как при доказательстве (6.2), из стабильности $f$ и $g$ можно заключить, что

Это свойство распространяется на компоненты связности $K$ в $H$: все особые пары ребер, встречающиеся в правильных циклах в $K$, одновременно либо левые, либо правые (это следует из того, что две такие пары $\pi ,\;\pi {\kern 1pt} '$ можно включить в один правильный (не обязательно простой) цикл в $K$). В соответствии с этим выделим четыре типа компонент $K$. А именно, скажем, что $K$ имеет: тип $A$ (тип $B$), если все ребра в $K$ принадлежат множеству$A$ (соответственно, $B$); и имеет тип $L$ (тип $R$), если $K$ имеет ребра в обоих множествах $A$ и $B$ (в этом случае назовем компоненту $K$ богатой), и ориентации всех особых пар в $K$ левые (соответственно, правые). Эквивалентно,

Пользуясь этим, можно явно описать множество стабильных потоков в $N$ в виде решетки (что делается в [8] путем сведения к задаче о стабильном распределении и апелляции к соответствующему результату в [4]). А именно, определим следующие функции $h,\;\ell $ на $E$:

Можно видеть, что $h$ и $\ell $ являются потоками. А также для каждой внутренней вершины ${v}$ поток $h$ доминирует потоки $f,\;g$ на множестве ${{\delta }^{{{\text{out}}}}}({v})$, и доминируется этими потоками на множестве ${{\delta }^{{{\text{in}}}}}({v})$, в то время как $\ell $ ведет себя противоположным образом. (Здесь для числовых функций $a,\;b$ на упорядоченном множестве $(S, \prec )$ считаем, что $a$ доминирует $b$, если либо $a = b$, либо имеется $e \in S$ такое, что $a(e) > b(e)$, $a(e{\kern 1pt} ') \geqslant b(e{\kern 1pt} ')$ при $e{\kern 1pt} ' \prec e$, и $a(e{\kern 1pt} '{\kern 1pt} ') \leqslant b(e{\kern 1pt} '{\kern 1pt} ')$ при $e \prec e{\kern 1pt} '{\kern 1pt} '$.)

Из вышесказанного можно получить (мы опускаем подробности), что $h$ совпадает с указанным в [8, Sec. 4] потоком $f \vee g$, а $\ell $ совпадает с потокам $f \wedge g$; в частности, оба $h,\;\ell $ стабильные.

Автор выражает благодарность рецензенту за анализ начальной версии статьи и указание работ [10], [12], не известных автору при ее написании.