Сложность некоторых алгоритмических проблем для кососимметрических графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

СЛОЖНОСТЬ НЕКОТОРЫХ АЛГОРИТМИЧЕСКИХ ПРОБЛЕМ ДЛЯ КОСОСИММЕТРИЧЕСКИХ ГРАФОВ

специальность 01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

□03052146

На правах рукописи УДК 519.178

Бабенко Максим Александрович

Москва — 2007

003052146

Работа выполнена на кафедре математической логики и теории алгоритмов Механико-математического факультета Московского государственного университета им. М. В. Ломоносова.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук,

профессор Н. К. Верещагин

доктор физико-математических наук,

профессор В. В. Вьюгин

кандидат физико-математических наук

Д. В. Карпов

Вычислительный центр имени А. А. Дородницына Российской академии наук

Защита диссертации состоится 6 апреля 2007 г. в 16 ч. 15 мин. на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М. В. Ломоносова по адресу:

119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 6 марта 2007 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор

В. Н. Чубариков

Общая характеристика работы

Актуальность темы

Данная работа относится к теории комбинаторной оптимизации. В качестве основного объекта рассмотрения выступают графы: стандартные (направленные и ненаправленные), а также нестандартные (кососиммет-рические и двунаправленные).

Приведем вначале основные определения, касающиеся двух стандартных типов графов: направленных и ненаправленных. Направленный граф G представляет собой четверку (V, A, tail, head), где V — конечное множество вершин, А — конечное множество дуг, а отображения tail: А —► V, head: А —> V сопоставляют каждой дуге а £ А пару различных вершин: начало tail(a) и конец head(a). Если head(ai) = ЬеаЛ(аг) и tail(ai) — tail(a2), то дуги а\ и аг называют параллельными. В случае когда не возникает неоднозначностей в понимании, дугу, идущую из вершины и в вершину v, мы будем обозначать через (и, v). Более того, при записи функций от дуг графа будем опускать двойные скобки и писать f(u,v) вместо полного варианта f((u,v)).

Маршрутом Р из s в t (или, для краткости, s-t маршрутом) в направленном графе G называют последовательность вершин и дуг вида

р = (s = v0, аи Vi,..., Vfc-i, ak, vk = t),

где Vi — вершины (0 < i < k), щ — дуги, tail(ai) = head(a,) = Vi (1 < i < k).

В случае если все дуги аг в последовательности Р различны, то маршрут Р будем называть простым по дугам (или путем)-, в случае если vt ф Vj для всех 0 < i < j < к и v0 ф Vi, vk ф vt- для всех 0 < г < к, то простым по вершинам (или простым путем). Отметим, что концы простого пути могут совпадать. Маршрут Р будем называть циклическим, если s = t; циклический маршрут, являющийся (простым) путем, будем называть (простым) циклом.

Переходим теперь к понятию ненаправленного графа. Каждый такой граф задается тройкой (V, Е, ends), где V — конечное множество вершин, Е — конечное множество ребер, а отображение ends задает для каждого ребра е G Е множество ends(e) = {u,v}, состоящее из двух различных вершин и, v (концов е). В случае если ends(ej) = ends^), то ребра е\ и &2 называют параллельными. Ребро, соединяющее вершины и иг», мы обозначаем через {и, и}.

Понятие маршрута переносится на случай ненаправленного графа следующим образом. Маршрутом Р из s в t (s-t маршрутом) в ненаправленном графе G называют последовательность вершин и ребер вида

Р- {v0,ei,v1,...,vk~i,ek,vk),

где Vi — вершины (0 < г < fc), е, — ребра, ends(ej) = {v,_i, V{} (1 < i < к).

Если все ребра в{ в последовательности Р различны, то маршрут Р будем называть простым по ребрам (или путем). Определения понятий простого по вершинам маршрута (или, иначе говоря, простого пути), циклического маршрута, а также цикла и простого цикла полностью повторяют соответствующие определения для случая направленного графа.

Понятие двунаправленного графа возникло в работах Эдмондса и Джонсона при решении специального класса задач целочисленного программирования1 .

Двунаправленный граф G — это четверка (V, Е, ends, о;). Здесь V — конечное множество вершин, Е — конечное множество двунаправленных ребер. Отображение ends определено на множестве Е и сопоставляет каждому ребру е £ Е двухэлементное мультимножество ends(e) = {u, v}, где u,v — вершины (не обязательно различные), называемые концами е. Наконец, для каждого ребра е € Е и вершины v € ends(e) определено значение w(e,v) € {+1,-1}, называемое направлением ребра е в вершине v. В случае если ui(e, v) = +1, то говорят, что ребро е входит в V, иначе говорят, что ребро е выходит из v. Отметим, что возможен случай ends(e) = такие ребра е называют двунаправленными петлями. В случае ui(e, v) = +1, петля е дважды входит в г>; иначе е дважды выходит из v.

Итак, каждое ребро е €Е Е соединяет две вершины u,d g ends(e) и принадлежит к одному из следующих трех типов:

1) направленное ребро (или дуга), которое выходит из одного конца и заходит в другой (при этом и ф г>);

2) ребро, входящее в оба конца;

1Edmonds J., Johnson Е. L. Matching, a Well-Solved Class of Integer Linear Programs // Combinatorial Structures and Their Applications, Calgary International Conference. New York: Gordon and Breach, 1970. P. 89-92.

Lawler E. L. Combinatorial Optimization: Networks and Matroids. New York- Holt, Reinhart, and "Winston, 1976.

Schrijver A. Combinatorial Optimization. Berlin: Springer, 2003.

3) ребро, выходящее из обоих концов.

Пример двунаправленного графа представлен на рис. 1.

Маршрут из й в 4 маршрут) в двунаправленном графе б? представляет собой чередующуюся последовательность вершин и ребер

Р = (в = и0,еьУи...,ек,Ук = $, (1)

где г>; — вершины (0 < г < /с), е* — двунаправленные ребра, епсЦе,) = {и,-!,^} (1 < г < к), и для всех 0 < г < к ребра образуют

транзитную пару в вершине г^, то есть одно из ребер е^ е,+1 входит в г;,, а другое выходит из V,.

Как и в случае обычных графов, маршрут без повторяющихся ребер называют путем. Понятие простого пути вводится для двунаправленных графов точно так же, как и для направленных и ненаправленных. Маршрут (1), в котором я = и ребра ей образуют транзитную пару в вершине в, называют циклическим. Циклический маршрут, являющийся (простым) путем, называют (простым) циклом.

Направленный граф можно считать двунаправленным, превратив каждую дугу а = (и, г>) исходного графа в ребро еа с множеством концов {и, и} и положив и>(еа, и) —1, со(еа, и) := +1. При этом семейство маршрутов исходного направленного графа и семейство маршрутов полученного двунаправленного графа находятся в естественном взаимно однозначном соответствии.

