Решение задач маршрутизации и путевых разбиений графов методами раскрасок и весовых перераспределений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. СОБОЛЕВА

ЗАМБАЛАЕВА Долгор Жамьяновна

РЕШЕНИЕ ЗАДАЧ МАРШРУТИЗАЦИИ И ПУТЕВЫХ РАЗБИЕНИЙ ГРАФОВ МЕТОДАМИ РАСКРАСОК И ВЕСОВЫХ ПЕРЕРАСПРЕДЕЛЕНИЙ

(01.01.09 - дискретная математика и математическая кибернетика)

На правах рукописи

1 О НОЯ 2011

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 2011

4859188

Работа выполнена в Учреждении Российской академии наук Институте математики им. С. Л. Соболева Сибирского отделения РАН.

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

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

кандидат физико-математических наук Глебов Алексей Николаевич доктор физико-математических наук, профессор Гимади Эдуард Хайрутдинович кандидат физико-математических наук Аксенов Валерий Анатольевич Учреждение Российской академии наук Институт математики и механики Уральского отделения РАН (ИММ УрО РАН)

Защита состоится 30 ноября 2011 г. в 17 часов на заседании диссертационного совета Д 003.015.01 при Учреждении Российской академии наук Институте математики им. С. Л. Соболева СО РАН (пр. Академика Коп-тюга, 4, 630090 Новосибирск).

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института математики СО РАН.

Автореферат разослан октября 2011 г.

Ученый секретарь диссертационного совета доктор физ.-мат. наук

Ю. В. Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Исследования в области дискретной оптимизации за последние полвека приобрели особую актуальность в связи с фундаментальными проблемами полиномиальной разрешимости задач из классов NP-полных и NP-трудных задач. Было установлено, что полиномиальная разрешимость хотя бы одной NP-полной проблемы влечет полиномиальную разрешимость любой другой задачи из класса NP. Драматизм ситуации состоит в том, что доказать (или опровергнуть) совпадение классов Р и NP к настоящему времени не удается. Большинство исследователей склоняются к пессимистической гипотезе несовпадения этих классов.

В этих условиях актуальными становятся исследования по разработке и обоснованию полиномиальных приближенных алгоритмов решения трудных задач комбинаторной оптимизации с возможно более лучшими оценками их качества. Основные усилия специалистов по методам комбинаторной оптимизации направлены в сторону развития новых методов построения малотрудоемких приближенных алгоритмов и получения как положительных, так и отрицательных результатов, касающихся существования полиномиальных приближенных схем (SNP-трудность). Это направление исследований является составной частью раздела математики, известного за рубежом под названием "Computer science". Оно сопровождается большим количеством международных симпозиумов и конференций, множеством специальных журналов и монографий, интенсивно развивается во многих научных школах (Кук С., Карп Р., Гэри М., Джонсон Д., Яннакакис М. и Пападимитриу X. - США, Ленстра Дж., Скрайвер А. — Нидерланды, Эрдеш П., Ловас Л. - Венгрия, Эдмондс Дж. — Канада, Грётшель М. — Германия, Буркард Р. — Австрия др.).

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

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

В связи с этим следует отметить, что теория графов за последние 30-40 лет оформилась в самостоятельную математическую дисциплину, с присущими ей задачами и подходами, и активно развивается. Идеи и методы теории конечных графов востребованы во многих областях дискретной математики и их приложениях. Одно из центральных мест в современной теории графов занимает теория раскраски, то есть разбиения дискретного объекта на проще устроенные подобъекты. В частности, внимание ведущих графистов мира привлекают задачи о вершинных раскрасках и разбиениях планарных графов. Одной из разновидностей таких задач являются задачи о путевых разбиениях графов, при которых каждая часть разбиения (цветовой класс) порождает подграф с заданными ограничениями на длины цепей. В диссертации путевые разбиения планарных графов изучаются в главе 1, а в главе 2 при разработке алгоритмов для задачи о двух коммивояжерах на максимум применяются реберные раскраски графов в 2 и 3 цвета.

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

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

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

(3,3)-разбиваемости таких графов. Разработаны новые алгоритмы для задачи о двух коммивояжерах на минимум и на максимум, обладающие лучшими, в сравнении с ранее известными, оценками точности.

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

Основные результаты.

1. Доказана r-разбиваемость планарных графов с обхватом не менее 5.

2. Доказано, что множество вершин планарного графа с обхватом не менее 7 можно разбить на два подмножества, каждое из которых порождает звездный лес, что эквивалентно путевой (3,3)-разбиваемости таких графов.

3. Построен полиномиальный приближенный алгоритм решения задачи о двух коммивояжерах на максимум (задача 2-PSP-max) с оценкой точности | и оценкой временной сложности 0(п3).

4. Для решения задачи о двух коммивояжерах на минимум с весами ребер 1 и 2 и различными весовыми функциями (задача 2-PSP(l,2)-min-2w) построены следующие приближенные алгоритмы:

4.1. алгоритм с оценкой точности | и временной сложностью 0(п3).

4.2. алгоритм с оценкой точности | и временной сложностью 0(п5).

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

Апробация работы. Результаты диссертации докладывались на международных научных студенческих конференциях «Студент и научно-технический прогресс» (Новосибирск, 2007, 2008), на Всероссийских конференциях «Методы оптимизации и экономические приложения» (Омск, 2009), «Дискретная оптимизация и исследование операций» (Алтай, 2010), «Математическое программирование и приложения» (Екатеринбург, 2011), на Международных конференциях по исследованию операций «European Conference on Operational Research» (Бонн, 2009), «Optimal Discrete Structures and Algorithms» (Росток, 2010), на научных семинарах Института математики им. С.Л. Соболева СО РАН.

Публикации. По теме диссертации автором опубликовано 11 работ, из них 5 публикаций в научных журналах [16-20] и 6 публикаций в трудах и тезисах конференций [21-26]. Результаты разделов 1.2, 3.3 и главы 2 получены в соавторстве с А.Н. Глебовым. Результат раздела 3.2. получен в соавторстве с А.Н. Глебовым и A.B. Гордеевой. Конфликт интересов с соавторами отсутствует.

Структура и объем работы. Диссертация изложена на 138 страницах, содержит введение, три главы и список литературы, содержащий 70 наименований.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

В разделе 1.1 вводятся основные определения и обозначения. Пусть а > 1, Ь > 1 - целые числа. Граф G называется (а,Ъ)-разбиваемым, если существует такое разбиение множества его вершин V = Vi U V2, что в подграфе Gi = G[Vi], порожденном подмножеством Vu длина наибольшей простой цепи не превосходит а, а в подграфе G2 = G[V2] - не превосходит Ь, где под длиной цепи понимается число ее вершин. Граф G называется т-разбиваемым, если он (а, Ь)-разбиваем для любых натуральных а, Ь таких, что а + Ь = т, где т = r(G) — наибольшая длина простой цепи в G.

В работах [10, 12] высказывалась гипотеза о том, что любой граф является r-разбиваемым. В [11, 12, 13, 14] и ряде других работ справедливость этой гипотезы была подтверждена для некоторых специальных классов графов. В [6] было доказано, что любой граф является (а, г - а)-разбиваемым при а < 8. Вопрос о т-разбиваемости планарных графов ранее специально не исследовался.

В разделе 1.2 диссертации гипотеза о т-разбиваемости частично подтверждена для специального подкласса пленарных графов, а именно доказана

Теорема 1. Любой планарный граф с обхватом не менее 5 является т-разбиваемым.

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

В разделе 1.3 доказана

