Содержание к диссертации
Введение
1. Основные определения, обозначения и свойства 12
1.1. Обозначения 12
1.2. Потоки в сетях 13
1.3. Декомпозиции потоков 16
1.4. Минимаксные потоковые теоремы 18
2. Приложения к классическим задачам комбинаторной оптимизации 20
2.1. Паросочетания и fr-паросочетания 20
2.2. Т-соединения 23
2.3. Упаковки Т-путей 24
2.4. Гаммоиды и дельта-гаммоиды 25
2.5. Матроидные паросочетания в гаммоидах 28
3. Пути в кососимметрических и двунаправленных графах 30
3.1. Введение 30
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: А —> V, head: A—>V сопоставляют каждой дуге а Є Л пару различных вершин: начало tail(a) и конец head(a). Если head(ai) = ЬеаЛ(аг) и tail(ai) = tail(a2), то дуги ах и аг называют параллельными. В случае когда не возникает неоднозначностей в понимании, дугу, идущую из вершины и в вершину v, мы будем обозначать через (u,v). Более того, при записи функций от дуг графа будем опускать двойные скобки и писать f(u,v) вместо полного варианта f((u,v)).
Маршрутом Р из s в t (или, для краткости, s-t маршрутом) в направленном графе G называют последовательность вершин и дуг вида
P=(s = v0, ах, vx,..., vk-h ak, vk = t),
где Vi — вершины (0 ^ і ^ k), a» — дуги, tail(aj) = Vi-\, head(aj) = Vi (1 < і ^ k).
В случае если все дуги Oj в последовательности Р различны, то маршрут Р будем называть простым по дугам (или путем); в случае если Vi ф Vj для всех 0 < і < j < k и Vq ф Vi, vk ф Vi для всех 0 < г < к, то простым по вершинам (или простым путем). Отметим, что концы простого пути могут совпадать. Маршрут Р будем называть циклическим, если s = t; циклический маршрут, являющийся (простым) путем, будем называть (простым) циклом.
Переходим теперь к понятию ненаправленного графа. Каждый такой граф задается тройкой (V, 2?, ends), где V — конечное множество вершин, Е — конечное множество ребер, а отображение ends задает для каждого ребра є Є Е множество ends(e) = {u,v}, состоящее из двух различных вершин и, v (концов е). В случае если ends(ei) = ends(e2), то ребра е\ и ег называют параллельными. Ребро, соединяющее вершины ии!), мы обозначаем через {и, v}.
Понятие маршрута переносится на случай ненаправленного графа следующим образом. Маршрутом Р из set (s-t маршрутом) в ненаправленном графе G называют последовательность вершин и ребер вида
P=(v0,e1,vh...,vk-1,ek,vk),
Рис. 1. Пример двунаправленного графа
где Vi — вершины (0 < і ^ к), Єі — ребра, ends(e*) = {uj_i,u,} (1 < і < А;).
Если все ребра е* в последовательности Р различны, то маршрут Р будем называть простым по ребрам (или путем). Определения понятий простого по вершинам маршрута (или, иначе говоря, простого пути), циклического маршрута, а также цикла и простого цикла полностью повторяют соответствующие определения для случая направленного графа.
Понятие двунаправленного графа возникло в работах Эдмондса и Джонсона при решении специального класса задач целочисленного программирования [19, 35, 45]. Двунаправленный граф G — это четверка (V, Е, ends,со). Здесь V — конечное множество вершин, Е — конечное множество двунаправленных ребер. Отображение ends определено на множестве Е и сопоставляет каждому ребру є Є Е двухэлементное мультимножество ends(e) = {и, v}, где и, v — вершины (не обязательно различные), называемые концами е. Наконец, для каждого ребра е G Е и вершины v Є ends (є) определено значение u(e,v) Є {+1,-1}, называемое направлением ребра е в вершине v. В случае если и>(е, v) = +1, то говорят, что ребро е входит в v, иначе говорят, что ребро е выходит из v. Отметим, что возможен случай ends(e) = {i>,i>}; такие ребра е называют двунаправленными петлями. В случае uj(e,v) = +1, петля е дважды входит в v; иначе е дважды выходит из v.
Итак, каждое ребро є є Е соединяет две вершины и, v Є ends(e) и принадлежит к одному из следующих трех типов:
направленное ребро (или дуга), которое выходит из одного конца и заходит в другой (при этом и ф v);
ребро, входящее в оба конца;
ребро, выходящее из обоих концов.
Пример двунаправленного графа представлен на рис. 1.
Маршрут из s в t (s-t маршрут) в двунаправленном графе G представляет собой чередующуюся последовательность вершин и ребер
(1) P=(s = v0,e1,vu...,ek,vk = t),
где Vi — вершины (0 < г ^ к), е* — двунаправленные ребра, ends(ej) = {vi-\,vi\ (1 ^ г ^ к), я для всех 0 < г < к ребра є*, Єі+і образуют транзитную пару в вершине Vi, то есть одно из ребер Єі, Єі+і входит в v^ а другое выходит ИЗ Vi-
Как и в случае обычных графов, маршрут без повторяющихся ребер называют путем. Понятие простого пути вводится для двунаправленных графов точно так же, как и для направленных и ненаправленных. Маршрут (1), в котором s = t, и ребра еі,Єк образуют транзитную пару в вершине s, называют циклическим. Циклический маршрут, являющийся (простым) путем, называют (простым) циклом.
Направленный граф можно считать двунаправленным, превратив каждую дугу a = (u,v) исходного графа в ребро еа с множеством концов {u,v} и положив ш(еа,и) := —1, u(ea,v) := +1. При этом семейство маршрутов исходного направленного графа и семейство маршрутов полученного двунаправленного графа находятся в естественном взаимно однозначном соответствии.
Для произвольного графа G мы будем писать Vg (соответственно Ас, Ее) для обозначения его множества вершин (соответственно дуг, ребер). Аналогично через Vp, Ар, Ер будут обозначаться мультимножества вершин, дуг и ребер произвольного маршрута Р.
Для двунаправленных графов существует также альтернативный и отчасти более удобный язык их описания — так называемые кососимметрические графы. Определение кососимметрического графа было сформулировано в работах Гольдберга и Карзанова [25, 26], а также Татта [48] (где они получили название антисимметрических орграфов). Рассмотрим направленный граф G. Пусть задана пара биекций o~v ' Vg —» Vq и о а : Ас —* Ас, обладающих следующими свойствами:
av(o~v(v)) = v для всех и Є Vg и ал(сгд(а)) = а для всех о Є Ас',
o-y(v) ^ v для всех г; Є Vg и ад(а) ф а для всех а Є Ас;
head((7^(a)) = oy(tail(a)) и tail(cr^(a)) = oy(head(a)) для всех о Є Ac-
Тогда тройку {G,ov,oa) будем называть кососимметрическим графом. Если это не вызывает разночтений, мы будем называть кососимметрическим и сам направленный граф G. В дальнейшем нам потребуется работать как с кососимметрическими, так и с обычными направленными графами. Для того, чтобы подчеркнуть отсутствие кососимметрической структуры у последних, будем называть их стандартными.
Пару отображений (ау,^л) мы скомбинируем в одно отображение a: Vg U Ac —> VqUAg- Отображения a, ay, о а будем называть отображениями симметрии графа. Для удобства записи мы будем использовать обозначение х' для образа а(х) (как по отношению к вершинам, так и к дугам). Элемент х' (вершину или дугу) будем называть симметричным к элементу х. Множество вершин Vg тогда разбивается на не пересекающиеся пары симметричных вершин; также дело обстоит и с множеством дуг. Симметрия естественным образом переносится на подмножества вершин и дуг графа. Из определения следует, что если в кососимметрическом графе G присутствуют дуги, соединяющие пару симметричных вершин v, v', то таких дуг непременно четное число, и они разбиваются на пары симметричных.
Соответствие между двунаправленными и кососимметрическими графами
Покажем теперь, как введенное понятие кососимметрического графа связано с понятием двунаправленного (см. также [26, раздел 2]). Пусть X — произвольное множество вершин двунаправленного графа G. Рассмотрим следующее преобразование: для всех вершин v Є X и ребер е, инцидентных v, обратим направление ребра е в вершине v. Данное преобразование не меняет множества маршрутов в G. Мы будем называть двунаправленные графы G\, ( эквивалентными, если ( можно получить из G\, применяя вышеуказанное преобразование для некоторого множества X.
Пусть задан кососимметрический граф G. Выберем произвольное упорядоченное разбиение 7Г = (Vi, V2) множества Vq (то есть Vq — V\ U V2, V\ Г) V2 = 0), такое что V{ = V2. Тогда по G и 7г можно построить двунаправленный граф G с множеством вершин V\ следующим способом: ребра G будут соответствовать парам симметричных дуг bJG. Точнее, каждая пара симметричных дуг а, а' в G порождает одно ребро е в G, соединяющее вершины u,v Є Vi, так что:
ребро е идет из к в и, если одна из дуг а, а' идет из и в г; (а другая из г/ в и');
ребро е выходит из обоих концов и, v, если одна из дуг а, а' идет из и в и' (а другая из г; в и');
ребро е входит в оба конца и, v, если одна из дуг а, а' идет из и' в и (а другая
ИЗ Vі В и).
В частности, ребро е будет петлей, если дуги а, а' соединяют пару симметричных вершин.
Обратно, двунаправленный граф G порождает кососимметрический граф G с отображением симметрии а следующим образом. Для каждой вершины v Є Vq возьмем ее копию a(v) и образуем множество V~ := {(?{v) \ v Є Vq}. Положим Vq = Vq U V'~. Для каждого ребра є Є Eq, соединяющего вершины unv, построим две симметричные дуги а, а' Є Aq, чтобы выполнялись указанные выше условия 1-3. Пример соответствия между двунаправленными и кососимметрическими графами представлен на рис. 2.
Отметим, что каждый двунаправленный граф порождает один кососимметрический. В то же время, кососимметрический граф G порождает набор двунаправленных в зависимости от выбранного разбиения 7Г множества вершин, которое используется при построении G. Все получающиеся так графы G, однако, будут эквивалентны.
Существует также соответствие между маршрутами в G и маршрутами в G. А именно, пусть т обозначает отображение VgUAq на VqUEq, склеивающее пары симметричных вершин и дуг. Каждый маршрут Р = (vq, ai, V\,..., ot, 1) в G индуцирует последовательность т(Р):— (т(г»о),т{а\),t{v\),...,r(ajt),r{vkj) вершин и ребер из G. Легко видеть, что т(Р) будет маршрутом в G.
В приложениях особенно важную роль играют не произвольные маршруты в графах, а пути. Если в направленном графе вершина t достижима из вершины s по
(а) Двунаправленный граф G (б) Соответствующий кососим-
метрический граф G
Рис. 2. Соответствие между двунаправленными и кососимметрическими графами
некоторому маршруту, то t также достижима по некоторому пути (даже простому). В противоположность этому, в двунаправленном графе наличие s-t маршрута не влечет за собой наличие s-t пути. Проверка наличия s-t пути в двунаправленном графе, вообще говоря, представляет собой достаточно сложную задачу.
Будем называть маршрут нетривиальным, если он содержит хотя бы одно ребро (или дугу). Путь в кососимметрическом графе будем называть регулярным, если в нем не встречается пары симметричных дуг (при этом симметричные вершины встречаться могут). По каждому нетривиальному маршруту Р = {wq,е\,w\,...,е*,Wk) в графе G можно построить последовательность т(Р) := (vo,ai,vi,...,ak,Vk) из вершин и дуг графа G по следующему правилу:
если ребро Єї выходит из Wq (соответственно входит в Wq), то положим Vq := Wq (соответственно Vq := w'0);
для всех 1 ^ і ^ к если ребро е{ выходит из tUj_i, то в качестве сц возьмем дугу из множества т_1(е^), которая выходит из iUj_i; кроме того положим Vi := head(aj);
для всех 1 ^ і <: А; если ребро Єі входит в u>j_i, то в качестве щ возьмем дугу из множества т~1{еі), которая выходит из w'^; кроме того положим Vi := head(aj).
В случае когда ребро е* представляет собой петлю, то дуги из т-1(е*) оказываются параллельными, поэтому дуга 0 выбирается из двух возможных произвольным образом. Несложно показать, что для любого нетривиального маршрута Р в G справедливы свойства:
т(Р) представляет собой маршрут в G, причем т(т(Р)) = Р;
Р представляет собой путь (то есть простой по ребрам маршрут), если и только если т (Q) представляет собой регулярный путь.
Тем самым, отображения г, т задают взаимно однозначное (с точностью до выбора представителя из пары параллельных дуг вида (v, v'), как указано выше) соответ-
ствие между семействами нетривиальных маршрутов (соответственно нетривиальных путей) в G и нетривиальных маршрутов (соответственно нетривиальных регулярных путей) в G.
Как будет показано далее в главе 2, в терминах кососимметрических графов оказывается возможным описать широкий спектр задач комбинаторной оптимизации (паросочетания в графах общего вида, Т-соединения, fr-паросочетания, /-факторы, упаковки Т-путей и другие). Тем самым, теория кососимметрических графов служит удобным обобщающим инструментом, а алгоритмы для задач на кососимметрических графах находят множество применений.
Основную часть работы составляют главы 3-9. Рассматриваемые в них задачи могут быть разделены на следующие три класса.
Первый класс составляют задачи, связанные с разысканием в кососимметри-ческом графе G кратчайшего регулярного пути между выбранной парой вершин. Длины дуг могут быть произвольными (в том числе отрицательными) числами, а длиной пути называется сумма длин составляющих его дуг. При этом предполагается, что длины симметричных дуг равны, и в графе отсутствуют регулярные циклы отрицательной длины. В работе Гольдберга и Карзанова [25] представлен алгоритм с оценкой О(тп2 log я). (Здесь и далее через п обозначается число вершин графа, а через тп — число ребер или дуг. При этом предполагается, что 2п ^ тп ^ п2). Мы улучшаем данную оценку до 0(min(mnlogп,п3)). Этому вопросу будет посвящена глава 3.
Второй класс образуют задачи, связанные с циклической структурой кососимметрических и двунаправленных графов. Мы обобщаем понятие ацикличности на случай кососимметрических графов. При этом оно распадается на два: обычная ацикличность (отсутствие циклов) и регулярная ацикличность (отсутствие регулярных циклов). В главе 5 для каждого из этих типов мы устанавливаем структурные результаты, а также предъявляем алгоритмы, позволяющие выполнить проверку на принадлежность данного графа к указанному типу за линейное время. Структурные результаты для случая регулярной ацикличности позволяют дать короткое доказательство известной в теории паросочетаний теоремы Коцига [34] (утверждающей, что если в ненаправленном графе G существует и единственно совершенное паросо-четание М, то в G есть мост, причем М содержит хотя бы один из мостов G).
Среди проблем второго класса следует также упомянуть задачу о разыскании в кососимметрическом графе G регулярного цикла минимального среднего веса. (Предполагается, что дугам графа приписаны вещественные веса, при этом веса симметричных дуг равны. Под средним весом цикла понимается отношение суммы весов его дуг к их количеству.) Для стандартных направленных графов эта задача изучалась Карпом [32] (алгоритм с оценкой 0(тп)), а для ненаправленных — Барахоной [16] (алгоритм с оценкой 0(тт(т?пlogп,тп3))). Задача на кососимметрическом графе обобщает обе упомянутые проблемы и, как мы показываем в главе 6, может быть решена за время 0(min(mn2 logп,п4)). В частности, мы улучшаем оценку Барахоны.
Третий класс складывается из потоковых и мультипотоковых задач. В главе 4 рассматривается проблема нахождения в кососимметрических сетях целочис-
ленных кососимметрических потоков минимальной стоимости; для ее решения предлагается два алгоритма. Оценка сложности первого составляет 0(kmm(m\ogn,п2)), где к — величина потока. Второй алгоритм имеет оценку сложности 0(ф(п, т) + min(mnlogп,п3)), где ф(п',т') обозначает сложность задачи о целочисленной циркуляции минимальной стоимости в стандартной направленной сети с п' вершинами и т' дугами.
В главе 7 мы изучаем случай простых кососимметрических сетей, то есть косо-симметрических графов, в которых каждой дуге приписана единичная пропускная способность, и параллельные дуги отсутствуют. Для стандартного направленного случая потоковая задача в простых сетях изучалась Карзановым, Эвеном, Таржа-ном [б, 20]. Был получен алгоритм со временем работы 0(min(mn2//3, m3/2)). Для двунаправленных сетей оценка сложности 0(т3/2) была получена Габовым [22]. В наших построениях мы опираемся на разработанный ранее Гольдбергом и Карзановым [26] метод блокирующих потоков в кососимметрических сетях. Мы устанавливаем для данного метода оценку сложности 0(тп2//3), тем самым полностью ликвидируя зазор между стандартным и кососимметрический вариантами задачи. Ключевую роль играет доказываемое нами утверждение о том, что всякий ациклический целочисленный кососимметрический поток в кососимметрической сети без параллельных дуг имеет носитель размера 0{riy/v), где v — величина потока (аналог этого утверждения для стандартных направленных сетей был получен Каргером и Левиным [33]).
В главе 8 изучается вопрос о построении в стандартной направленной сети разложения многополюсного потока на слагаемые, отвечающие всевозможным парам источников и стоков. Предлагаемый алгоритм имеет оценку сложности 0(m\og(n2/m)) (в предположении, что число источников и стоков ограничено константой). Также рассматривается обобщение на случай кососимметрических сетей.
В главе 9 изучаются целочисленные мультипотоковые задачи в кососимметрических сетях. В общей постановке эти проблемы являются NP-трудными, поэтому мы ограничиваемся классом внутренне сбалансированных сетей (то есть таких, в которых для любой внутренней вершины v суммы пропускных способностей дуг, входящих в г; и выходящих из v, равны). Ранее задача о максимальном мультипо-токе изучалась для случая ненаправленных и стандартных направленных сетей в работе Ибараки, Карзанова, Нагамочи [31]. Кососимметрический случай является одновременным обобщением как направленного, так и ненаправленного. Мы излагаем алгоритм для нахождения искомого целочисленного кососимметрического муль-типотока за время 0(mnlog(n2/m)\ogt) (где t обозначает количество терминалов). Эта оценка совпадает со временем работы известного алгоритма для направленного случая и улучшает другую известную оценку 0(тп2) для ненаправленного случая.
Благодарности
Данная работа выполнена при поддержке грантов РФФИ № 03-01-00475, 05-01-02803, 06-01-00122 и НШ 358.2003.1.
Автор выражает глубокую признательность доктору физико-математических наук, главному научному сотруднику Александру Викторовичу Карзанову за постановку задач, подробные обсуждения и множество полезных идей. Автор благодарен
научному руководителю доктору физико-математических наук, профессору Николаю Константиновичу Верещагину за постоянное внимание к работе.
Автор признателен профессору Владимиру Андреевичу Успенскому, профессору Мати Рейновичу Пентусу, а также кандидату физико-математических наук Александру Шеню за конструктивные предложения, высказанные ими во время докладов автора на семинарах кафедры математической логики и теории алгоритмов.
Автор глубоко благодарит своих родителей, Бабенко Александра Максимовича и Кашенкову Валентину Сергеевну за поддержку, оказанную во время написания работы.
Минимаксные потоковые теоремы
Пусть N = (G, с) — направленная сеть, s Є VQ — источник, t Є VQ — сток. Нас будут интересовать следующие два вопроса: 1) Каково необходимое и достаточное условие максимальности заданного потока в сети N1 2) Какова комбинаторная минимаксная формула, выражающая величину максимального потока в сети iV? Ответы на оба этих вопроса были даны еще в середине прошлого века в работах Форда и Фалкерсона. Критерий максимальности потока в терминах остаточной сети звучит следующим образом: Теорема 1.4.1 (Форд-Фалкерсон [21]). Поток f в направленной сети N имеет максимальную величину, если и только если в графе остаточной сети Nf не существует s пути. Аналогичный результат для случая кососимметрической сети выглядит так: Теорема 1.4.2 (Татт [48]). Целочисленный кососимметрический поток f в косо-симметрической сети N имеет максимальную величину, если и только если в расщепленном графе остаточной сети S(Nf) не существует регулярного s-s пути. Для формулировки минимаксного результата введем следующее дополнительное определение. Будем называть s разрезом любое множество вершин А, такое что s Є A, t . А. Пропускной способностью разреза А будем называть значение с(6"1(А)). Теорема 1.4.3 (Форд-Фалкерсон [21]). Величина максимального s потока в направленной сети равна минимальной пропускной способности s разреза в ней. Сформулируем теперь теорему о нечетном барьере, играющую в теории косо-симметрических потоков роль, аналогичную теореме 1.4.3 для стандартных направленных потоков. Пусть в кососимметрическои сети N = (G, с) выделены источник S и сток s .
Для пары подмножеств X, У С VG будем обозначать через с(Х, У) сумму пропускных способностей дуг, идущих из X в У. Предположим, что заданы множества вершин A,A ,M,Bi,...,Bk (возможен случай к = 0), такие что: Тогда набор В — (A,M;Bi,...,Bk) будем называть нечетным s-баръером. Множества ВІ называют нечетными фрагментами, а числа с(А, ВІ) — рангами фрагментов ВІ. Пропускной способностью В называется значение c(B):=c(A,VG-A)-k. Аналог теоремы 1.4.3 для кососимметрических сетей выглядит так: Теорема 1.4.4 (Татт [48]). Величина максимального целочисленного кососиммет-рического s-s потока в кососимметрическои сети равна минимальной пропускной способности нечетного s-баръера в ней. Приложения к классическим задачам комбинаторной оптимизации
Одним из важных приложений теории классических потоков в направленных сетях является возможность записать в потоковых терминах задачу о максимальном паросочетании в двудольном графе. Напомним, что паросочетанием М в ненаправленном графе G называют такое множество ребер G, что любая вершина G оказывается инцидентна не более одному ребру из М. Те вершины G, которые инцидентны ровно одному ребру из М, называют покрытыми М. Если паросочетание покрывает все вершины графа, то его называют совершенным. Задача о максимальном паросочетании состоит в нахождении в заданном графе паросочетания максимальной мощности. Ненаправленный граф G называется двудольным, если найдутся подмножества X,Y С VG, такие что VG = X U Y, 7GP0 = 1G{Y) — 0- (Здесь и далее запись АиВ будет обозначать, что АПВ = 0.) Множества X, Y называются долями графа (они определены не однозначно). Двудольные графы без параллельных ребер можно также представлять в виде троек G = (X, У, Е), где X,Y— доли, Е С X xY — множество ребер. (При этом, конечно, мы заранее фиксируем некоторое разбиение множества вершин на доли.) В случае двудольного графа задача о максимальном паросочетании оказывается сводящейся к задаче о максимальном потоке. А именно, построим по двудольному графу G = (X, Y, Е) вспомогательную направленную сеть G с множеством вершин Vd:=XUYU{s,t}, где s, t — пара новых вершин, которые будут играть роль источника и стока соответственно. Для всех х Є X добавим дугу (s, х), а для всех у Є У — дугу (у, t). Наконец, для каждого ребра {х,у} Є Е, где х Є X, у Є Y, добавим дугу (х,у). Дуги вида (s, х) и (у, t) будем называть вспомогательными, а дуги вида (х, у) — основными. Пропускные способности всех дуг положим равными 1. Пример построения сети G по графу G приведен на рис. 2.1. Сведение задачи о максимальном паросочетании в двудольном графе к задаче о максимальном потоке в направленной сети Рассмотрим какой-либо целочисленный поток / в сети G. Разложим по теореме 1.3.1 этот поток в декомпозицию. Все скаляры этой декомпозиции равны 1. Поскольку граф G ациклический, то циклов в этой декомпозиции быть не может. Более того, каждый s путь в ней имеет вид Скажем, что пути Рху соответствует ребро {х, у} графа G. Тогда легко видеть, что взяв множество ребер, отвечающих путям из декомпозиции /, мы получим паросо-четание Mf в G, причем М/ = val(/). Более того, это соответствие между целочисленными потоками в G и паросочетаниями в G является взаимно однозначным. Тем самым, получено искомое сведение к задаче о максимальном целочисленном потоке. Можно также рассмотреть вариант, когда ребрам графа G назначены стоимости w: EG — М, а задача состоит в нахождении паросочетания, имеющего минимальную стоимость среди паросочетании, имеющих максимальную мощность. Перенесем функцию w на множество основных дуг G, а стоимости вспомогательных дуг положим равными 0. Тогда описанное выше соответствие между потоками и паросочетаниями будет сохранять стоимость, поэтому задача может быть решена путем нахождения в сети G целочисленного потока / максимальной величины val(/) и минимальной СТОИМОСТИ W /. В случае если граф G не является двудольным, сведение задачи о максимальном паросочетании в нем к потоковой задаче в направленной сети, по-видимому, невозможно. Однако оказывается возможным получить сведение к задаче в кососимметри-ческой сети. Итак, пусть G — произвольный ненаправленный граф. Построим косо-симметрическую сеть G следующим образом. Возьмем для каждой вершины v Є VQ ее симметричную копию v1.
Матроидные паросочетания в гаммоидах
Еще одна задача комбинаторной оптимизации, которая может быть решена с помощью теории кососимметрических потоков, формулируется следующим образом. Пусть М = {Е,1) — матроид. Пусть также задано семейство V, членами которого служат не пересекающиеся пары элементов Е. Назовем множество X С Е допустимым (или матроидным паросочетанием), если оно независимо относительно М и представляется в виде объединения некоторого набора пар из V. Задача о максимальном матроидном паросочетании состоит в нахождении допустимого множества максимальной мощности (см. также [41, 40, 38]).
В общей постановке (при условии, что матроид М задан оракулом, проверяющим независимость) задача о матроидном паросочетании не может быть решена за полиномиальное время [40] (интересно отметить, что этот результат не зависит от истинности гипотезы Р ф NP). В случае если матроид является линейным, то полиномиальный алгоритм существует [39], однако является довольно сложным. Мы далее опишем простой алгоритм решения для случая, когда М — гаммоид.
А именно, пусть М порождается направленным графом G с выделенным источником s и стоком t. Будем считать, что Sm(s) = 50Ut(i) = 0. Пусть также задано некоторое семейство V пар дуг вида {а, Ь} С 50ut(s). Построим двунаправленный граф G следующим образом. В качестве множества вершин G возьмем VG — {s}. Каждую дугу а Є I{VG — {s}) перенесем в G, обратив ее направление и преобразовав ее в двунаправленное ребро еа, выходящее из head(a) и заходящее в tail(a) (такие ребра мы будем называть основными). Для каждой пары дуг {а, Ь} Є V добавим в G двунаправленное ребро еаь, выходящее из вершин head (а) и head(fc) (такие ребра мы будем называть вспомогательными).
Рассмотрим произвольный целочисленный t-поток h в G. По теореме о декомпозиции его носитель можно представить в виде набора не пересекающихся по ребрам і-путей Pi,..., Pk в G. Каждый из этих путей содержит ровно одно вспомогательное ребро. Фиксируем путь Pi, пусть он содержит вспомогательное ребро ем, отвечающее дугам а = (s,u) и Ь — (s,v). Удаляя еаь из Р , мы разобьем РІ на два пути: t-u путь и t-v путь. Обращая направления этих путей в С? и добавляя к ним дуги а, Ь, мы преобразуем их в пару s путей Q},Qf в G. Проделав это преобразование со всеми Pi, получим набор пар путей Q\, Q\,..., Q\, Q\. Складывая индикаторы этих путей в G, получаем целочисленный s поток g в G, такой что suppg П Sout(s) — допустимое множество мощности val(ft). Более того, описанное соответствие между целочисленными -потоками в G и целочисленными s потоками в G, задающими допустимые множества, является взаимно-однозначным. Следовательно, решив задачу о максимальном целочисленном -потоке в G, мы заодно получим решение для задачи о матроидном паросочетании в гаммоиде М.
Эта идея может быть легко обобщена на стоимостной случай. А именно, пусть элементам носителя Е приписаны стоимости w: Е — R. Задача будет состоять в том, чтобы найти допустимое множество X минимальной стоимости w(X) среди всех допустимых множеств максимальной мощности. Для случая произвольного матроида М. эта задача, конечно, не имеет полиномиального решения. Более того, эффективного решения в классе линейных матроидов также не известно. Однако, если М — гаммоид, то изложенная конструкция дает сведение к задаче о стоимостном целочисленном двунаправленном потоке. Действительно, пусть задана весовая функция w: 50ut(s) — R. Тогда достаточно назначить в G основным ребрам нулевую стоимость, вспомогательным ребрам вида е0ь — стоимости w(a) + w(b), а затем применить алгоритм из главы 4. Соответствие между целочисленными t-потоками в G и целочисленными потоками в G, задающими допустимые множества, будет не только взаимно однозначным, но и сохраняющим стоимость. Альтернативное изложение способа решения задачи о матроидном паросочетании для гаммоидов можно найти в [47]. Пусть задан двунаправленный граф G, и в нем выделена пара вершин а, Ь Є VQ. Поставим следующую задачу: найти в графе G а-Ь путь или установить, что его не существует. (Напомним, что по определению путь, в отличие от маршрута, не может содержать повторяющихся ребер.) Для определенности мы потребуем также, чтобы искомый путь выходил из обоих концов а и Ь (остальные случаи легко сводятся к указанному применением элементарных преобразований в вершинах а и Ь).
Данный вопрос обобщает соответствующую задачу достижимости в направленном графе и уже оказывается нетривиальным. Несложно показать, что достаточно изучить случай а = Ь. Действительно, добавим к исходному графу новую вершину s, а также ребра {s, а} и {s, b}, выходящие из s и заходящие в а и Ь соответственно. Добавлением в начало ребра {s, а}, а в конец ребра {s,b} всякий а-Ь путь, выходящий из а и Ь, превращается в s-путь (напомним, что так называется двунаправленный s-s путь, выходящий обоими концами из вершины s). Обратно, удаляя первое и последнее ребра из произвольного s-пути, мы получаем а-Ь путь искомого вида.
Задачу о разыскании s-пути также легко переформулировать в терминах косо-симметрических графов. Получаем задачу регулярной достижимости:
(R) В заданном кососимметрическом графе G с выделенной вершиной s найти регулярный s-s путь или установить, что его не существует.
Отметим также, что если регулярный путь в G найдется, то найдется также и простой регулярный путь. Его образ в двунаправленном графе G (отвечающем G) даст s-путь, проходящий через каждую вершину не более двух раз.
Алгоритм для задачи (R) приведен в [25]; для полноты изложения мы приводим его (под названием REGULAR-PATH) В разделах 3.3, 3.4. Время работы данного алгоритма составляет 0(т) (здесь и далее т обозначает число дуг или ребер графа, а п — число вершин в нем). В работе [25] также приведен структурный результат (который мы формулируем в разделе 3.2), дающий необходимое и достаточное условие существования регулярного s-s пути в терминах отсутствия в графе G так называемого
Реализация алгоритма поиска кратчайшего регулярного пути
В данном разделе мы опишем, как изложенная общая схема может быть реализована, чтобы обеспечить оценку времени работы 0(min(mlogn,n2)). Вначале обсудим способ хранения графа и его перестройки. В основе наших построений будет лежать способ представления графа, изложенный в разделе 3.4. Как и в алгоритме REGULAR-PATH множество Т мы храним в виде леса F. Теперь нам потребуется более мощная структура данных для представления F. А именно, с каждой вершиной v леса F связано вещественное число — ключ k(v) (смысл этих ключей будет объяснен ниже). Лес F поддерживает выполнение следующих операций: (F1) создать в дереве новую изолированную вершину с указанным значением ключа; (F2) изменить ключ указанной вершины дерева; (F3) добавить в дерево дугу (и, v), идущую от указанной вершины и в корневую вершину v (тем самым, и становится родителем v); (F4) удалить из дерева дугу, идущую в заданную вершину от ее родителя; (F5) удалить из дерева заданную вершину, у которой нет сыновей; (F6) по заданной вершине v найти корень root(v) ее поддерева. (F7) по заданной вершине v вычислить сумму ключей вершин, лежащих на пути от v до корня root(v) (не включая саму v). Операции (F1)-(F5) выполняются за время 0{Траще), а операции (F6)-(F7) — за время 0(Tj.uen/). Фактический способ реализации F будет выбран далее. Одновременно получат конкретные значения оценки времени Т ЛП9е и Триегу. Для хранения дерева путей Т будем для каждой вершины v Є Цг — {s} помнить дугу дерева, входящую в v (как и в алгоритме REGULAR-PATH). Способы коррекции Т при его наращивании и вырезании ростка остаются прежними. Рассмотрим шаг восстановления для ростка г. Помимо корректировки дерева ростков F нам понадобится добавить в дерево путей Т дуги, лежащие внутри восстанавливаемого ростка. Подходящим способом хранения множества дуг А0 и порождающих путей (см. свойство (ВЗ)) можно добиться того, чтобы время построения пути, о котором идет речь в лемме 3.5.3, было линейным по его длине. Следовательно, на коррекцию дерева Г на шаге восстановления ростка г уйдет время 0(V -). Опишем теперь способ хранения и изменения двойственных переменных 7Г и . Далее нам часто будет встречаться следующая технически тривиальная, но полезная конструкция, которую мы будем называть методом аккумуляции значений.
Рассмотрим простейший модельный пример. Предположим, что требуется поддерживать множество U элементов, с каждым из которых связано число, называемое ключом. Ключ элемента х будем обозначать через к(х). Кроме того, в множестве U будет выделено подмножество UQ. Требуется реализовать структуру данных, позволяющую за время 0(1) выполнять следующие операции: (А1) добавить новый элемент х с указанным ключом к множеству U; (А2) удалить из множества U элемент х (если х Є Щ, то х удаляется и из UQ); (A3) добавить элемент х Є U к выделенному подмножеству UQ; (А4) исключить элемент х Є UQ из выделенного подмножества UQ\ (А5) по заданному элементу х Є U определить, лежит ли а; в выделенном подмножестве UQ; (Аб) получить текущий ключ элемента х; (А7) установить новое значение ключа элемента х; (А8) добавить к ключам всех элементов из UQ заданное число 5. Для реализации этой структуры данных достаточно вместо явных значений ключей хранить аккумулированное значение А и для каждого элемента х — эффективный ключ к(х): I к(х), иначе. Иначе это соотношение можно записать так: Тогда операция (А8) сведется к изменению значения Д на 5. Аналогичная конструкция (с той же асимптотической оценкой сложности) годится, когда выделенных подмножеств не одно, а несколько, но их число ограничено абсолютной константой. Метод аккумуляции значений применим для хранения потенциалов 7Г и следующим образом. С каждой вершиной г; исходного графа Go связан потенциал K(V). На множестве вершин исходного графа Go будем рассматривать V0+ и V0 как выделенные подмножества.
Потенциалы вершин будут выражаться следующим образом: где Д -, Av+ — аккумулированные значения для подмножеств VQ, VQ соответственно, а 7Г — эффективные потенциалы. Аналогично, с каждым ростком г Є37 связан потенциал (т). На множестве Т будем считать подмножества F+ и Т выделенными — это позволит изменять потенциалы сразу для всех элементов каждого из этих множеств за время 0(1). Потенциалы ростков будут выражаться формулой: где Д г-, А?+ — аккумулированные значения для подмножеств 7 , Т+ соответственно, а — эффективные потенциалы. Ключами вершин т леса F (не являющихся листьями) мы объявим эффективные потенциалы (т). Для листьев ключи не определены. В процессе работы алгоритму требуется вычислять некоторые из модифицированных длин 1\. Покажем, как производить эти вычисления эффективно. Фиксируем дугу а Є Ас И рассмотрим ее прообраз a := 0-1(а) = (u,v) Є AG0- Для вычисления модифицированной длины а будем использовать следующую формулу: Здесь I обозначает эффективную длину, а функции 6 : AQ0 — Ж и Sbase Ас0 — Ж служат для корректировки длин с помощью потенциалов (первая отвечает за изменение длин всех дуг, пересекающих разрезы S(VT) ростков rGf; вторая — за изменение длин базисных и антибазисных дуг): Значения 7г(и) и ir(v) в (3.5) вычисляются за время 0(1) по формуле (3.3). Будем поддерживать на множестве Ад0 следующие выделенные подмножества: Тогда с помощью схемы аккумуляции вычисление значений бьаве и их обновление (при изменении потенциалов ростков из Т и Т ) можно выполнить за время 0(1). Как видно из определения, для произвольной вершины v Є VQ0 поправка 5cut{v) равна сумме потенциалов ростков из Т, содержащих v. В частности, S v) = О для всех простых внешних вершин v исходного графа. Для вычисления значения Scutiv) алгоритм использует возможности леса F. А именно, вычисляется сумма ключей, сохраненных в вершинах F на пути от г; к root(v) (не считая саму v). Чтобы учесть тот факт, что ключами вершин г леса F являются не сами потенциалы ростков (г), а лишь эффективные значения (т), выполняется коррекция по формуле (3.4). Суммарно для вычисления модифицированной длины любой дуги требуется 0(TpUery) единиц времени.
Алгоритм сведения к задаче в стандартной направленной сети
Как это может показаться, стоимостные потоковые задачи в случае кососим-метрических сетей намного труднее их стандартных направленных аналогов. Однако оказывается, что существует способ свести кососимметрическую задачу к обычной. При этом потребуется выполнить постобработку, сложность которой составляет О(тп log п). Близкие идеи были предложены Ансти в работах о 6-паросочетаниях [13, 14]. Далее мы приводим адаптацию для случая задач в кососимметрических сетях. Учитывая упомянутое в начале раздела сведение от задачи (MCF) к задаче (МСС), мы сконцентрируем свое внимание на последней. Нам понадобится ряд вспомогательных определений. Ненаправленный граф G будем называть кососимметрическим, если задана пара биекций оу\ VQ — Va и а Е- EG — Eg, обладающих следующими свойствами: Как и в случае направленных кососимметрических графов, мы объединяем эту пару отображений в одно a: VQ U EG — VQ U EQ И пишем x вместо o(x). Симметрия естественным образом продолжается на пути, циклы и другие объекты в G. Цикл С будем называть самосимметричным, если С = С (равенство понимается с точностью до циклического сдвига). Лемма 4.3.1. Пусть задан ненаправленный кососимметрический граф G, в котором степень каждой вершины четна. Тогда за линейное время можно построить семейство простых циклов Сі,..., С , задающих разбиение EG. Более того, в этой последовательности для каждого цикла СІ найдется также и симметричный ему цикл Cj (возможно і = j).
Доказательство. Начав с произвольной начальной вершины v0, такой что 5(VQ) ф 0, будем строить путь Р, поочередно добавляя к нему в конец ребра из EQ. Четность степеней всех вершин гарантирует, что требуемое ребро найдется на каждом шаге. Этот процесс будем продолжать до тех пор, пока либо путь Р не перестанет быть простым, либо у путей Р vi Р не появится общая вершина. Пусть процесс остановился, и на последнем шаге к пути было добавлено ребро е = {и, v}, где и — конец пути до добавления. Если от добавления е путь Р перестал быть простым, то его можно разбить на две части: простой путь Р0 от v0 до v и «хвостовой» цикл С. Выделим цикл С и ему симметричный С в качестве элементов разложения, удалим их ребра из Си заменим Р на его начальный VQ-V отрезок Ро, после чего продолжим действовать как и раньше. Если же добавление ребра е привело к появлению общих вершин у путей Р и Р , то теперь путь Р состоит из vo v отрезка Ро и v -v отрезка Pi. Выделим в качестве самосимметричного элемента разложения цикл, составленный из путей Pi и Р[, затем заменим Р на Р0 и продолжим итерации. Время работы такого алгоритма пропорционально суммарной длине всех построенных циклов, то есть является линейным, как и требовалось. Рассмотрим в сети N = (G, с) с симметричной функцией стоимостей w задачу (МСС). Снимем с искомой функции /, задающей циркуляцию, условие симметричности. Тогда получим классическую задачу о целочисленной циркуляции минимальной стоимости в направленной сети. Для решения последней разработаны многочисленные эффективные алгоритмы (см., например, [27, 29, 43, 12]).
Пусть /о обозначает (не обязательно симметричное) целочисленное решение стандартной задачи о циркуляции. Симметризуем его, положив Функция /і: Ас — К+ задает симметричную циркуляцию в сети, причем в силу симметрии целевого функционала справедливо равенство w /о = w /і, так что циркуляция /і также будет иметь минимальную стоимость (среди всех стандартных циркуляции в данной сети). Обозначим через 7г: VQ — R соответствующий сертификат консервативности w в G/2: Набор 7г легко построить с помощью алгоритма Беллмана-Форда [10] за время 0(тп). Положим AQ := {а Ac \ /i(a) . Z}. Имеем: А 0 = А0. Каждая дуга о Є А0 порождает пару дуг а, а 1 в остаточной сети G . Поскольку приведенные стоимости wn дуг а\, а,2 равны по величине и противоположны по знаку, то tyw(a) = ww(a_1) = 0. Таким образом, изменение циркуляции /і на дугах из А0 не нарушает ее оптимальности. Построим ненаправленный кососимметрический граф Н, взяв Vc в качестве множества вершин и добавив для каждой дуги (и, v) Є AQ ребро {и, v}. Кососимметриче-ская структура графа G индуцирует таковую на графе Я. Для графа Н выполнены условия леммы 4.3.1. Построим за время 0(т) разложение Ен в семейство циклов, в котором любой цикл либо самосимметричен, либо входит вместе с симметричным ему циклом. Полученный набор циклов обозначим через С. Будем последовательно корректировать циркуляцию /і (с сохранением ее оптимальности в классе всех стандартных направленных циркуляции), удаляя некоторые циклы С, так чтобы в конце все циклы из С были самосимметричны и не имели пересечений по вершинам. Обозначим через / текущую циркуляцию. Произвольную пару симметричных циклов можно устранить следующим образом. Возьмем первый такой цикл из С, ориентируем произвольным образом и обозначим результат через С. Цикл С можно рассматривать как содержащийся в остаточной сети G/. В этой же сети содержится и симметричный цикл С. Протолкнем по циклам С и С" половину единицы потока, положив / := / ф (хс + Xе"). Этим преобразованием мы сохраним симметрию циркуляции и удалим из С пару С, С. Избавившись от пар симметричных циклов, мы оставим в С лишь самосимметричные циклы. Пусть пара таковых С\,СЇ Є С имеет общую вершину v. Тогда С\, Сэ также пересекаются и по симметричной вершине v . Пара вершин v, v разбивает каждый из циклов С на две симметричные части. А именно, для і = 1,2 существуют v-v пути Pi в G/, такие что СІ получается объединением путей Р , Р/ и снятием с их дуг ориентации. Положим Q := Pi о Р2-1 и / := / Ф \(\ + XQ) (здесь через Р2-1 обозначен путь, противоположный к Рг). Этим преобразованием пара Сі, Сг будет удалена из С. Пусть теперь в С остались самосимметричные циклы Сі,..., С&, к п/2. Возьмем на цикле СІ произвольную вершину Vi (1 і к). Для каждого і рассмотрим путь Pj по циклу СІ (в произвольную сторону) от вершины Vi до вершины v[. Протолкнем половину единицы потока вдоль каждой из пар путей Р,-, Р/, получим функцию /г: Построение функции /г по /о возможно за суммарное время 0(т). Наконец надстроим сеть: добавим к ней пару симметричных вершин q, q , а также симметричные дуги вида (q,Vi), (v q1), 1 і к, назначив им нулевую стоимость и единичную пропускную способность. Функцию /г продолжим на множество добавленных дуг естественным образом, чтобы получить целочисленный кососим-метрический q-q1 поток, имеющий минимальную стоимость среди всех целочисленных кососимметрических потоков величины к. Для получения искомой оптимальной циркуляции воспользуемся изложенным ранее алгоритмом дополнения вдоль кратчайших путей (начав с системы потенциалов 7г). Учитывая, что к = 0(п), получаем следующее утверждение
Похожие диссертации на Сложность некоторых алгоритмических проблем для кососимметрических графов