Для произвольного графа С? мы будем писать Ус (соответственно Ас, Ее) для обозначения его множества вершин (соответственно дуг, ребер). Аналогично через Ур, Ар, Ер будут обозначаться мультимножества вершин, дуг и ребер произвольного маршрута Р.

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

сформулировано в работах Гольдберга и Карзанова2, а также Татта3 (где они получили название антисимметрических орграфов).

Рассмотрим направленный граф G. Пусть задана пара биекций ay: Vg —> Vq и о а - Aq Ag, обладающих следующими свойствами:

1) оу(оу(и)) = v для всех г; £ Vq и стДсгДа)) = а для всех а € Ag',

2) сту{у) ф v для всех v G Vg и ста (а) ^ а для всех а € Ас;

3) head(c7^(fl)) = oy(tail(a)) и tail(cr^(a)) = <7y(head(a)) для всех а €

Тогда тройку (G, оу, будем называть кососимметрическим графом. Если это не вызывает разночтений, мы будем называть кососимметрическим и сам направленный граф G. В дальнейшем нам потребуется работать как с кососимметрическими, так и с обычными направленными графами. Для того, чтобы подчеркнуть отсутствие кососимметрической структуры у последних, будем называть их стандартными.

Пару отображений (оу, а а) мы скомбинируем в одно отображение <т: Vg U Ag —» Vg U Ag. Отображения сг, оу, а а будем называть отображениями симметрии графа. Для удобства записи мы будем использовать обозначение х' для образа сг(х) (как по отношению к вершинам, так и к дугам). Элемент х' (вершину или дугу) будем называть симметричным к элементу х. Множество вершин Vg тогда разбивается на непересекающиеся пары симметричных вершин; также дело обстоит и с множеством дуг. Симметрия естественным образом переносится на подмножества вершин и дуг графа. Из определения следует, что если в ко-сосимметрическом графе G присутствуют дуги, соединяющие пару симметричных вершин v, г/, то таких дуг непременно четное число, и они разбиваются на пары симметричных.

Покажем теперь, как введенное понятие кососимметрического графа связано с понятием двунаправленного. Пусть задан кососимметрический граф G. Выберем произвольное упорядоченное разбиение 7Г = (Vi, V2) множества Vg (то есть Vg = V\ U V2, Vi П V2 — 0), такое что V{ = V2. Тогда no G и 7Г можно построить двунаправленный граф G с множеством вершин Vi следующим способом: ребра G будут соответствовать парам

2 Goldberg А. V., Karzanov А. V. Path Problems in Skew-Symmetric Graphs // Combinatorics. 1996 V. 16, № 3. P. 353-382.

Goldberg A. V., Karzanov A. V. Maximum Skew-Symmetric Flows and Matchings // Mathematical Programming. 2004. V. 100, № 3. P. 537-568.

3 Tutte W. T. Antisymmetncal Digraphs // Canadian J. Math. 1967. V. 19. P. 1101-1117.

г

Чг-У

X

V

(а) Двунаправленный граф С?

(5) Соответствующий кососим-метрический граф в

Рис. 2. Соответствие между двунаправленными и кососимметрическими графами

симметричных дуг в С. Точнее, каждая пара симметричных дуг а, а' в (3 порождает одно ребро е в С?, соединяющее вершины и, V 6 так что:

1) ребро е идет из и в V, если одна из дуг а, а' идет из и в г» (а другая из V1 в и');

2) ребро е выходит из обоих концов и, V, если одна из дуг а, а' идет из и в г/ (а другая из г; в и');

3) ребро е входит в оба конца и, V, если одна из дуг а, а' идет из и' в г; (а другая из г/ в и).

В частности, ребро е будет петлей, если дуги а, а' соединяют пару симметричных вершин.

Обратно, двунаправленный граф С? порождает кососимметрический граф б с отображением симметрии а следующим образом. Для каждой вершины V € Уд возьмем ее копию ст(г)) и образуем множество У~ := {<т(г>) | V е Уд}- Положим Ус := Уд и У~. Для каждого ребра е € Ед, соединяющего вершины и иг), построим две симметричные дуги а, а' е Ас, чтобы выполнялись указанные выше условия 1-3. Пример соответствия между двунаправленными и кососимметрическими графами представлен на рис. 2.

Существует также соответствие между маршрутами в С и маршрутами в С?. А именно, пусть т обозначает отображение Ус и Ас на Уд и Ед, склеивающее пары симметричных вершин и дуг. Каждый маршрут Р = (г;0, а^ а*, в С? индуцирует последовательность

т(Р) := (т(г>о), т(а1)>г("О> • ■ - >т(ак),т(уь)) вершин и ребер из <3. Легко видеть, что т(Р) будет маршрутом в (2.

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

Будем называть маршрут нетривиальным, если он содержит хотя бы одно ребро (или дугу). Путь в кососимметрическом графе будем называть регулярным, если в нем не встречается пары симметричных дуг (при этом симметричные вершины встречаться могут). По каждому нетривиальному маршруту Р = (то, ех, го1;..., е*, и)/.) в графе С? можно построить последовательность т(Р) := («0,01,1)1 , из вершин и дуг графа С по следующему правилу:

1) если ребро е\ выходит из гио (соответственно входит в ш0), то положим «о := ЗДо (соответственно Vo :— ги'0);

2) для всех 1 < г < к если ребро е; выходит из ^¿-ь то в качестве возьмем дугу из множества т~1(в{), которая выходит из кроме того положим VI := Ьеас1(а;);

3) для всех 1 < г < к если ребро в{ входит в г/7,_1, то в качестве а* возьмем дугу из множества т-1(ех), которая выходит из ии'^; кроме того положим Ь{ := ЬеаЛ(а,).

В случае когда ребро е,- представляет собой петлю, то дуги из т-1(е*) оказываются параллельными, поэтому дуга а, выбирается из двух возможных произвольным образом. Несложно показать, что для любого нетривиального маршрута Р в С справедливы свойства:

1) т(Р) представляет собой маршрут в б, причем т(т(Р)) = Р;

2) Р представляет собой путь (то есть простой по ребрам маршрут), если и только если т(<5) представляет собой регулярный путь.

