26. Задача коммивояжера с неравенством треугольника. Алгоритм Кристофидеса

Задано множество городов V и для каждой пары городов u и v – стоимость проезда из u в v. Коммивояжер должен объехать все города, затратив на это минимально возможную сумму денег.

Метрическая задача коммивояжера

с(x,y)£c(x,z)+c(z,y)

Алгоритм Кристофидеса

Идея: дополним граф до эйлерова графа, добавив новые кратные ребра таким образом, чтобы степени всех вершин стали четными. Найдем в полученном графе эйлеров цикл H. Если в H каждая вершина встречается ровно 1 раз, то это гамильтонов цикл. Пусть вершина x встречается 2 раза …-u-x-v-… - второе вхождение x. Заменим в H ребра ux и xv на ребро uv, получив

новый цикл H’ .c(u,x)+c(x,v)£ c(uv), следовательно, с(H’) £c(H) Проделав это со всеми кратными вхождениями вершин, в конце концов получим гамильтонов цикл H’ такой, что с(H’)£c(H) Проделав это со всеми вершинами , в конце концов мы получим гамильтонов цикл H’,т.что с(H’)£c(H)

Какие ребра надо было добавлять вначале, чтоб когда добавляли нашелся эйлеров цикл?

//не знаю что это но не удаляла

(1. Находим минимальное остовное дерево T графа G

2. Пусть U – множество вершин T, имеющих нечетную степень, G[U] – подграф графа G, порожденный U. Найдем в G[U] совершенное паросочетание минимального веса

3. Добавим к дереву T все ребра M, если какое-то ребро из M там уже есть, то добавим кратное ему. Получим эйлеров граф, содержащий все вершины графа G. Найдем в нем эйлеров цикл H и “сожмем” его до гамильтонова цикла H’)