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

• Автор: Замбалаева, Долгор Жамьяновна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Новосибирск
• Количество страниц: 138 с. : ил.

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

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

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

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

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

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

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

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

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

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

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

2.2 Описание алгоритма А7/9
2.3 Построение туров Т/, Т2* в связном 4-регулярном графе, не
изоморфном К$ и К^4
2.3.1 Построение базовых туров Тх и Тг
2.3.2 Разбиение туров Тх и Тг
2.3.3 Свойства туров М и Мх и М и М[
2.3.4 Построение туров Т* и Т2*
2.4 Построение реберно непересекающихся цепей для компонент связности С4

2.4.1 Случай компоненты связности, не изоморфной К§
и К^4
2.4.2 Случай компоненты связности, изоморфной К$ или

2.5 Дополнение пары частичных туров до гамильтоновых циклов
2.5.1 Описание процедуры Н$
2.5.2 Обоснование процедуры Н^
2.6 Доказательство теоремы
2.7 Случай весов ребер из промежутка [1,д]
3 Полиномиальные приближенные алгоритмы для задачи о двух коммивояжерах на минимум с двумя весовыми функциями, принимающими значения 1 и 2
3.1 Основные определения и обозначения
3.2 Полиномиальный 7/5-приближенный алгоритм
для задачи 2-Р8Р-гшп-2'ил-(1,2)
3.2.1 Описание алгоритма Л7/5
3.2.2 Оценка точности и временная сложность алгоритма
40/5
3.2.3 Доказательство леммы 3
3.2.4 Обоснование временной сложности алгоритма А7/5
3.3 Полиномиальный 4/3-приближенный алгоритм
для задачи 2-РЗР-пнп-2'у-(1, 2)
3.3.1 Основные определения и обозначения
3.3.2 Описание алгоритма Л4/3
3.3.3 Оценка точности и временная сложность алгоритма
.44/з
3.3.4 Доказательство леммы 3
3.3.5 Обоснование временной сложности алгоритма Л4/3
Литература

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

шина адз — донор, т. е. 73 = 4, кз > 2 согласно (Й4а). Следовательно, № (у) > 1 - | - § - | = 0.
Пусть <і(ги4) > 3. Тогда 72 = по утверждению 1.1. Если ^ то ц2(ь) >1 — | — | — | = 0. Пусть Ц- > Так как 73 ф § по (Й4с), то 7з = 1 или 7з = кз = 1. В обоих случаях имеем г(/3) = 7. При этом
с- т/(0,1,0)
хотя бы одна из вершин г>2, г>з принадлежит 1/Д : в первом случае это
следует из свойства ((33), во втором — из леммы 1.6. Поскольку сі(іі) > 3, то г>з 0 У^0Д’0). Следовательно, г>2 Є У^0,1,0^. В этом случае грань /2 инцидентна двум 2-вершинам, откуда /2 Є Т1+, что противоречит ранее введенному предположению /2 Є Т1-72. Лемма 1.13 доказана.
Назовем ребро е = иу жестким, если <і(и) > 3, с1(у) > 5.
Лемма 1.14. Если V Є V — вершина степени 5, то /12(у) > 0.
Доказательство. Пусть у є V, сі(у) = 5. Тогда
р(у) = 2 с1(у) — 6 = 10 — 6 = 4.
Обозначим грани, инцидентные у, в циклическом порядке через /і /5. По свойству ((42) вершина у смежна не более чем с тремя 2-вершинами.
Случай 1. у — максимальная, т. е. смежна с тремя 2-вершинами. Тогда у инцидентна двум жестким ребрам, и рі(ь) = р(у) — 3-1 = 4 — 3 = 1. Рассмотрим грань /, инцидентную ровно одному жесткому ребру уу. Докажем, что вершина у отдает грани / по правилу ЙЗ не более При р(/) — ® это следует из (Йба) и (Й7). Пусть / = уу^ЩУаУьЩ Є Т1~7, с?(г>б) = 2, к — количество доноров грани /. Так как у Є Кпаж, то по свойству ((43) только одна из вершин Уі,У2 может быть (0,1,0)-вершиной. По этому же свойству, если У§ не донор, ТО ТОЛЬКО одна ИЗ вершин Нз, Уа может быть (0,1,0)-вершиной, и тогда 7 = | по (Й4). Если же у§ — донор, то к > 2, и 7 < согласно (БЧсД), откуда
Теперь рассмотрим грань / = уу...уі инцидентную двум жестким ребрам ууі, уур Докажем, что вершина у отдает грани / по правилу ЙЗ не более Пусть / Є Т1-7, к — количество доноров грани /. Если г(/) > 8, то 7 = согласно (Е6Ь), (Е7). Пусть I = 6. Если 7 = |, то по свойству