Тем самым, отображения т, т задают взаимно однозначное (с точностью до выбора представителя из пары параллельных дуг вида (и, г>'), как указано выше) соответствие между семействами нетривиальных маршрутов (соответственно нетривиальных путей) в (3 и нетривиальных маршрутов (соответственно нетривиальных регулярных путей) в (?.

Как показано в главе 2 диссертации, в терминах кососимметриче-ских графов оказывается возможным описать широкий спектр задач комбинаторной оптимизации (паросочетания в графах общего вида, Т-соединения, 6-паросочетания, /-факторы, упаковки Т-путей и другие). Тем самым, теория кососимметрических графов служит удобным обобщающим инструментом, а алгоритмы для задач на кососимметрических графах находят множество применений.

Цель работы

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

Первый класс составляют задачи, связанные с разысканием в ко-сосимметрическом графе G кратчайшего регулярного пути между выбранной парой вершин. Длины дуг могут быть произвольными (в том числе отрицательными) числами, а длиной пути называется сумма длин составляющих его дуг. При этом предполагается, что длины симметричных дуг равны, и в графе отсутствуют регулярные циклы отрицательной длины. В работе Гольдберга и Карзанова4 представлен алгоритм с оценкой 0(тп2 logn). (Здесь и далее через тг обозначается число вершин графа, а через тп — число ребер или дуг. При этом предполагается, что 2п <тп < п2). Мы улучшаем данную оценку до 0(min(mnlogn,n3)).

Второй класс образуют задачи, связанные с циклической структурой кососимметрических и двунаправленных графов. Мы обобщаем понятие ацикличности на случай кососимметрических графов. При этом оно распадается на два: обычная ацикличность (отсутствие циклов) и регулярная ацикличность (отсутствие регулярных циклов). Для каждого из этих типов мы устанавливаем структурные результаты, а также предъявляем алгоритмы, позволяющие выполнить проверку на принадлежность данного графа к указанному типу за линейное время. Структурные результаты для случая регулярной ацикличности позволяют дать короткое доказательство известной в теории паросочетаний теоремы Коцига5 (утверждающей, что если в ненаправленном графе G су-

4 Goldberg А. V., Karzanov А. V. Path Problems in Skew-Symmetric Graphs // Combinatorica. 1996. V. 16, № 3. P. 353-382.

ществует и единственно совершенное паросочетание М, то в G есть мост, причем М содержит хотя бы один из мостов G).

Среди проблем второго класса следует также упомянуть задачу о разыскании в кососимметрическом графе G регулярного цикла минимального среднего веса. (Предполагается, что дугам графа приписаны вещественные веса, при этом веса симметричных дуг равны. Под средним весом цикла понимается отношение суммы весов его дуг к их количеству.) Для стандартных направленных графов эта задача изучалась Карпом6 (алгоритм с оценкой 0(тпп)), а для ненаправленных — Ба-рахоной7 (алгоритм с оценкой 0(min(m2nlogn,mn3))). Задача на косо-симметрическом графе обобщает обе упомянутые проблемы и, как мы показываем, может быть решена за время 0(min(mn2 logn, п4)). В частности, мы улучшаем оценку Барахоны.

Третий класс складывается из потоковых и мультипотоковых задач. Нами рассматривается проблема нахождения в кососимметрических сетях целочисленных кососимметрических потоков минимальной стоимости; для ее решения предлагается два алгоритма. Оценка сложности первого составляет 0(&min(mlogn,n2)), где к — величина потока. Второй алгоритм имеет оценку сложности 0(ф(п,гп) + min(mralogrc, га3)), где ф(п', т') обозначает сложность задачи о целочисленной циркуляции минимальной стоимости в стандартной направленной сети с п' вершинами и т! дугами.

Мы также изучаем случай простых кососимметрических сетей, то есть кососимметрических графов, в которых каждой дуге приписана единичная пропускная способность, и параллельные дуги отсутствуют. Для стандартного направленного случая потоковая задача в простых сетях изучалась Карзановым, а также Эвеном и Таржаном8. Был получен алгоритм со временем работы 0(min(mn2/3,m3/2)). Для двунаправленных сетей оценка сложности 0(т3/2) была получена Габовым9.

bKotzig A. On the Theory of Finite Graphs with a Linear Factor I // Mat.-Fyz. Casopis Slovensk. Akad. Vied. 1959. V. 9. P. 73-91.

eKarp R. M. A Characterization of the Minimum Cycle Mean in a Digraph // Discrete Mathematics. 1978. V. 23. P. 309-311.

7Barahona F. Reducing Matching to Polynomial Size Linear Programming 11 SIAM Journal on Optimization. 1993. V. 3. P. 688-695.

6Карзанов Л. В. О нахождении максимального потока в сетях специального вида и некоторых приложениях // Сб.: Математические вопросы управления производством. Вып. 5. М.: МГУ. 1973. С. 81-94.

Even S., Tarjan R. Е. Network Flow and Testing Graph Connectivity // SIAM Journal on Computing.

1975. V. 4, Л» 4. P. 507-518.

"Gabow H. N. An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems // Proceedings of the Fifteenth Annual ACM Symposium on Theory of

В наших построениях мы опираемся на разработанный ранее Гольд-бергом и Карзановым10 метод блокирующих потоков в кососимметриче-ских сетях. Мы устанавливаем для данного метода оценку сложности 0(тпп2//3), тем самым полностью ликвидируя зазор между стандартным и кососимметрическим вариантами задачи. Ключевую роль играет доказываемое нами утверждение о том, что всякий ациклический целочисленный кососимметрический поток в кососимметрической сети без параллельных дуг имеет носитель размера 0(riy/v), где v — величина потока (аналог этого утверждения для стандартных направленных сетей был получен Каргером и Левиным11).

В работе также изучается вопрос построения в стандартной направленной сети разложения многополюсного потока на слагаемые, отвечающие всевозможным парам источников и стоков. Предлагаемый алгоритм имеет оценку сложности 0(mlog(n2/m)) (в предположении, что число источников и стоков ограничено константой). Также рассматривается обобщение на случай кососимметрических сетей.

Кроме того, мы рассматриваем целочисленные мультипотоковые задачи в кососимметрических сетях. В общей постановке эти проблемы являются NP-трудными, поэтому мы ограничиваемся классом внутренне эйлеровых сетей (то есть таких, в которых для любой внутренней вершины v суммы пропускных способностей дуг, входящих В V и выходящих из v, равны). Ранее задача о максимальном мультипотоке изучалась для случая ненаправленных и стандартных направленных сетей в работах Ломоносова12, а также Ибараки, Карзанова, Нагамочи13. Кососимметрический случай является одновременным обобщением как направленного, так и ненаправленного. Мы излагаем алгоритм для нахождения искомого целочисленного кососимметрического мультипотока за время O(mn\og(n2/m)logt) (где t обозначает количество терминалов). Эта оценка совпадает со временем работы известного алгоритма для направленного случая и улучшает другую известную оценку 0(тп2) для ненаправленного случая.

Computing. V. 15. 1983. Р. 448-456.

10 Goldberg А. V., Karzanov А. V. Maximum Skew-Symmetric Flows and Matchings // Mathematical Programming 2004. V. 100, Л» 3. P. 537-568.

11 Karger D. R., Lewine M. S. Finding Maximum Flows in Undirected Graphs Seems Easier Than Bipartite Matching // Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. New York. ACM Press, 1998. P. 69-78.

Lomonosov M V. Combinatorial Approaches to Multiflow Problems // Discrete Applied Math. V. 11, № 1. P. 1-S4.

13Ibaraki T., Karzanov A. V., Nagamochi Я. A Fist Algorithm for Finding a Maximum fVee Multiflow in an Inner Eulerian Network and Some Generalizations // Combinatories. 1998. V. 18, № 1. P. 61-83.

Основные методы исследования

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

Научная новизна

Результаты работы являются новыми. Основными среди них являются следующие:

1) Предложен алгоритм с оценкой времени 0(тт(тпк^п,п3)), находящий в заданном кососимметрическом графе кратчайший регулярный путь между заданной парой вершин.

2) Предложены алгоритмы, находящие целочисленный косо-симметрический поток минимальной стоимости за время 0(к тш(ш1о§п,п2)) и 0{ф(п,тп) + тш(тпк^п,п3)) (где к обозначает величину искомого потока, а ф(п',т') — сложность задачи о целочисленной циркуляции минимальной стоимости в стандартной направленной сети с п' вершинами и т' дугами).

3) Предложен алгоритм с линейной оценкой времени, проверяющий заданный кососимметрический граф на регулярную ацикличность.