Теорема 2. Множество вершин любого плоского графа с обхватом не менее 7 можно разбить на два подмножества, каждое из которых порождает звездный лес.

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

В [10, 11, 12] и ряде других работ исследовались (о, 6)-разбиения для некоторых специальных классов (непланарных) графов. Уже для планар-ных графов Глебовым и Замбалаевой [19] было доказано, что такие графы с обхватом не менее 8, 9 и 16 являются (2,3)-, (2,2)- и (1,2)-разбиваемыми соответственно. Эти результаты были усилены Бородиным и Ивановой [3, 4], которые установили, что планарные графы с обхватом не менее 14 являются (1,2)-разбиваемыми, а с обхватом не менее 8 — (2,2)-разбиваемыми.

С другой стороны, Михоком [15] было показано, что для любых фиксированных значений параметров а, Ь существуют плоские графы, не являющиеся (а, Ь)-разбиваемыми. При этом во всех примерах графов, приводимых в [15], содержится большое число циклов длины 3. Поэтому представляет интерес вопрос о том, для какого наименьшего значения д > 4

существуют такие константы а, Ь, что любой планарный граф с обхватом не менее д является (а, Ь)-разбиваемым. Из доказанной в диссертации теоремы 2 следует, что д < 7.

Во второй главе диссертации рассматривается задача задача об отыскании в полном взвешенном неориентированном графе двух реберно непересекающихся гамильтоновых циклов с максимальным суммарным весом ребер, известная как задача о двух коммивояжерах на максимум (2-РБР-тах). Известно, что данная задача ^Т-трудна. В главе 2 построен полиномиальный алгоритм А7/э приближенного решения 2-РЭР-шах, имеющий оценку точности | и кубическую временную сложность.

В разделе 2.1 приводится постановка задачи 2-РЗР-тах. Дан полный п-вершинный неориентированный граф Е), на ребрах которого задана весовая функция и> : Е -» Допустимым решением задачи 2-РЭР-тах называется любая пара реберно непересекающихся гамильтоновых циклов ЯЬЯ2 в С. Значение целевой функции для ЯЬЯ2 определяется как и Я2) = и>{Нг) + ю(Н2), где = £ебЯ. ю(е), г е {1,2}, то

есть равно сумме весов всех ребер из Нх и Я2. Требуется найти в графе С такие два реберно непересекающихся гамильтонова цикла Яь Я2, что суммарный вес их ребер и)(Н1 иЯ2) максимален. Через ОРТ обозначается оптимальное значение целевой функции.

В разделе 2.2 приводится описание алгоритма Л7/9 приближенного решения поставленной задачи, который имеет наилучшую на сегодняшний день оценку точности * ^ 0.778 и кубическую временную сложность, что улучшает результат Агеева, Бабурина и Гимади [1], ранее построивших для данной задачи алгоритм с оценкой §.

В основе алгоритма А7/9 лежит идея, впервые реализованная Сердю-ковым [7] при построении приближенного алгоритма для задачи одного коммивояжера на максимум (ТБР-тах) с оценкой точности На первом этапе алгоритма Сердюкова в графе находятся 2-фактор и паросочетание максимального веса, суммарный вес которых составляет не менее 5 от веса оптимального решения. Далее алгоритм разбивает найденные 2-фактор и паросочетание на два частичных тура (то есть на два набора из вершинно непересекающихся цепей, покрывающих все вершины графа), каждый из которых дополняется до гамильтонова цикла. Максимальный по весу из этих циклов дает решение 2-Р8Р-тах с оценкой точности §.

