Оглавление
Введение
1 Путевые разбиения плоских графов
1.1 Основные определения и обозначения.
1.2 тразбиваемость плоских графов с обхватом 5
1.3 3,3разбиваемость плоских графов с обхватом 7
1.3.1 Простейшие свойства контрпримера к теореме 2 . .
1.3.2 Формула Эйлера.
1.3.3 Свойства граней минимального контрпримера .
1.3.4 Окрестности вершин степени 4.
1.3.5 Проверка неотрицательности зарядов после перераспределения
2 Полиномиальный алгоритм с оценкой точности 79 для задачи о двух коммивояжерах на максимум
2.1 Постановка задачи, определения и обозначения.
2.2 Описание алгоритма
2.3 Построение туров в связном 4регулярном графе, не
изоморфном Кг0 и
2.3.1 Построение базовых туров Ту и Т.
2.3.2 Разбиение туров Ту и Т2
2.3.3 Свойства туров М и М и М и М.
2.3.4 Построение туров Тх и Т2.
2.4 Построение реберно непересекающихся цепей для компонент связности О4.
2.4.1 Случай компоненты связности, не изоморфной
и КАЛ .
2.4.2 Случай компоненты связности, изоморфной К или
2.5 Дополнение пары частичных туров до гамильтоновых циклов
2.5.1 Описание процедуры Яц2
2.5.2 Обоснование процедуры Н.
2.6 Доказательство теоремы 3.
2.7 Случай весов ребер из промежутка 1,д.
3 Полиномиальные приближенные алгоритмы для задачи о двух коммивояжерах на минимум с двумя весовыми функциями, принимающими значения 1 и 2
3.1 Основные определения и обозначения.
3.2 Полиномиальный 75приближенный алгоритм
для задачи 2i2, 2
3.2.1 Описание алгоритма А75.
3.2.2 Оценка точности и временная сложность алгоритма
3.2.3 Доказательство леммы 3.3
3.2.4 Обоснование временнбй сложности алгоритма Л75 .
3.3 Полиномиальный 43приближенный алгоритм
для задачи 2Р8Ртт21,2
3.3.1 Основные определения и обозначения
3.3.2 Описание алгоритма Л43.
3.3.3 Оценка точности и временная сложность алгоритма
3.3.4 Доказательство леммы 3.6
3.3.5 Обоснование временной сложности алгоритма Л43 .
Литература
- Київ+380960830922