4) Построен алгоритм с оценкой времени О(пип(тп21о§п,п4)), находящий в заданном кососимметрическом графе регулярный цикл минимального среднего веса.

5) Доказано, что в простой кососимметрической сети произвольный ациклический целочисленный кососимметрический поток величины V имеет носитель размера 0(пу/ь).

6) Доказано, что в простой кососимметрической сети метод блокирующего потока находит максимальный целочисленный кососимметрический поток за время 0(тп2/3).

7) Предложен алгоритм, находящий максимальный целочисленный кососимметрический мультипоток в кососимметрической внутренне эйлеровой сети за время 0(тпп^(п2/тп) 1о§£) (где I обозначает количество терминалов).

Теоретическая и практическая ценность

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

Апробация результатов

Результаты диссертации докладывались на Первой Международной конференции «Computer Science in Russia» в Санкт-Петербурге (июнь 2006 г.), а также на Колмогоровском семинаре по сложности вычислений и сложности определений в МГУ им. М. В. Ломоносова (февраль 2005 г., октябрь 2005 г., май 2006 г., октябрь 2006 г.; руководители семинара: Н. К. Верещагин, A. JI. Семёнов, А. Е. Ромащенко и А.Х. Шень).

Публикации

Основные результаты опубликованы в 5 работах, список которых приведен в конце автореферата [1-5].

Структура и объем диссертации

Диссертация состоит из введения, 9 глав, списка литературы и предметного указателя. Полный объем диссертации — 114 страниц, список литературы содержит 49 наименований.

Содержание работы

Во введении дается краткий исторический обзор проблемы, приводятся известные результаты, перечисляются основные результаты диссертации.

В главе 1 вводятся основные определения, а также формулируется ряд стандартных теорем теории кососимметрических графов.

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

В главе 3 изучаются задачи о разыскании кратчайших регулярных путей в кососимметрических графах, приводится алгоритм с оценкой сложности 0(min(mnlogn,n3)).

Глава 4 посвящена теории стоимостных целочисленных кососиммет-рических потоков. Для задачи нахождения целочисленного кососиммет-рического потока минимальной стоимости приводятся алгоритмы с оценками сложности 0(к тт(т к^п, п2)) и 0(ф{п,т) + тш(г7тк^п,п3)).

В главе 5 изучается строение ациклических и регулярно ациклических кососимметрических графов, а также приводится алгоритм с линейной оценкой сложности, предназначенный для проверки регулярной ацикличности.

В главе 6 рассматривается задача о нахождении в кососимметриче-ской сети регулярного цикла минимального среднего веса. Для ее решения предлагается алгоритм с оценкой сложности 0(тш(тшг2к^п, п4)).

В главе 7 рассматривается задача о нахождении максимального целочисленного кососимметрического потока в простой кососимметриче-ской сети. Доказывается, что метод блокирующего потока решает данную задачу за время 0(тп2/3). Кроме того, показывается, что носитель целочисленного кососимметрического потока величины и в кососиммет-рической сети без параллельных дуг имеет размер 0(пу/у).

В главе 8 рассматривается задача о разложении многополюсного потока на слагаемые, отвечающие всевозможным парам источников и стоков. Для случая стандартных направленных и кососимметрических сетей приводятся алгоритмы, строящие искомое разложение за время 0(т^(п2/т)).