В представленном в диссертации алгоритме Л7/9 реализован аналогичный подход, однако в качестве исходного подграфа, подвергающегося разбиению на непересекающиеся по ребрам частичные туры, используется 4-регулярный остовный подграф максимального веса в (3. При этом

представленный алгоритм развивает идеи, ранее использованные в работе Гимади, Глазкова и Глебова [5] при построении приближенного алгоритма с оценкой | для задачи 2-Р8Р на минимум с весами ребер 1 и 2. Ключевым этапом алгоритма Л7/9 является построение двух реберных раскрасок начальной пары частичных туров в два и в три цвета, что позволяет получить шесть альтернативных пар реберно непересекающихся частичных туров, наилучшая из которых имеет суммарный вес ребер не менее |ОРТ. Благодаря структурным свойствам начальной пары частичных туров, полученные туры удается дополнить до пары реберно непересекающихся гамильтоновых циклов, что не всегда возможно в случае произвольных реберно непересекающихся частичных туров.

Для построенного алгоритма в диссертации доказана следующая

Теорема 3. Алгоритм А7/д находит, в полном п-вершинном графе С? пару реберно непересекающихся гамильтоновых циклов Нг,Н2, для которых выполняется оценка ш(#1 иЯ2) > 1<ЭРТ. Временная слоокностъ алгоритма равна 0(п3).

Для доказательства теоремы 3 сначала в разделах 2.3-2.5 диссертации описываются и устанавливаются свойства используемых алгоритмом Л7/9 процедур. Доказательство самой теоремы 3 дается в разделе 2.6.

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

В разделе 2.7 для случая 2-Р8Р-шах, в котором веса ребер принимают значения из заданного промежутка [1,9], предложена модификация алгоритма Л7/д, имеющая гарантированную оценку точности что

улучшает ранее полученную Гимади и Ивониной оценку

Теорема 4. Алгоритм Лт^з находит в полном п-вершинном графе С, веса ребер которого принимают значения из промежутка [1,д], пару реберно непересекающихся гамильтоновых циклов ЯЬЯ2, для которых выполняется оценка и Я2) > ОРТ. Временная сложность алгоритма равна 0(п3).

В третьей главе исследуется задача о двух коммивояжерах на минимум с двумя различными весовыми функциями, принимающими значения 1 и 2 (задача 2-Р8Р-тт-2\у-(1,2)). Приведем ее формулировку. Дан неориентированный полный п-вершинный граф С(У, Е) и две весовые функции ребер: ицЕ{1,2}, : Е -» {1,2}. Требуется найти непересекающиеся по ребрам гамильтоновы циклы Яь Я2 такие, что их суммарный вес

«^(ЯО 4- №2(Я2), где и>ДЯ*) = 'Шг(е), минимален. Для приближен-

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

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

Для приближенного решения задачи 2-Р8Р-тт-2\у-(1,2) в разделах 3.2 и 3.3 представлены полиномиальные алгоритмы Л7/5 и Л4/3 соответственно. Последний алгоритм имеет наилучшую на сегодняшний день гарантированную оценку точности для данной задачи, равную | (без учета аддитивной константы) и оценку временной сложности 0(п°). Алгоритм Л7/5 обладает худшей по сравнению с алгоритмом Л4/3 оценкой точности 7/5, зато имеет лучшую (кубическую) оценку временной сложности. Оба алгоритма улучшают оценку точности уч ранее полученную в [8].

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

Дополнительные трудности при разработке и анализе алгоритмов в главе 3 (по сравнению со случаем двух одинаковых весовых функций) связаны с тем, что в рассматриваемом случае невозможна свободная переброска ребер из одного тура в другой. Из-за этого оказались неприменимыми многие методы, ранее использовавшиеся в задаче о двух коммивоя-

жерах с весами ребер 1 и 2 (см. [1, 2, 5]). Значительный объем доказательства оценок точности обоих алгоритмов также связан с рассмотрением большого числа случаев, соответствующих различным типам вершин графа. Тип вершины определяется тем, является ли она в туре концевой или внутренней вершиной цепи, вершиной цикла, синглом (¿'-вершиной) или так называемой (^-вершиной (б-, д)-дерева (независимо для каждого тура).

Следует отметить, что в разделе 3.3, посвященном построению и анализу алгоритма Л4/3, понятие частичного тура, традиционно используемое при построении алгоритмов для задач одного и двух коммивояжеров, существенно модифицировано за счет включения в туры наряду с цепями и циклами так называемых (в, д)-деревьев, определение и свойства которых даются в разделе 3.3.1 диссертации.

Для построенных алгоритмов доказаны следующие результаты:

Теорема 5. Алгоритм А7/5 за время 0(п3) находит в полном п-вершинном графе С пару реберно непересекающихся гамилътоновых циклов Н1, Н2, для веса которых выполняется неравенство

■шх{Н1) + -ш2{Нг) < {ОРТ+1.

Теорема 6. Алгоритм Л4/3 за время 0(п5) находит в полном п-вершинном графе С пару реберно непересекающихся гамилътоновых циклов Нг, #2, для веса которых выполняется неравенство

1И1(#1) + »02(Яа) < §ОРГ+1.

Есть все основания полагать, что разработанные в диссертации методы, связанные с применением раскрасок вершин и ребер, перераспределением зарядов и использованием принципиально новых объектов, таких как («, д)-деревья, окажется полезными при разработке других алгоритмов решения задач маршрутизации, главным образом, задач одного, двух и более коммивояжеров на минимум и на максимум.

Автор выражает искреннюю признательность своему научному руководителю Алексею Николаевичу Глебову за постоянную поддержку и внимание к работе.

Список литературы

[1] Агеев A.A., Бабурин А.Е., Гимади Э.Х. Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающих-

ся гамильтоновых циклов максимального веса. // Дискрет, анализ и исслед. операций. - 2006. - Сер. 1. Т. 13, № 2. - С. 11-20.

[2] Бабурин А. Е., Гимади Э.Х., Коркишко Н.М. Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых цикла минимального веса. // Дискрет, анализ и исслед. операций. - 2004. - Сер. 2. Т. 11, № 1. - С. 11-25.

[3] Бородин О. В., Иванова А. О. Почти правильные 2-раскраски вершин разреженных графов // Дискретный анализ и исследование операций. - 2009. - Т. 16, № 2. - С. 16-20.

[4] Бородин О. В., Иванова А. О. Разбиение разреженных плоских графов на два подграфа малой степени // Сибирские электронные математические известия, (http://semr.raath.nsc.ru). — 2009. — Т. 6.

- С. 13-16.

[5] Гимади Э. X., Глазков Ю. В., Глебов А. Н. Приближенные алгоритмы решения задачи о двух коммивояжерах в полном графе с весами ребер 1 и 2 // Дискрет, анализ и исслед. операций. — Сер. 2. 2007. - Т. 14, № 2. - С. 41-61.

[6] Мельников JI.C., Петренко И.В. О путевых ядрах и разбиениях в неориентированных графах// Дискретный анализ и исследование операций. - 2002. - Сер. 1. Т. 9, № 2. - С. 21-35.

[7] Сердюков А. И. Алгоритм с оценкой для задачи коммивояжера на максимум. // Управляемые системы. Сб. науч. тр. — 1984. — Вып. 25.

- С.80-86.

[8] А.Е. Baburin, F.Della Croce, Е.К. Gimadi, Y.V. Glazkov and V.Th. Paschos. Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 // Discrete Applied Mathematics, Vol. 157, No 9, 2009, P. 1988-1992.

[9] Berman P., Karpinski M. 8/7-approximation algorithm for (1,2)-TSP // Proc. of the 17th annual ACM-SIAM symposium on discrete algorithms, SODA 2006 (Miami, January 22-26, 2006). New York: ACM Press, 2006. P. 641-648.

[10] Borowiecki M., Broere I., Frick M., Mihok P., Semanisin G. A

survey of hereditary properties of graphs // Discussiones Mathematicae Graph Theory. 1997. V. 17, N 1 P. 5-50.

[11] Broere I., Dorfling M., Dunbar J. E., Frick M. A path(ological) partition problem // Discussiones Mathematicae Graph Theory. 1998. V. 18, N 1 P. 113-125.

[12] Broere I., Hajnal P., Mihok P., Semanisin G. Partition problems and kernels of graphs // Discussiones Mathematicae Graph Theory. 1997. V. 17, N 2 P. 311-313.

[13] Dunbar J. E., Frick M. Path kernels and partitions // Math. Combin. Comput. 1999. V. 31. P. 137-149.

[14] Dunbar J. E., Frick M., Bullock F. Path partitions and Pn-free sets // Discrete Math. 2004. V. 289. N 1-3, P. 145-155.

[15] Mihok J. Graphs, hypergraphs and matroids. Zielon Gora: Higher College Engrg., 1985.

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

Статьи в журналах

[16] Глебов А.Н., Гордеева А.В., Замбалаева Д.Ж. Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями // Сибирские электронные математические известия (htpp://semr.math.nsc.ru). — 2011. — Т. 8. — С. 296-309.

[17] Глебов А.Н., Замбалаева Д.Ж. Полиномиальный алгоритм с оценкой точности 7/9 для задачи о двух коммивояжерах на максимум // Дискретный анализ и исследование операций. — 2011. — Т. 18, № 4. - С. 17-48.

[18] Глебов А.Н., Замбалаева Д.Ж. Приближенный алгоритм решения задачи о двух коммивояжерах на минимум с различными весовыми функциями // Дискретный анализ и исследование операций. — 2011. - Т. 18, № 5. - С. 11-37.

[19] Глебов А.Н., Замбалаева Д.Ж. Путевые разбиения планар-ных графов // Сибирские электронные математические известия (htpp://semr.math.nsc.ru). - 2007. - Т. 4. - С. 450-459.

[20] Замбалаева Д.Ж. Разбиение плоского графа с обхватом 7 на два звездных леса// Дискретный анализ и исследование операций. — 2009. - Т. 16, № 3. - С. 20-46

Прочие публикации

[21} Глебов А.Н., Замбалаева Д.Ж. Путевые и звездные разбиения плоских графов // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 29 июня -4 июля 2009). Омск: Полиграфический центр К АН, 2009. С. 121.

[22] Глебов А.Н., Замбалаева Д.Ж. Задача о двух коммивояжерах на минимум в полном графе с различными весовыми функциями // Материалы Российской конференции «Дискретная оптимизация и исследование операций«- (Республика Алтай, 27 июня - 3 июля 2010). Новосибирск: Издательство Института математики, 2010. С. 131.

[23] Глебов А.Н., Замбалаева Д.Ж. Эффективный алгоритм с оценкой точности 7/9 для задачи о двух коммивояжерах на максимум // Информационный бюллетень Ассоциации математического программирования. № 12. XIV Всероссийская конференция «Математическое программирование и приложения» (Екатеринбург, 28 февраля - 4 марта 2011). Екатеринбург: УрО РАН, 2011. С. 168.

[24] Глебов А.Н., Замбалаева Д.Ж., Ивонина Е.В. Эффективные алгоритмы с гарантированными оценками точности для задач одного и двух коммивояжеров на максимум // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения» (пос. Листвянка, 23-29 июня 2011). Т. 4: Дискретная оптимизация. Иркутск: РИО ИДСТУ СО РАН, 2011. С. 82-87.

[25] Zambalaeva D. Decomposing planar graphs into degenerate subgraphs // Abstracts of European conference on Operational Research, Bonn, July 5-8, 2009. P. 183.

[26] Zambalaeva D. 4/3-approximation algorithm for the minimum 2-PSP with different weight functions valued 1 and 2 // Abstracts of International conference on Optimal Discrete Structures and Algorithms (ODSA), Rostok, September 13-15, 2010. P. 66.

Замбалаева Долгор Жамьяновна

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 24.10.2011 г. Формат 60x84 1\1б Усл. печ. л. 1.2 Объем 32 стр. Тираж 80 экз. Заказ № 205

Отпечатано Омега Принт

Введение

1 Путевые разбиения плоских графов

1.1 Основные определения и обозначения.

1.2 т-разбиваемость плоских графов с обхватом 5.

1.3 (3,3)-разбиваемость плоских графов с обхватом 7.

1.3.1 Простейшие свойства контрпримера к теореме

1.3.2 Формула Эйлера.

1.3.3 Свойства граней минимального контрпримера

1.3.4 Окрестности вершин степени 4.

1.3.5 Проверка неотрицательности зарядов после перераспределения

2 Полиномиальный алгоритм с оценкой точности 7/9 для задачи о двух коммивояжерах на максимум

2.1 Постановка задачи, определения и обозначения.

2.2 Описание алгоритма Л7/9.

2.3 Построение туров Т^Т^ в связном 4-регулярном графе, не изоморфном

§ и К4 4.

2.3.1 Построение базовых туров Т\ и Тг.

2.3.2 Разбиение туров Т\ и Т2.

2.3.3 Свойства туров Ми^иМиМ|.

2.3.4 Построение туров Т* и Т2*.

2.4 Построение реберно непересекающихся цепей для компонент связности

2.4.1 Случай компоненты связности, не изоморфной

2.4.2 Случай компоненты связности, изоморфной или Ä4j

2.5 Дополнение пары частичных туров до гамильтоновых циклов

2.5.1 Описание процедуры Н\ 2.

2.5.2 Обоснование процедуры

2.6 Доказательство теоремы 3.

2.7 Случай весов ребер из промежутка [1 ,q].

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

3.1 Основные определения и обозначения.

3.2 Полиномиальный 7/5-приближенный алгоритм для задачи 2-PSP-min-2w-(l, 2).

3.2.1 Описание алгоритма A^ß.

3.2.2 Оценка точности и временная сложность алгоритма

3.2.3 Доказательство леммы 3.3.

3.2.4 Обоснование временной сложности алгоритма A-jß

3.3 Полиномиальный 4/3-приближенный алгоритм для задачи 2-PSP-min-2w-(l, 2).

3.3.1 Основные определения и обозначения.

3.3.2 Описание алгоритма А4/3.

3.3.3 Оценка точности и временная сложность алгоритма

3.3.4 Доказательство леммы 3.6.

3.3.5 Обоснование временной сложности алгоритма А4/

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

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

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

Метод весовых перераспределений для вершин графа, наряду с главой 1, используется также и в главе 3 диссертации, в которой построены полиномиальные приближенные алгоритмы для задачи о двух коммивояжерах на минимум с различными весовыми функциями, принимающими значения 1 и 2. При помощи таких перераспределений в главе 3 обосновываются оценки точности полученных алгоритмов. В отличие от доказательства структурных результатов о плоских графах, в рассматриваемом случае использование зарядов (весов) вершин и последующее их перераспределение с сохранением суммы не является типичным, и применялось до этого только Берманом и Карпински [25] в задаче одного коммивояжера на минимум с весами ребер 1 и 2.

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

В работе рассматриваются конечные неориентированные графы без петель и кратных ребер. Плоским графом называется граф, вершинами которого являются точки на плоскости, а ребрами — жордановы кривые, соединяющие пары вершин так, что различные кривые пересекаются только в своих общих концевых вершинах. Граф называется планар-ным, если он изоморфен какому-либо плоскому графу. Гранями плоского графа называются области, на которые плоскость разбивается его ребрами и вершинами. Через С = Е, Е) обозначается плоский граф с множеством вершин V, множеством ребер Е и множеством граней Е. Если плоский граф С связен, то каждая его грань / ограничена некоторым (не обязательно простым) циклом, который называется граничным циклом грани /. Рангом г(/) грани / называется длина ее граничного цикла (где мосты засчитываются дважды). Через (1{у) = (1с(у) обозначается степень вершины V € V в т. е. число инцидентных V ребер из Е. Через ) обозначается обхват графа С, т.е. наименьшая длина простого цикла в (2, где обхват ациклического графа (леса) считается равным бесконечности.

Формулу Эйлера |У| — \Е\ + = 2 для связного плоского графа Оу, Е, .Р) можно записать в следующем виде:

• <*(") - 9) + £(г(Л - 5) = Е = где д — произвольное положительное число, выбор которого зависит от специфики рассматриваемой задачи. Величины

Ку) = ¥ • ад - 9, МЛ = г(/) - <7 принято называть зарядом вершины V € V и зарядом грани / Е Р соответственно. Заметим, что если выполняются условия <?((?) > <7 и > 1 то все гРани в имеют неотрицательный заряд.

Применение метода перераспределения зарядов (или весовых перераспределений) при доказательстве результатов о плоских графах включает следующие три этапа. На первом этапе устанавливается некоторая система сводимых конфигураций Б, т.е. такой набор структурных фрагментов графа, что ни один из этих фрагментов не может содержаться в минимальном контрпримере С к доказываемому утверждению. Второй этап рассматриваемого метода подразумевает разработку некоторой системы правил, по которым происходит перераспределение зарядов (весов) между элементами (вершинами и гранями) в минимальном контрпримере С: элементы с положительным значением заряда передают "избыток" своего заряда элементам, имеющим отрицательный заряд (как правило, ими являются вершины и грани с малой степенью/рангом). Третий, заключительный, этап состоит в проверке того, что после перераспределения зарядов по этим правилам заряд каждого элемента графа С (обладающего системой сводимых конфигураций 5), становится неотрицательным. Последнее свойство противоречит формуле Эйлера, согласно которой сумма зарядов всех элементов графа равна отрицательному числу. Другими словами, суть противоречия, полученного на третьем этапе, состоит в том, что система сводимых конфигураций 5 является для графа С неизбежной, т. е. хотя бы одна из этих конфигураций должна содержаться в минимальном контрпримере, что противоречит определению сводимости.

Одним из первых данный метод начал применять Хееш в ходе исследования знаменитой проблемы четырех красок в работе [53] 1969 г. Программа, предложенная Хеешем, была в итоге реализована в 1976 г. в результате "ручных" вычислений и применения ЭВМ Аппелем и Ха-кеном [20, 21, 22]. Их доказательство теоремы о четырех красках основывается на построении неизбежной системы из почти полутора тысяч сводимых конфигураций и служит классическим примером применения метода весовых перераспределений для плоских графов. Другой пример того же рода — это построенная в тоже время Бородиным [3, 26, 27] система из примерно 450 сводимых конфигураций для доказательства того, что любой плоский граф является ациклически 5-раскрашиваемым (т. е. допускает такую правильную раскраску в 5 цветов, что любой подграф, порожденный вершинами двух цветов, является ациклическим).

В настоящей диссертации данный метод впервые применяется в главе 1, в которой исследуются так называемые путевые разбиения плоских графов, понятие которых было введено в [29].

Дадим необходимые определения. Пусть а > 1, Ь > 1 — целые числа. Граф С называется (а, Ъ)-разбиваемым, если существует такое разбиение множества его вершин V = УгиУ^, что в подграфе С1 = порожденном подмножеством Уг, длина наибольшей простой цепи не превосходит а, а в подграфе = С?^] ~ не превосходит Ь, где под длиной цепи понимается число ее вершин. Заметим, что (1,1)-разбиваемость графа равносильна его двудольности, (2, 2)-разбиваемость — возможности разбиения на два подграфа с максимальной степенью 1, а (3,3)-разбиваемость разбиваемости на два звездных леса (для графов без 3-циклов).

Граф С называется т-разбиваемым, если он (а, 6)-разбиваем для любых натуральных а, Ь таких, что а + Ь = т, где т = т{0) — наибольшая длина простой цепи в С.

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

В работах [29, 31] высказывалась гипотеза о том, что любой граф является т-разбиваемым. В [30, 31, 43, 44] и ряде других работ справедливость этой гипотезы была подтверждена для некоторых специальных классов графов. В [16] было доказано, что любой граф является (а, т—а)-разбиваемым при а < 8. Вопрос о т-разбиваемости планарных графов ранее специально не исследовался.

В разделе 1.2 диссертации гипотеза о т-разбиваемости частично подтверждена для специального подкласса планарных графов, а именно доказано, что любой планарный граф с обхватом не менее 5 является т-разбиваемым (теорема 1).

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

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

Одним из наиболее сильных результатов в рассматриваемой области является вышеупомянутый результат Бородина [26] о том, что любой плоский граф допускает ациклическую раскраску вершин в 5 цветов, т. е. такую правильную 5-раскраску, при которой вершины любых двух цветов порождают лес. Заметим, что из теоремы об ациклической 5-раскраске следует ранее полученный Штейном [67, 68] результат о вершинной разбиваемости плоского графа на независимое множество и два леса. Другое важное следствие теоремы об ациклической 5-раскрашивае-мости состоит в том, что множество ребер любого плоского графа можно разбить на пять подмножеств, каждое из которых порождает звездный лес. При этом, как было установлено Хакими, Митчемом и Шмейхелем [51], оценка пять неулучшаема.

В разделе 1.3 диссертации доказано, что множество вершин плоского графа с обхватом не менее 7 можно разбить на два подмножества, каждое из которых порождает звездный лес (теорема 2). Иначе это утверждение можно сформулировать так: множество вершин плоского графа с обхватом не менее 7 можно разбить на два подмножества, каждое из которых порождает подграф, не содержащий циклов и простых цепей с более чем тремя вершинами. Здесь обнаруживается связь полученного результата с понятием путевой разбиваемости. В силу того, что (3,3)-разбиваемость графа эквивалентна его разбиваемости на два звездных леса (для графов без 3-циклов), утверждение теоремы 2 равносильно тому, что любой плоский граф с обхватом не менее 7 является (3, 3)-разбиваемым.

В [29, 30, 31] и ряде других работ исследовались (а, Ь)-разбиения для некоторых специальных классов (непланарных) графов. Глебовым и Зам-балаевой [10] было доказано, что планарные графы с обхватом не менее 8, 9 и 16 являются (2,3)-, (2,2)- и (1,2)-разбиваемыми соответственно. Позднее эти результаты были усилены Бородиным и Ивановой [5, 6], которые доказали, что планарные графы с обхватом не менее 14 являются (1,2)-разбиваемыми, а с обхватом не менее 8 — (2,2)-разбиваемыми. С другой стороны, Михоком [60] было показано, что для любых фиксированных значений параметров а, Ь существуют плоские графы, не являющиеся (а, 6)-разбиваемыми. При этом во всех примерах графов, приводимых в [60], содержится большое число циклов длины 3. Поэтому представляет интерес вопрос о том, для какого наименьшего значения д > 4 существуют такие константы а, 6, что любой плоский граф с обхватом не менее д является (а, Ь)-разбиваемым. Из доказанной в диссертации теоремы 2 следует, что д < 7.

Другим классом задач, для решения которых в главах 2 и 3 диссертации применяются методы раскрасок и весовых перераспределений для графов, являются задачи маршрутизации, а точнее, разновидности задач о двух коммивояжерах на минимум и на максимум.

Один из подходов, традиционно используемых при решении подобных оптимизационных задач, состоит в следующем. Вместо решения одной конкретной задачи рассматриваются алгоритмы, рассчитанные на так называемую массовую задачу П, содержащую ряд свободных переменных. Индивидуальная задача I получается из массовой задачи П присвоением всем ее переменным конкретных значений. Таким образом, массовая задача П — это совокупность индивидуальных задач. В общем виде индивидуальную задачу оптимизации / можно записать следующим образом: п гшп (*) где 5п(-0 С I - это множество допустимых решений, или, другими словами, множество вариантов, среди которых должно быть выбрано решение, /п(/, х) : 5п(/) —> Я — целевая функция, позволяющая оценивать качество полученного решения.

Если множество 5п(-0 конечно, то возникает задача дискретной оптимизации. Перебрав все варианты, мы обязательно найдем решение.

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

Большинство дискретных задач может быть переформулировано в виде задач распознавания свойств, т. е. в виде вопроса, ответом на который может быть либо 'да', либо 'нет'. Среди задач распознавания свойств выделяют класс АТР — задачи, которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве. Вопрос о том, совпадают ли классы Р и А/\Р, является центральным в теории сложности. При этом гипотеза Р ф АТР принимается многими математиками.

Если оптимизационная задача А^Р-трудна, то для ее решения нельзя построить точный полиномиальный алгоритм, при условии, что Р ф ЫР [13]. В данной ситуации можно рассматривать задачу с точки зрения выявления полиномиально разрешимых подклассов. Другой подход заключается в построении приближенного алгоритма А, который за время, ограниченное полиномом невысокой степени, находит допустимое решение "близкое" к оптимальному. Очевидным образом встает вопрос о степени этой близости. Если можно априорно установить эту степень, то говорят об алгоритмах с гарантированными оценками точности. Формально оценку точности алгоритма А для задач минимизации определяют, как величину тах/еп оРТп(Г) (если она существует), где ОРТц(1) — значение целевой функции на оптимальном решении х*: А(1) — величина ж), где х — решение построенное алгоритмом А. Аналогичным образом определяется оценка точности для задач максимизации.

Одной из самых известных и наиболее исследованных задач дискретной оптимизации является задача коммивояжера (в англоязычной литературе — Traveling salesman problem или TSP). Задача коммивояжера (далее ЗК) заключается в нахождении наиболее выгодного маршрута, проходящего через каждый из данных городов по одному разу с последующим возвратом в исходный город или, другими словами, экстремального по весу гамильтонова цикла в заданном графе. Общая постановка задачи, впрочем, как и большинство ее частных случаев, относится к классу NP-трудных задач [13].

Систематическое исследование ЗК как задачи комбинаторной оптимизации началось с работы [37]. Обзоры [54, 59] и книги [58, 63, 65, 66] содержат описание основных достижений в области ее решения.

Ввиду богатой истории исследования ЗК, широкое распространение и известность получили также ее различные вариации и обобщения. Например, ранее интенсивно исследовалась только ЗК на минимум. Однако в последние десятилетия все больше внимания уделяется задаче коммивояжера на максимум (TSP-max). Известно, что для этой задачи в ее общей постановке существует порог неприближаемости в классе полиномиальных алгоритмов (в предположении Р -ф NP) [46]. В работах [12, 15, 18, 19, 24, 32, 46, 52, 55] были предложены полиномиальные алгоритмы для ЗК на максимум с гарантированными оценками точности. Долгое время наилучшим полиномиальным алгоритмом для TSP-max с гарантированной оценкой точности оставался |-приближенный алгоритм Сердюкова [18]. За последние годы этот результат был незначительно усилен разными авторами за счет построения рандомизированных алгоритмов с оценками || — е [52] и Щ — г [35] (для любой константы е > 0), а также детерминированных алгоритмов с оценками || — £ [34] и Щ — £ [69], основанных на дерандомизации алгоритма из [52].

Другим естественным обобщением классической ЗК является задача об т коммивояжерах (га-Peripatetic salesman problem или m-PSP), состоящая в поиске в полном взвешенном неориентированном графе т реберно непересекающихся гамильтоновых циклов с минимальным или максимальным суммарным весом ребер. Наибольшее внимание уделяется задаче о двух коммивояжерах (2-Р8Р), которая рассматривается как в случае произвольной, так и метрической весовой функции, а также для более специальных классов графов с весами ребер 1 и 2 или же с весовой функцией ги : Е —► [1, д], где д — заданое число.

С тех пор как задача 2-Р8Р была впервые упомянута в [57], появилось много работ, посвященных ее исследованию. В [39] было доказано, что задача о существовании двух реберно непересекающихся гамильтоновых циклов в неориентированном графе А^Р-полна, что влечет АТР-трудность задачи 2-РБР как на минимум, так и на максимум даже в случае, если веса ребер принимают лишь значения 1 и 2.

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

В [38] рассмотрены некоторые полиномиально разрешимые случаи задачи 2-РБР на минимум. Работы [39]—[41] посвящены построению и анализу нижних и верхних оценок в задаче 2-РБР на минимум с целью их использования в методе ветвей и границ. В работе [42] представлен полиэдральный подход к решению ш-РБР.

Один из методов, применяемых во многих алгоритмах приближенного решения ТБР и 2-Р8Р, состоит в построении гамильтоновых циклов из так называемых частичных туров. Частичным туром в неориентированном графе называется набор из вершинно непересекающихся цепей, покрывающих все вершины графа. Очевидно, что добавлением ребер, соединяющих концевые вершины различных цепей частичного тура, можно получить гамильтонов цикл. Если же дана пара реберно непересекающихся туров, или непересекающиеся гамильтонов цикл и тур, то, добавляя ребра специальным образом, можно получить пару реберно непересекающихся гамильтоновых циклов. При этом построенная пара циклов будет тем ближе по весу к оптимальной, чем "лучше" исходные туры. Таким образом, приближенное решение 2-РБР может быть сведено к задаче отыскания подходящих частичных туров. Эта идея используется во всех алгоритмах, представленных в главах 2 и 3 диссертации.

В работе Агеева, Бабурина, Гимади [1] для приближенного решения задачи 2-Р8Р на максимум был предложен алгоритм с оценкой временной сложности 0(п3) и гарантированной оценкой точности В основе алгоритма лежит идея, впервые реализованная Сердюковым [18] при построении уже упомянутого приближенного алгоритма для ТБР-тах с оценкой точности На первом этапе алгоритма Сердюкова в графе находятся 2-фактор и паросочетание максимального веса, суммарный вес которых составляет не менее | от веса оптимального решения. Далее алгоритм разбивает найденные 2-фактор и паросочетание на два частичных тура, каждый из которых дополняется до гамильтонова цикла. Максимальный по весу из этих циклов дает решение 2-Р8Р-тах с оценкой точности |. В алгоритме Агеева, Бабурина, Гимади разбиению на два реберно непересекающихся частичных тура подвергается кубический (или "почти кубический") остовный подграф максимального веса.

В главе 2 диссертации представлен алгоритм А7/9 для задачи 2-Р8Р-тах, имеющий лучшую на сегодняшний день оценку точности | ~ 0.778 и кубическую временную сложность. Данный алгоритм основан на описанной выше идее Сердюкова. Кроме того, в нем развиты идеи, ранее использованные в работе Гимади, Глазкова и Глебова [11] при построении |-приближенного алгоритма для задачи 2-РБР на минимум с весами ребер 1 и 2. В качестве исходного подграфа, подвергающегося разбиению на непересекающиеся по ребрам частичные туры, используется 4-регулярный остовный подграф максимального веса. Ключевым для алгоритма А7/д является построение реберных раскрасок начальной пары частичных туров (полученной применением специальной процедуры из

11]) в два и в три цвета, позволяющих получить шесть альтернативных пар реберно непересекающихся частичных туров, наилучшая из которых имеет суммарный вес ребер не менее § от оптимального. Более того, благодаря структурным свойствам начальной пары частичных туров, полученные туры удается дополнить до пары реберно непересекающихся гамильтоновых циклов, что далеко не всегда возможно в случае произвольных реберно непересекающихся частичных туров. Примечательно, что полученная для рассматриваемой задачи оценка точности | превосходит наилучшие известные на данный момент оценки для "более простой" задачи одного коммивояжера на максимум.

Для случая 2-Р8Р-шах, в котором веса ребер принимают значения из заданного промежутка в разделе 2.7 диссертации предложена модификация алгоритма А7/9, имеющая гарантированную оценку точности что улучшает ранее полученную Гимади, Ивониной [48] оценку

Другой разновидностью задачи маршрутизации, исследуемой в диссертации, является задача о двух коммивояжерах на минимум с двумя различными весовыми функциями, принимающими значения 1 и 2 (задача 2-PSP-min-2w-(l, 2)). В этой задаче дан неориентированный полный п-вершинный граф С(У,Е) и две весовые функции: и>1 : Е —> {1,2}, гУ2 : Е —■> {1,2}. Требуется найти непересекающиеся по ребрам гамиль-тоновы циклы Н\ и #2 такие, что их суммарный вес ъи^Нх) + «^(-й^), IV(Щ) = ]Сеея*'ш(е)> ^ е {1)2}, минимален.

Отметим, что для задачи одного коммивояжера на минимум в случае произвольной весовой функции нет полиномиальных алгоритмов с гарантированными оценками точности. Для метрической ТБР-тт известен алгоритм Кристофидеса [36] и Сердюкова [17] с оценкой |. В случае весов ребер 1 и 2 Пападимитриу и Яннакакисом [62] был получен алгоритм с оценкой точности Для этой же задачи Берман и Карпински [25] предложили алгоритм, для которого анонсировали оценку точности о но данный результат не был строго обоснован.

Уже для задачи о двух коммивояжерах на минимум с весами ребер 1 и

2 (2-Р8Р(1,2)-тт) Глазков, Гимади и Глебов получили вышеупомянутый алгоритм с оценкой | в случае, когда весовые функции для обоих циклов одинаковы. В случае двух различных весовых функций (задача 2-Р8Р-min-2w-(l, 2)) в [23] был предложен алгоритм с оценкой у.

В главе 3 диссертации представлены два приближенных алгоритма, усиливающие результат из [23]. В первой части главы получен алгоритм А7/5 с оценкой точности | (без учета аддитивной константы) и временной сложностью 0(гг3), а во второй ее части — алгоритм Л4/3, имеющий лучшую оценку точности | (также без учета аддитивной константы), но худшую оценку временной сложности О(п5).

В основу обоих алгоритмов положена идея метода из [25], заключающаяся в построении и последовательном "улучшении" пары реберно непересекающихся туров из ребер единичного веса и последующем замыкании этих туров в непересекающиеся гамильтоновы циклы. Под "улучшением" туров понимается такое их локальное преобразование, при котором уменьшается либо общее число цепей и циклов, составляющих туры, либо число одновершинных цепей — синглов (или обобщающих их (я, д)-деревев в случае алгоритма А4/3). Для того, чтобы гарантировать возможность улучшающего преобразования в случае, если нужное качество решения еще не достигнуто, применяется введенная в [25] модификация метода перераспределения зарядов вершин. Аналогично тому, как это обычно делается при работе с плоскими графами, для каждой вершины графа определяется ее заряд, т. е. число, определяемое на основе туров оптимального решения. В дальнейшем происходит перераспределение этих зарядов между вершинами графа с сохранением их суммы.

Дополнительные трудности при разработке и анализе алгоритмов главы 3 (по сравнению со случаем двух одинаковых весовых функций) связаны с тем, что в данном случае невозможна свободная переброска ребер из одного тура в другой. Из-за этого оказались неприменимыми многие методы, ранее использовавшиеся в задаче о двух коммивояжерах с весами ребер 1 и 2 (см. [1, 2, 11]). Значительный объем обоснования оценок точности алгоритмов А7/5, Л4/3 связан с рассмотрением большого числа случаев, соответствующих различным типам вершин графа. Тип вершины определяется тем, является ли она в туре концевой или внутренней вершиной цепи, вершиной цикла, синглом (^-вершиной) или так называемой Q-вершиной (s, д)-дерева (независимо для каждого тура).

В разделе 3.3, посвященном построению и анализу алгоритма Aj/3, понятие тура, традиционно используемое в большинстве работ, посвященных задачам одного и двух коммивояжеров, существенно модифицировано за счет включения в туры наряду с цепями и циклами так называемых (s, д)-деревьев, определение и свойства которых рассматриваются в пункте 3.3.1 диссертации.

Есть все основания полагать, что разработанные в диссертации методы, связанные с применением раскрасок ребер, перераспределением зарядов и использованием принципиально новых объектов, таких как (s, д)-деревья, окажется полезными при разработке других алгоритмов решения задач маршрутизации, в первую очередь, задач одного, двух и более коммивояжеров на минимум и на максимум.

Результаты диссертации докладывались на международных научных студенческих конференциях «Студент и научно-технический прогресс» (Новосибирск, 2007, 2008), на Всероссийских конференциях «Методы оптимизации и экономические приложения» (Омск, 2009), «Дискретная оптимизация и исследование операций» (Алтай, 2010), «Математическое программирование и приложения» (Екатеринбург, 2011), на Международных конференциях по исследованию операций «European Conference on Operational Research» (Бонн, 2009), «Optimal Discrete Structures and Algorithms» (Росток, 2010), на научных семинарах Института математики им. СЛ. Соболева СО РАН.

Все результаты диссертации опубликованы в статьях [7, 8, 9, 10, 14].

Диссертант выражает искреннюю признательность своему научному руководителю Алексею Николаевичу Глебову за постоянную поддержку и внимание к работе.

1. Агеев A.A., Бабурин А. Е., Гимади Э.Х. Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса. // Дискрет, анализ и исслед. операций. 2006. Сер. 1. Т. 13, № 2. С. 11-20.

2. Бабурин А. Е., Гимади Э.Х., Коркишко Н. М. Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых цикла минимального веса. // Дискрет, анализ и исслед. операций. 2004. Сер. 2. Т. 11, № 1. С. 11-25.

3. Бородин О. В. Доказательство гипотезы Б. Грюнбаума об ациклической 5-раскрашиваемости плоских графов // Доклады АН СССР. 1976. Т. 231. С. 18-20.

4. Бородин О. В., Глебов А. Н. О разбиении плоского графа обхвата 5 на пустой и ациклический подграфы // Дискретный анализ и исследование операций. 2001. Сер. 1. Т. 8, № 4. С. 34-53.

5. Бородин О. В., Иванова А. О. Почти правильные 2-раскраски вершин разреженных графов // Дискретный анализ и исследование операций. 2009. Т. 16, № 2. С. 16-20.

6. Бородин О. В., Иванова А. О. Разбиение разреженных плоских графов на два подграфа малой степени // Сибирские электронные математические известия, (http://semr.math.nsc.ru). 2009. Т. 6. С. 1316.

7. Глебов А.Н., Гордеева A.B., Замбалаева Д.Ж. Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями // Сибирские электронные математические известия (htpp://semr.math.nsc.ru). 2011. Т. 8. С. 296-309.

8. Глебов А.Н., Замбалаева Д.Ж. Полиномиальный алгоритм с оценкой точности 7/9 для задачи о двух коммивояжерах на максимум // Дискретный анализ и исследование операций. 2011. Т. 18, № 4. С. 17-48.

9. Глебов А.Н., Замбалаева Д.Ж. Приближенный алгоритм решения задачи о двух коммивояжерах на минимум с различными весовыми функциями // Дискретный анализ и исследование операций. 2011. Т. 18, № 5. С. 11-37.

10. Глебов А.Н., Замбалаева Д.Ж. Путевые разбиения планар-ных графов // Сибирские электронные математические известия (htpp://semr.math.nsc.ru). 2007. Т. 4. С. 450-459.

11. Гимади Э. X., Глазков Ю. В., Глебов А. Н. Приближенные алгоритмы решения задачи о двух коммивояжерах в полном графе с весами ребер 1 и 2 // Дискрет, анализ и исслед. операций. Сер. 2. 2007. Т. 14, № 2. С. 41-61.

12. Гимади Э. X., Сердюков А. И. О некоторых результатах для задачи коммивояжера на максимум // Дискрет, анализ и исслед. операций. 2001. Т. 8, № 1. С. 22-39.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982.

14. Замбалаева Д.Ж. Разбиение плоского графа с обхватом 7 на два звездных леса// Дискретный анализ и исследование операций. 2009. Т. 16, № 3. С. 20-46

15. Косточка А. В., Сердюков А. И. Полиномиальные алгоритмы с оценками 3/4 и 5/6 для задачи коммивояжера на максимум. // Управляемые системы. Сб. науч. тр. 1985. Вып. 26. С. 55-59.

16. Мельников JI.C., Петренко И.В. О путевых ядрах и разбиениях в неориентированных графах// Дискретный анализ и исследование операций. 2002. Сер. 1. Т. 9, № 2. С. 21-35.

17. Сердюков А. И. О некоторых экстремальных обходах в графах. // Управляемые системы. Сб. науч. тр. 1978. Вып. 17. С. 76-79.

18. Сердюков А. И. Алгоритм с оценкой для задачи коммивояжера на максимум. // Управляемые системы. Сб. науч. тр. 1984. Вып. 25. С. 80-86.

19. Сердюков А. И. Задача коммивояжера на максимум в конечномерных вещественных пространствах. // Дискретный анализ и исследование операций. 1995. Т. 2, № 1. С. 50-56.

20. Appel К., Haken W. The existence of unavoidable sets of geographically good configurations // Illinois J. Math. 1976. V. 20. P. 218-297.

21. Appel K., Haken W. The solution of the four-color-map problem // Scientific American. 1977. V. 237, N 4. P. 108-121.

22. Appel K., Haken W. The four color proof suffices // Math. Intelligencer. 1986. V. 8, N 1. P. 10-20.

23. A.E. Baburin, F.Della Croce, E.K. Gimadi, Y.V. Glazkov, V.Th. Paschos. Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 // Discrete Applied Mathematics. 2009. V. 157, N 9. P. 1988-1992.

24. Barvinok A.I. Two algorithmic results for the traveling salesman problem. // Math. Oper. Res. 1996. V. 21, N 1. P. 56-84

25. Berman P., Karpinski M. 8/7-approximation algorithm for (1,2)-TSP // Proc. of the 17th annual ACM-SIAM symposium on discrete algorithms, SODA 2006 (Miami, January 22-26, 2006). New York: ACM Press, 2006. P. 641-648.

26. Borodin O. V. On acyclic colorings of planar graphs // Discrete Math. 1979. V. 25, N 3. P. 211-236.

27. Borodin O. V. Four problems on plane graphs raised by Branko Griinbaum // Contemporary Math. 1993. V. 147. P. 149-156.

28. Borodin O.V., Kostochka A.V., Sheikh N.N., Yu G.Decomposing a planar graph with girth 9 into a forest and matching // Europ. J. Combin. 2008. V. 29, N 5. P. 1235-1241.

29. Borowiecki M., Broere I., Frick M., Mihok P., Semanisin G. Asurvey of hereditary properties of graphs // Discussiones Mathematicae Graph Theory. 1997. V. 17, N 1. P. 5-50.

30. Broere I., Dorfling M., Dunbar J. E., Frick M. A path(ological) partition problem // Discussiones Mathematicae Graph Theory. 1998. V. 18, N 1. P. 113-125.

31. Broere I., Hajnal P., Mihok P., Semanisin G. Partition problems and kernels of graphs // Discussiones Mathematicae Graph Theory. 1997. V. 17, N 2. P. 311-313.

32. Burkard R.E., Deineko V. G., Van Dal R., Van Der Veen J. A. A., Woeginger G.J. Well-solvable special cases of the traveling salesman problem: A Survey // SIAM Review. 1998. V. 40, N 3. P. 496546.

33. Chartrand G., Kronk H. V. The point-arboricity of planar graphs // J. London Math. Soc. 1969. V. 44, N 4. P. 612-616.

34. Chen Z.-Z., Okamoto Y., Wang L. Improved deterministic approximation algorithms for Max TSP // Inform. Process. Lett. 2005. V. 95, N 2. P. 333-342.

35. Chen Z.-Z., Wang L. An improved randomized approximation algorithm for Max TSP // J. Comb. Optim. 2005. V. 9, N 4. P. 401432.

36. Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem // Technical report CS-93-19: Carnegie Mellon University, 1976.

37. Dantzig G. B., Fulkerson D. R., Johnson S. M. Solution of a large scale salesman traveling problem // Oper. res. 1954. V. 2. P.393-410.

38. De Brey M. J.D., Volgenant A. Well-solved cases of the 2-peripatetic salesman problem // Optimization. 1997. V. 39, N 3. P.275-293.

39. De Kort J.B. J.M. Lower bounds for symmetric if-peripatetic salesman problems// Optimization. 1991. V. 22, N 1. P.113-122.

40. De Kort J.B. J.M. Upper bounds for the symmetric 2-peripatetic salesman problems// Optimization. 1992. V. 23, N 4. P.357-367.

41. De Kort J. B. J. M. A branch and bound algorithm for symmetric 2-peripatetic salesman problems// Europian J. of Oper. Res. 1993. V. 10, N 2. P.229-243.

42. Duchenne E., Laporte G., Semet F. Branch-and-cut algorithms for the undirected m-peripatetic salesman problem // Europian J. of Oper. Res. 2005 V. 162, N 3. P. 700-712.

43. Dunbar J. E., Frick M. Path kernels and partitions // Math. Combin. Comput. 1999. V. 31. P. 137-149.

44. Dunbar J. E., Frick M., Bullock F. Path partitions and Pn-free sets // Discrete Math. 2004. V. 289, N 1-3. P. 145-155.

45. Fijavz G., Juvan M., Mohar B., Skrekovski R. Planar graphs without cycles of specific lengths // Europ. J. Combin. 2002. V. 23, N 4. P. 377-388.

46. Fisher M. L., Nemhauser G. L., Wolsey L. A. An analysis of approximations for finding a maximum weight Hamiltonian circuit // Oper. Res. V. 27, N 6. P. 799-809.

47. Gabow H. N. An efficient reduction technique for degree-restricted subgraph and bidirected network flow problems // Proc. 15th annual ACM symposium on theory of computing (Boston, April 25-27, 1983). New York: ACM, 1983. P. 448-456.

48. Gimadi E. Kh., Ivonina E. V. Approximation algorithms for maximum-weight 2-Peripatetic Salesman Problem in complete graph with restricted distances // Discrete Applied Mathematics, submitted.

49. Grötzsch H. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Natur. Reihe. 1959. V. 8. P. 109-120.

50. Grünbaum B. Acyclic colorings of planar graphs // Israel J. Math. 1973. V. 14, N 3. P. 390-408.

51. S. L. Hakimi, J. Mitchem, E. F. Schmeichel Star arboricity of graphs // Discrete Math. 1996. V. 149, N 1-3. P. 93-98.

52. Hassin R., Rubinstein S. Better approximations for max TSP // Inform. Process. Lett. 2000. V. 75. P. 181-186.

53. Heesch H. Untersuchungen zum Vierfarbenproblem Mannheim-Vienna-Zurich: Bibliographisches Institut. 1969.

54. Junger M., Reinelt G., Rinaldi G., The Traveling Salesman Problem // Handbook on Operation Research and Management Sciences. Network models / Ed. by M. Ball, T. Magnanti, C.M Monma, G.L. Nemhauser. Amsterdam: North Holland, 1995. V. 7. P. 225-330.

55. Kosaraju S.R., Park J.K., Stein C. Long tours and short superstrings // 35st IEEE symp. on Foundations of Computer Science. 1994. P. 166-177.

56. Kostochka A. V., Melnikov L. S. Note to the paper of Grünbaum on acyclic colorings // Discrete Math. 1976. V. 14, N 4. P. 403-406.

57. Krarup J. The perepatetic salesman and some related unsolved problems// Combinatorial programming: methods and applications (Proc. NATO Advanced Study Inst., Versailles, 1974). 1975. P. 173-178.

58. Lawler E. L., Lenstra J.K., Rinnoy Kan A. H., Shmoys D.B.The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester, 1985.

59. Melamed 1.1., Sergeev S.I., Sigal I. K. The traveling salesman problem. Approximations algorithms // Automat. Remote Control. 1990. P. 1459-1479.

60. Mihok J. Graphs, hypergraphs and matroids. Zielon Gora: Higher College Engrg., 1985.

61. C. St. J. A. Nash-Williams Decomposition of finite graphs into forests // J. London Math. Soc. 1964. V. 39. P. 12.

62. Papadimitriou C.H., Yannakakis M. The travelling salesman problem with distances One and Two // Math. Oper. Res. 1993. V. 18, N 1. P. 1-11.

63. Punnen A., Gutin G. The Traveling Salesman Problem and its variations Dortrecht/Boston/London, 2003.

64. Raspaud A., Wang W. On the vertex-arboricity of planar graphs // Europ. J. Combin. 2008. V. 29, N 4. P. 1064-1075.

65. Reinelt G. The Traveling Salesman: Computational Solutions for TSP Applications. Berlin: Springer-Verlag, 1994.

66. Slominski L. Propabilistic analysis of combinatorial algorithms: A „ bibliography with selected annotations // Computing. 1982. N. 28. P.257.267.

67. Stein S.K. B-sets and coloring problems // Bull. Amer. Math. Soc. 1970. V. 76, N 4. P. 805-806.

68. Stein S. K. B-sets and planar maps // Pacific J. Math. 1971. V. 37, N 1. P. 217-224.

69. Wang W., Lih K.-W. Choosability and edge choosability of planar graphs without 5-cycles // Appl. Math. Lett. 2002. V. 15, N 5. P. 561-565.