Сложность некоторых алгоритмических проблем для кососимметрических графов

• Автор: Бабенко, Максим Александрович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 114 с. : ил.

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

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

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

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

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

2. Приложения к классическим задачам комбинаторной оптимизации

2.1. Паросочетания и Ь-паросочетания

2.2. Г-соединения

2.3. Упаковки Т-путей

2.4. Гаммоиды и дельта-гаммоиды

2.5. Матроидные паросочетания в гаммоидах

3. Пути в кососимметрических и двунаправленных графах
3.1. Введение
3.2. Фрагменты, ростки и барьеры
3.3. Алгоритм поиска регулярного пути
3.4. Реализация алгоритма поиска регулярного пути
3.5. Консервативность и регулярная консервативность
3.6. Алгоритм поиска кратчайшего регулярного пути
3.7. Реализация алгоритма поиска кратчайшего регулярного пути
3.8. Случай произвольных длин дуг
4. Стоимостные потоки в кососимметрических сетях
4.1. Введение
4.2. Алгоритм дополнения вдоль путей минимальной стоимости
4.3. Алгоритм сведения к задаче в стандартной направленной сети
5. Ациклические кососимметрические графы
5.1. Введение
5.2. Ациклические графы
5.3. Регулярно ациклические графы
5.4. Приложение к теории паросочетаний
5.5. Ациклическая декомпозиция

5.6. Алгоритм проверки регулярной ацикличности
5.7. Характеризация в терминах сильно связных компонент
6. Задача о цикле минимального среднего веса
6.1. Введение
6.2. Общий подход
6.3. Минимальные средние регулярные циклы
7. Потоки в простых кососимметрических сетях
7.1. Введение
7.2. Оценка мощности носителя ациклического потока
7.3. Оценка величины потока
7.4. Метод блокирующего потока
8. Декомпозиция многополюсных потоков
8.1. Введение
8.2. Декомпозиция в направленных графах
8.3. Декомпозиция в кососимметрических графах
9. Мультипотоки в двунаправленных и кососимметрических сетях
9.1. Введение
9.2. Мультипотоки в кососимметрических сетях
9.3. Случай двух пар терминалов
9.4. Случай трех пар терминалов
9.5. Общий случай
9.6. Оценка времени работы
Литература
Предметный указатель

Основные понятия
Данная работа относится к теории комбинаторной оптимизации. В качестве основного объекта рассмотрения выступают графы: стандартные (направленные и ненаправленные), а также нестандартные (кососимметрические и двунаправленные).
Приведем вначале основные определения, касающиеся двух стандартных типов графов: направленных и ненаправленных. Направленный граф G представляет собой четверку (У,, A, tail, head), где V — конечное множество вершин, А — конечное множество дуг, а отображения tail: А —> V, head: А —> V сопоставляют каждой дуге а 6 А пару различных вершин: начало tail(a) и конец head(a). Если head(aj) = head(a2) и tail(ai) = tail(d2), то дуги ai и аг называют параллельными. В случае когда не возникает неоднозначностей в понимании, дугу, идущую из вершины и в вершину v, мы будем обозначать через (и, и). Более того, при записи функций от дуг графа будем опускать двойные скобки и писать f(u,v) вместо полного варианта
Маршрутом Р из s в i (или, для краткости, s-t маршрутом) в направленном графе G называют последовательность вершин и дуг вида
Р = (s = v0,аиvu...,vk-uak,vk = t),
где Vi — вершины (0 < i < k), ai — дуги, tail(aj) = v»_i, head(a;) = Vi (1 ^ i < k).
В случае если все дуги а; в последовательности Р различны, то маршрут Р будем называть простым по дугам (или путем)] в случае если и, ф Vj для всех 0 < г < j < k и v0 ф V{, vk Ф Vi для всех 0 < г < к, то простым по вершинам (или простым путем). Отметим, что концы простого пути могут совпадать. Маршрут Р будем называть циклическим, если s = t] циклический маршрут, являющийся (простым) путем, будем называть (простым) циклом.
Переходим теперь к понятию ненаправленного графа. Каждый такой граф задается тройкой (V, Е, ends), где V — конечное множество вершин, Е — конечное множество ребер, а отображение ends задает для каждого ребра е £ Е множество ends(e) = {и, и}, состоящее из двух различных вершин и, v (концов е). В случае если ends(ei) = ends(e2), то ребра е и называют параллельными. Ребро, соединяющее вершины и ни, мы обозначаем через (u, v}.
Понятие маршрута переносится на случай ненаправленного графа следующим образом. Маршрутом Р из s в t (s-t маршрутом) в ненаправленном графе G называют последовательность вершин и ребер вида
р = (v0,e1,v1 vk-1,ek,vk),