Глава 9 посвящена мультипотоковым задачам. Для случая внутренне эйлеровой кососимметрической сети приводится алгоритм, решающий задачу о максимальном целочисленном кососимметрическом мультипо-токе за время 0{тп \о%(п2/т)

Благодарности

Данная работа выполнена при поддержке грантов РФФИ № 03-0100475, 05-01-02803, 06-01-00122 и НШ 358.2003.1.

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

Автор признателен профессору Владимиру Андреевичу Успенскому, профессору Мати Рейновичу Пентусу, а также кандидату физико-математических наук Александру Шеню за конструктивные предложения, высказанные ими во время докладов автора на семинарах кафедры математической логики и теории алгоритмов.

Публикации автора по теме диссертации

[1] Бабенко М. А. Быстрый алгоритм построения декомпозиции многополюсных потоков // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2006. № 2. С. 53-55.

[2] Бабенко М. А. О потоках в простых двунаправленных и кососим-метрических сетях // Проблемы передачи информации. 2006. Т. 42. № 4. С. 104-120.

[3] Бабенко М. А. О потоковых задачах в кососимметрических и двунаправленных сетях // М.: МГУ. 2007. Деп. в ВИНИТИ 26.01.2007 № 71-В2007. 96 с.

[4] Бабенко М. А. Об одном приложении теории ациклических косо-симметрических графов // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2007. № 2. С. 65-66.

[5] Babenko М. A. Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure // Lecture Notes in Computer Science. 2006. V. 3967. P. 23-34.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать 5,ОЗ. О")

Формат 60 х 90 1/16. Усл. печ. л. О,

Тираж 100 экз. Заказ 12.

Введение

1. Основные определения, обозначения и свойства

1.1. Обозначения.

1.2. Потоки в сетях.

1.3. Декомпозиции потоков.

1.4. Минимаксные потоковые теоремы.

3.2. Фрагменты, ростки и барьеры.32

3.3. Алгоритм поиска регулярного пути.34

3.4. Реализация алгоритма поиска регулярного пути.36

3.5. Консервативность и регулярная консервативность.38

3.6. Алгоритм поиска кратчайшего регулярного пути.41

3.7. Реализация алгоритма поиска кратчайшего регулярного пути.44

3.8. Случай произвольных длин дуг.50

4. Стоимостные потоки в кососимметрических сетях 53

4.1. Введение .53

4.2. Алгоритм дополнения вдоль путей минимальной стоимости.54

4.3. Алгоритм сведения к задаче в стандартной направленной сети.59

5. Ациклические кососимметрические графы 62

5.1. Введение .62

5.2. Ациклические графы.63

5.3. Регулярно ациклические графы.64

5.4. Приложение к теории паросочетаний.66

5.5. Ациклическая декомпозиция.67

5.6. Алгоритм проверки регулярной ацикличности. 67

5.7. Характеризация в терминах сильно связных компонент. 72

6. Задача о цикле минимального среднего веса 75

6.1. Введение . 75

6.2. Общий подход. 76

6.3. Минимальные средние регулярные циклы. 78

7. Потоки в простых кососимметрических сетях 81

7.1. Введение .81

7.2. Оценка мощности носителя ациклического потока.82

7.3. Оценка величины потока.86

7.4. Метод блокирующего потока.86

8. Декомпозиция многополюсных потоков 88

8.1. Введение . 88

8.2. Декомпозиция в направленных графах. 89

8.3. Декомпозиция в кососимметрических графах. 91

9. Мультипотоки в двунаправленных и кососимметрических сетях 94

9.1. Введение . 94

9.2. Мультипотоки в кососимметрических сетях. 97

9.3. Случай двух пар терминалов. 99

9.4. Случай трех пар терминалов.101

9.5. Общий случай.104

9.6. Оценка времени работы.105

Литература 108

Предметный указатель 112

Введение

Основные понятия

Данная работа относится к теории комбинаторной оптимизации. В качестве основного объекта рассмотрения выступают графы: стандартные (направленные и ненаправленные), а также нестандартные (кососимметрические и двунаправленные).

Приведем вначале основные определения, касающиеся двух стандартных типов графов: направленных и ненаправленных. Направленный граф G представляет собой четверку (V, A, tail, head), где V — конечное множество вершин, А — конечное множество дуг, а отображения tail: A-+V, head: А —» V сопоставляют каждой дуге а е А пару различных вершин: начало tail(a) и конец head(a). Если head(ai) = head(<22) и tail(ai) = tail(a2), то дуги а\ и аг называют параллельными. В случае когда не возникает неоднозначностей в понимании, дугу, идущую из вершины и в вершину v, мы будем обозначать через (u,v). Более того, при записи функций от дуг графа будем опускать двойные скобки и писать f(u,v) вместо полного варианта f((u,v)).

Маршрутом Р из s в t (или, для краткости, s-t маршрутом) в направленном графе G называют последовательность вершин и дуг вида

P=(s = vq, ах, vx,., vk-h ak, vk = t), где Vi — вершины (0 ^ i ^ k), а» — дуги, tail(aj) = V{-1, head(aj) = V{ (1 < г ^ k).

В случае если все дуги щ в последовательности Р различны, то маршрут Р будем называть простым по дугам (или путем); в случае если Vi ф Vj для всех 0 < i < j < k и vq ф Vi, vk ф Vi для всех 0 < г < к, то простым по вершинам (или простым путем). Отметим, что концы простого пути могут совпадать. Маршрут Р будем называть циклическим, если s = t; циклический маршрут, являющийся (простым) путем, будем называть (простым) циклом.

Переходим теперь к понятию ненаправленного графа. Каждый такой граф задается тройкой (V,E,ends), где V — конечное множество вершин, Е — конечное множество ребер, а отображение ends задает для каждого ребра ее Е множество ends(e) = состоящее из двух различных вершин и, v (концов е). В случае если ends(ei) = ends(e2), то ребра е\ и ег называют параллельными. Ребро, соединяющее вершины uviv, мы обозначаем через {и, v}.

Понятие маршрута переносится на случай ненаправленного графа следующим образом. Маршрутом Р из set (s-t маршрутом) в ненаправленном графе G называют последовательность вершин и ребер вида

Р ={vo,e1,v1,.,vk-hek,vk),

Рис. 1. Пример двунаправленного графа где Vi — вершины (0 < i ^ к), ei — ребра, ends(ej) = {«i-i,!;,-} (1 ^ г < к).

Если все ребра е* в последовательности Р различны, то маршрут Р будем называть простым по ребрам (или путем). Определения понятий простого по вершинам маршрута (или, иначе говоря, простого пути), циклического маршрута, а также цикла и простого цикла полностью повторяют соответствующие определения для случая направленного графа.

Понятие двунаправленного графа возникло в работах Эдмондса и Джонсона при решении специального класса задач целочисленного программирования [19, 35, 45]. Двунаправленный граф G — это четверка (V, Е, ends,со). Здесь V — конечное множество вершин, Е — конечное множество двунаправленных ребер. Отображение ends определено на множестве Е и сопоставляет каждому ребру е Е Е двухэлементное мультимножество ends(e) = {u,v}, где и, v — вершины (не обязательно различные), называемые концами е. Наконец, для каждого ребра е Е Е и вершины v Е ends(e) определено значение u(e,v) Е {+1,-1}, называемое направлением ребра е в вершине v. В случае если ш(е, v) = +1, то говорят, что ребро е входит в v, иначе говорят, что ребро е выходит из v. Отметим, что возможен случай ends(e) = {v, и}; такие ребра е называют двунаправленными петлями. В случае uj(e,v) = +1, петля е дважды входит в и; иначе е дважды выходит из v.

Итак, каждое ребро е Е Е соединяет две вершины и, v Е ends(e) и принадлежит к одному из следующих трех типов:

1) направленное ребро (или дуга), которое выходит из одного конца и заходит в другой (при этом и ф и);

2) ребро, входящее в оба конца;

3) ребро, выходящее из обоих концов.

Пример двунаправленного графа представлен на рис. 1.

Маршрут из s в t (s-t маршрут) в двунаправленном графе G представляет собой чередующуюся последовательность вершин и ребер где Vi — вершины (0 < г ^ k), ej — двунаправленные ребра, ends(ej) = {vi-\,vi} (1 ^ г ^ к), и для всех 0 < i < к ребра е*, ei+1 образуют транзитную пару в вершине Vi, то есть одно из ребер е*, e;+i входит в V{, а другое выходит из Uj.

1)

P=(s = v0, еь vi,., ек, vk = t),

