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

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

В диссертации метод перераспределения зарядов в его классической форме, наряду с техникой раскрасок вершин, применяется в главе 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., Бабурин А. Е., Гимади Э. Х. Полиномиальный алгоритм с оценкой точности ¾ для отыскания двух непересекающихся гамильтоновых циклов максимального веса. // Дискрет, анализ и исслед. операций. 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. Косточка А. В., Сердюков А. И. Полиномиальные алгоритмы с оценками ¾ и 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. 496 546.

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. 401 432.

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. Grotzsch H. Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Natur. Reihe. 1959. V. 8. P. 109−120.

50. Grunbaum 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 Grunbaum 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.