единиц времени. Каждая непустая очередь Щ делегирует свой минимальный элемент в очередь второго порядка Щ. Последняя реализована в виде списка, так что добавление и удаление элементов в ней выполняются за время 0(1), а поиск минимума — за время 0(п). Тем самым, для вычисления значения £2 алгоритму достаточно произвести выбор минимумов среди Н] и Щ, на что уйдет время 0(п).
Состояние очередей Н] обновляется при операциях наращивания дерева, вырезания и восстановления ростков. Шаг вырезания ростка т требует корректировки векторов Щ, на что уходит 0(п ■ |1^|) единиц времени. Суммарно все шаги вырезания потребуют 0(п2) единиц времени. Пусть на шаге наращивания в дерево добавляется вершина V, которая является простой или составной базисной. Тогда для V строится очередь Щ{у) путем просмотра соответствующего набора дуг-прообразов, ставших существенными. Поскольку каждая дуга может стать существенной лишь один раз (см. (3.6)), то суммарно на добавление дуг будет уходить время 0{тп). Аналогичные действия по просмотру новых существенных дуг производятся при восстановлении ростка г. Кроме того, при восстановлении т перестройка Н потребует дополнительно 0{п ■ Ус) единиц времени, то есть 0(п2) всего.
Окончательно для случая плотного графа получаем алгоритм с оценкой сложности 0(п2). Итак, доказано утверждение:
Теорема 3.7.1. Задача (Э*) может быть решена за время 0(mI^(mlogn,n2)).
3.8. Случай произвольных длин дуг
Покажем, что проверка функции длин на регулярную консервативность (и построение соответствующего сертификата) сводится к решению 0(п) задач (Б*). Пусть задан граф и симметричная функция длин £: Ас —> К. Предположим, что функция £ принимает отрицательные значения лишь на к парах дуг; обозначим их через оі,а[,. ..,ак,а'к. Построим последовательность графов Со в которой С,-получается из Є удалением дуг {а.,, а), а'к}. В частности, в Со нет отрицательных дуг, и справедливо равенство С* = С. Будем строить последовательность правильных сертификатов регулярной консервативности (я0, £о) (я*, £*) для графов С0,.. ■, С*. В качестве (тг0, £0) возьмем тождественно нулевые функции.
Покажем, как осуществляется переход от г-го сертификата к і + 1-му. Пусть а* = (і,я), а' = (в',?). Произведем надстройку графа Сі следующим образом: добавим к нему пару симметричных вершин ш, и/, а также вспомогательные дуги нулевой длины (ги, в), (в', и/), (и>, £), (£', и/). Полученный граф (см. рис. 3.3) обозначим через С, а за функцией длин сохраним прежнее обозначение І.
Продолжим сертификат (я;,&) с графа Сі на граф <3. Для этого выберем потенциалы добавленных вершин ш, и/ равными по абсолютной величине и противоположными по знаку, причем такими, чтобы модифицированные длины инцидентных им дуг оказались неотрицательными. Затем применим к графу С алгоритм ІІЕСиьАіі-Энсштезт-Ратн. В результате получим правильный сертификат регулярной консервативности (я, £) в графе С. Наша цель теперь — перенести данный сертификат в граф Сі+і- Вначале сузим функцию я на множество Ус, результат обозначим через яі+і. Затем поочередно рассмотрим все ростки т Є виррф Поскольку в графе <5