Как и в случае обычных графов, маршрут без повторяющихся ребер называют путем. Понятие простого пути вводится для двунаправленных графов точно так же, как и для направленных и ненаправленных. Маршрут (1), в котором s = t, и ребра е\,ек образуют транзитную пару в вершине s, называют циклическим. Циклический маршрут, являющийся (простым) путем, называют (простым) циклом.

Направленный граф можно считать двунаправленным, превратив каждую дугу а = (u,v) исходного графа в ребро еа с множеством концов {u,v} и положив ш(еа>и) := —1, и>(еа,v) := +1. При этом семейство маршрутов исходного направленного графа и семейство маршрутов полученного двунаправленного графа находятся в естественном взаимно однозначном соответствии.

Для произвольного графа G мы будем писать Vg (соответственно Ас, Ее) для обозначения его множества вершин (соответственно дуг, ребер). Аналогично через Vp, Ар, Ер будут обозначаться мультимножества вершин, дуг и ребер произвольного маршрута Р.

Для двунаправленных графов существует также альтернативный и отчасти более удобный язык их описания — так называемые кососимметрические графы. Определение кососимметрического графа было сформулировано в работах Гольдберга и Карзанова [25, 26], а также Татта [48] (где они получили название антисимметрических орграфов). Рассмотрим направленный граф G. Пусть задана пара биекций ay: Vg —<► Vg и о а '■ Ag —* Ас, обладающих следующими свойствами:

1) оу(оу(г;)) = v для всех v eVg и <тл(сгд(а)) = а для всех о 6 Ас',

2) oy(v) ^ v для всех v eVc и стд(а) ф а для всех а G Ас',

3) Ьеас1(<7л(а)) = oy(tail(a)) и tail(cr^(a)) = 0y(head(a)) для всех a G Ас

Тогда тройку (G,ov,(?a) будем называть кососимметрическим графом. Если это не вызывает разночтений, мы будем называть кососимметрическим и сам направленный граф G. В дальнейшем нам потребуется работать как с кососимметрическими, так и с обычными направленными графами. Для того, чтобы подчеркнуть отсутствие кососимметрической структуры у последних, будем называть их стандартными.

Пару отображений (ау,<та) мы скомбинируем в одно отображение a: Vg U Ас * VgUAq. Отображения а, оу, о а будем называть отображениями симметрии графа. Для удобства записи мы будем использовать обозначение х' для образа а(х) (как по отношению к вершинам, так и к дугам). Элемент х' (вершину или дугу) будем называть симметричным к элементу х. Множество вершин Vg тогда разбивается на не пересекающиеся пары симметричных вершин; также дело обстоит и с множеством дуг. Симметрия естественным образом переносится на подмножества вершин и дуг графа. Из определения следует, что если в кососимметрическом графе G присутствуют дуги, соединяющие пару симметричных вершин v, г/, то таких дуг непременно четное число, и они разбиваются на пары симметричных.

Соответствие между двунаправленными и кососим-метрическими графами

Покажем теперь, как введенное понятие кососимметрического графа связано с понятием двунаправленного (см. также [26, раздел 2]). Пусть X — произвольное множество вершин двунаправленного графа G. Рассмотрим следующее преобразование: для всех вершин v G X и ребер е, инцидентных v, обратим направление ребра е в вершине v. Данное преобразование не меняет множества маршрутов в G. Мы будем называть двунаправленные графы G\, G2 эквивалентными, если G2 можно получить из G\, применяя вышеуказанное преобразование для некоторого множества X.

Пусть задан кососимметрический граф G. Выберем произвольное упорядоченное разбиение ж = (Vi, V2) множества Vq (то есть Va — Vi U V2, V\ П V2 = 0), такое что V{ = V2. Тогда по G и 7г можно построить двунаправленный граф G с множеством вершин V\ следующим способом: ребра G будут соответствовать парам симметричных дуг в G. Точнее, каждая пара симметричных дуг а, а' в G порождает одно ребро е в G, соединяющее вершины u,v Е V\, так что:

1) ребро е идет из и в и, если одна из дуг а, а' идет из и в г; (а другая из v' в и');

2) ребро е выходит из обоих концов и, v, если одна из дуг а, а' идет из и в и' (а другая из г; в и');

3) ребро е входит в оба конца и, v, если одна из дуг а, а' идет ю и' в v (а другая из v' в и).

В частности, ребро е будет петлей, если дуги а, а' соединяют пару симметричных вершин.

Обратно, двунаправленный граф G порождает кососимметрический граф G с отображением симметрии а следующим образом. Для каждой вершины v G Vq возьмем ее копию a(v) и образуем множество V~ := {а(и) \v EVg}. Положим Vq :=Vq U V~. Для каждого ребра е 6 Eg, соединяющего вершины иив, построим две симметричные дуги а, а' € Aq, чтобы выполнялись указанные выше условия 13. Пример соответствия между двунаправленными и кососимметрическими графами представлен на рис. 2.

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

Существует также соответствие между маршрутами в G и маршрутами в G. А именно, пусть т обозначает отображение VgUAq на VgUEg,, склеивающее пары симметричных вершин и дуг. Каждый маршрут Р = (г^о, а\, V\,., a*, Vk) в G индуцирует последовательность т(Р) := (т(г> о), r(aj), t(vi), ., т(йк), т(г^)) вершин и ребер из G. Легко видеть, что т(Р) будет маршрутом в G.

В приложениях особенно важную роль играют не произвольные маршруты в графах, а пути. Если в направленном графе вершина t достижима из вершины s по

У1 а) Двунаправленный граф G б) Соответствующий кососим-метрический граф G

Рис. 2. Соответствие между двунаправленными и кососимметрическими графами некоторому маршруту, то t также достижима по некоторому пути (даже простому). В противоположность этому, в двунаправленном графе наличие s-t маршрута не влечет за собой наличие s-t пути. Проверка наличия s-t пути в двунаправленном графе, вообще говоря, представляет собой достаточно сложную задачу.

Будем называть маршрут нетривиальным, если он содержит хотя бы одно ребро (или дугу). Путь в кососимметрическом графе будем называть регулярным, если в нем не встречается пары симметричных дуг (при этом симметричные вершины встречаться могут). По каждому нетривиальному маршруту р = (wq,е\,w\,.,е*,wk) в графе G можно построить последовательность т(Р) := (vo,ai,vi,.,ak,Vk) из вершин и дуг графа G по следующему правилу:

1) если ребро t\ выходит из Wq (соответственно входит в Wq), то положим v0:=W0 (соответственно Vo := w'0);

2) для всех 1 ^ г ^ к если ребро е{ выходит из w^i, то в качестве щ возьмем дугу из множества т-1(е*), которая выходит из кроме того положим V{ :=

3) для всех 1 ^ i ^ к если ребро е; входит в Wj-i, то в качестве а* возьмем дугу из множества r1(ej), которая выходит из х; кроме того положим Vi := head(aj).

В случае когда ребро е* представляет собой петлю, то дуги из т-1(е*) оказываются параллельными, поэтому дуга щ выбирается из двух возможных произвольным образом. Несложно показать, что для любого нетривиального маршрута Р в G справедливы свойства:

1) т(Р) представляет собой маршрут в G, причем т(т(Р)) = Р\

2) Р представляет собой путь (то есть простой по ребрам маршрут), если и только если т (Q) представляет собой регулярный путь.

Тем самым, отображения т, т задают взаимно однозначное (с точностью до выбора представителя из пары параллельных дуг вида (v, v'), как указано выше) соответhead(aj); ствие между семействами нетривиальных маршрутов (соответственно нетривиальных путей) в G и нетривиальных маршрутов (соответственно нетривиальных регулярных путей) в G.

Как будет показано далее в главе 2, в терминах кососимметрических графов оказывается возможным описать широкий спектр задач комбинаторной оптимизации (паросочетания в графах общего вида, Т-соединения, ^паросочетания, /-факторы, упаковки Т-путей и другие). Тем самым, теория кососимметрических графов служит удобным обобщающим инструментом, а алгоритмы для задач на кососимметрических графах находят множество применений.

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

Первый класс составляют задачи, связанные с разысканием в кососимметри-ческом графе G кратчайшего регулярного пути между выбранной парой вершин. Длины дуг могут быть произвольными (в том числе отрицательными) числами, а длиной пути называется сумма длин составляющих его дуг. При этом предполагается, что длины симметричных дуг равны, и в графе отсутствуют регулярные циклы отрицательной длины. В работе Гольдберга и Карзанова [25] представлен алгоритм с оценкой О (тп2 log п). (Здесь и далее через п обозначается число вершин графа, а через т — число ребер или дуг. При этом предполагается, что 2п ^ т ^ п2). Мы улучшаем данную оценку до 0(min(mnlogn, п3)). Этому вопросу будет посвящена глава 3.

Второй класс образуют задачи, связанные с циклической структурой кососимметрических и двунаправленных графов. Мы обобщаем понятие ацикличности на случай кососимметрических графов. При этом оно распадается на два: обычная ацикличность (отсутствие циклов) и регулярная ацикличность (отсутствие регулярных циклов). В главе 5 для каждого из этих типов мы устанавливаем структурные результаты, а также предъявляем алгоритмы, позволяющие выполнить проверку на принадлежность данного графа к указанному типу за линейное время. Структурные результаты для случая регулярной ацикличности позволяют дать короткое доказательство известной в теории паросочетаний теоремы Коцига [34] (утверждающей, что если в ненаправленном графе G существует и единственно совершенное паросо-четание М, то в G есть мост, причем М содержит хотя бы один из мостов G).

Среди проблем второго класса следует также упомянуть задачу о разыскании в кососимметрическом графе G регулярного цикла минимального среднего веса. (Предполагается, что дугам графа приписаны вещественные веса, при этом веса симметричных дуг равны. Под средним весом цикла понимается отношение суммы весов его дуг к их количеству.) Для стандартных направленных графов эта задача изучалась Карпом [32] (алгоритм с оценкой 0(тп)), а для ненаправленных — Барахоной [16] (алгоритм с оценкой 0(min(m2nlogn, тп3))). Задача на кососимметрическом графе обобщает обе упомянутые проблемы и, как мы показываем в главе 6, может быть решена за время 0(min(mn2logn,n4)). В частности, мы улучшаем оценку Барахоны.

Третий класс складывается из потоковых и мультипотоковых задач. В главе 4 рассматривается проблема нахождения в кососимметрических сетях целочисленных кососимметрических потоков минимальной стоимости; для ее решения предлагается два алгоритма. Оценка сложности первого составляет 0(kmm(m\ogn,п2)), где к — величина потока. Второй алгоритм имеет оценку сложности 0(ф(п, т) + min(mnlogn, п3)), где ф(п', т!) обозначает сложность задачи о целочисленной циркуляции минимальной стоимости в стандартной направленной сети с п' вершинами и т' дугами.

В главе 7 мы изучаем случай простых кососимметрических сетей, то есть косо-симметрических графов, в которых каждой дуге приписана единичная пропускная способность, и параллельные дуги отсутствуют. Для стандартного направленного случая потоковая задача в простых сетях изучалась Карзановым, Эвеном, Таржа-ном [б, 20]. Был получен алгоритм со временем работы 0(vmn(mn2^, тп3/2)). Для двунаправленных сетей оценка сложности 0(т3/2) была получена Габовым [22]. В наших построениях мы опираемся на разработанный ранее Гольдбергом и Карзановым [26] метод блокирующих потоков в кососимметрических сетях. Мы устанавливаем для данного метода оценку сложности 0(тп2//3), тем самым полностью ликвидируя зазор между стандартным и кососимметрическим вариантами задачи. Ключевую роль играет доказываемое нами утверждение о том, что всякий ациклический целочисленный кососимметрический поток в кососимметрической сети без параллельных дуг имеет носитель размера 0{rty/v), где v — величина потока (аналог этого утверждения для стандартных направленных сетей был получен Каргером и Левиным [33]).

В главе 8 изучается вопрос о построении в стандартной направленной сети разложения многополюсного потока на слагаемые, отвечающие всевозможным парам источников и стоков. Предлагаемый алгоритм имеет оценку сложности 0(m\og(n2/т)) (в предположении, что число источников и стоков ограничено константой). Также рассматривается обобщение на случай кососимметрических сетей.

В главе 9 изучаются целочисленные мультипотоковые задачи в кососимметрических сетях. В общей постановке эти проблемы являются NP-трудными, поэтому мы ограничиваемся классом внутренне сбалансированных сетей (то есть таких, в которых для любой внутренней вершины v суммы пропускных способностей дуг, входящих вии выходящих из v, равны). Ранее задача о максимальном мультипо-токе изучалась для случая ненаправленных и стандартных направленных сетей в работе Ибараки, Карзанова, Нагамочи [31]. Кососимметрический случай является одновременным обобщением как направленного, так и ненаправленного. Мы излагаем алгоритм для нахождения искомого целочисленного кососимметрического муль-типотока за время 0(mnlog(n2/m)\ogt) (где t обозначает количество терминалов). Эта оценка совпадает со временем работы известного алгоритма для направленного случая и улучшает другую известную оценку 0(тп2) для ненаправленного случая.

Благодарности

Данная работа выполнена при поддержке грантов РФФИ № 03-01-00475, 05-0102803, 06-01-00122 и НШ 358.2003.1.

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

Автор признателен профессору Владимиру Андреевичу Успенскому, профессору Мати Рейновичу Пентусу, а также кандидату физико-математических наук Александру Шеню за конструктивные предложения, высказанные ими во время докладов автора на семинарах кафедры математической логики и теории алгоритмов.

Автор глубоко благодарит своих родителей, Бабенко Александра Максимовича и Кашенкову Валентину Сергеевну за поддержку, оказанную во время написания работы.

1. Карзанов А. В. Алгоритм максимальной упаковки нечетнополюсных разрезов и его приложения // Сб.: Исследования по прикладной теории графов. Новосибирск: Наука СО. 1986. С. 126-140.

2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

3. Черкасский В. В. Решение задачи о многопродуктовом потоке в сети // Сб.: Экономика и математические методы. 1977. Т. 13, № 1. С. 143-151.

4. AhujaR. К., Goldberg A. V., OrlinJ. В., TarjanR. E. Finding Minimum-Cost Flows by Double Scaling // Mathematical Programming. 1992. V. 53, № 3. P. 243-266.

5. Anstee R. P. An Algorithmic Proof of Tutte's F-Factor Theorem // Journal of Algorithms. 1985. V. 6, № 1. P. 112-131.

6. Anstee R. P. A Polynomial Algorithm for B-Matchings: an Alternative Approach // Information Processing Letters 1987. V. 24, № 3. P. 153-157.

7. Babenko M. A. Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure // Lecture Notes in Computer Science. 2006. V. 3967. P. 23-34.

8. Barahona F. Reducing Matching to Polynomial Size Linear Programming // SIAM Journal on Optimization. 1993. V. 3. P. 688-695.

9. Bouchet A. Isotropic Systems // European Journal of Combinatorics. 1987. V. 8. P. 231-244.

10. Bouchet A. Matchings and Delta-Matroids // Discrete Applied Mathematics. 1989. V. 24, № 16. P. 55-62.

11. Edmonds J., Johnson E. L. Matching, a Well-Solved Class of Integer Linear Programs // Combinatorial Structures and Their Applications, Calgary International Conference. NY: Gordon and Breach, 1970. P. 89-92.

12. Even S., Tarjan R. E. Network Flow and Testing Graph Connectivity 11 SIAM Journal on Computing. 1975. V. 4. P. 507-518.

13. Ford L., Fulkerson D. Flows in Networds. Princeton: Princeton University Press, 1962.

14. Gabow H. N. An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems // Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. 1983. V. 15. P. 448-456.

15. Gabow H. N., Kaplan H., Tarjan R. E. Unique Maximum Matching Algorithms // Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing. 1999. P. 70-78.

16. Gabow H. N., Tarjan R. E. A Linear-Time Algorithm for a Special Case of Disjoint Set Union // Journal of Computer and System Sciences. 1986. V. 30. P. 209-221.

17. Goldberg A. V., Karzanov A. V. Path Problems in Skew-Symmetric Graphs // Combinatorics 1996. V. 16, № 3. P. 353-382.

18. Goldberg A. V., Karzanov A. V. Maximum Skew-Symmetric Flows and Matchings // Mathematical Programming. 2004. V. 100, № 3. P. 537-568.

19. Goldberg A., Tarjan R. Solving Minimum-Cost Flow Problems by Successive Approximation // Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing. NY: ACM Press, 1987. P. 7-18.

20. Goldberg A. V., Tarjan R. E. A New Approach to the Maximum-Flow Problem // Journal of ACM. 1988. V. 35, № 4. P. 921-940.

21. Goldberg A. V., Tarjan R. Е. Finding Minimum-Cost Circulations by Canceling Negative Cycles // Journal of ACM. 1989. V. 36, № 4. P. 873-886.

22. Goldberg A. V., Rao S. Beyond the Flow Decomposition Barrier // Journal of ACM. 1998. V. 45, № 5. P. 783-797.

23. Ibaraki Т., Karzanov A. V., Nagamochi H. A Fast Algorithm for Finding a Maximum Free Multiflow in an Inner Eulerian Network and Some Generalizations // Combinatorica. 1998. V. 18, № 1. P. 61-83.

24. Karp R. M. A Characterization of the Minimum Cycle Mean in a Digraph // Discrete Mathematics. 1978. V. 23. P. 309-311.

25. Karger D. R., Levine M. S. Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching // Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. NY: ACM Press, 1998. P. 69-78.

26. Kotzig A. On the Theory of Finite Graphs with a Linear Factor I // Mat.-Fyz. Casopis Slovensk. Akad. Vied. 1959. V. 9. P. 73-91.

27. Lawler E. L. Combinatorial Optimization: Networks and Matroids. NY: Holt, Rein-hart, and Winston, 1976.

28. Lomonosov M. V. Combinatorial Approaches to Multiflow Problems // Discrete Applied Mathematics. 1985. V. 11, № 1. P. 1-94.

29. Lovasz L. On Some Connectivity Properties of Eulerian Graphs // Acta Math. Akad. Sci. Hung. 1976. V. 28. P. 129-138.

30. Lovasz L. Matroid Matching and Some Applications // Journal of Combinatorial Theory, Series B. 1980. V. 28. P. 208-236.

31. Lovasz L. Selecting Independent Lines from a Family of Lines in a Space // Acta Scientiarum Mathematicarum (Szeged). 1980. V. 42, № 1-2. P. 121-131.

32. Lovasz L. The Matroid Matching Problem // Colloq. Math. Society. Janos Bolyai. 1981. V. 25. P. 495-517.

33. Jloeac JI., Пламмер M. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.

34. Mader W. Uber die Maximalzahl Kantendisjunkter A-Wege // Archiv der Mathe-matik (Basel). 1978. V. 30. P. 325-336.

35. Orlin J. A Faster Strongly Polynomial Minimum Cost Flow Algorithm // Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. NY: ACM Press, 1988. P. 377-387.

36. Oxley J. G. Matroid Theory. Oxford: Oxford University Press, 1992.

37. Schrijver A. Combinatorial Optimization. Berlin: Springer, 2003.

38. Sleator D. D., Tarjan R. E. A Data Structure for Dynamic Trees // Journal of Computer and System Sciences. 1983. V. 26, № 3. P. 362-391.

39. Tong P., Lawler E., Vazirani V. Solving the Weighted Parity Problem for Gammoids by Reduction to Graphic Matching // Progress in Combinatorial Optimization. 1982. P. 363-374.

40. Tutte W. T. Antisymmetrical Digraphs // Canadian Journal of Mathematics. 1967. V. 19. P. 1101-1117.

41. Whitney H. On the Abstract Properties of Linear Dependence // American Journal of Mathematics. 1935. V. 57. P. 509-533.Предметный указатель