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

Лемма 3. Пусть <math>U \subseteq V \;</math>, #U нечетно. Пусть M – совершенное паросочетание с минимальным весом на U. Тогда <math>w(M) \le OPT/2 \;</math>.

Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем сокращение в H, получая обход H0 на G|U следующим образом: H порождает перестановку вершин в U, представляющую собой порядок, в котором они посещаются по ходу H. Соединим вершины U в порядке, заданном перестановкой. Каждому ребру в H0 соответствует путь в H, соединяющий две вершины этого ребра. Согласно неравенству треугольника, w(H0) < w(H). Поскольку #U является четным, H0 представляет собой объединение двух паросочетаний. Вес более легкого из них не превышает w(H0)/2 < OPT/2. □

Можно вычислить совершенное паросочетание с минимальным весом за время O(n3); см., например, [5].

Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 2(n — 1), а это четное число. Таким образом, совершенное паросочетание на U существует. Вес эйлерова обхода, очевидно, составляет w(T) + w(M). Согласно лемме 1, w(T) < OPT. Согласно лемме 3, w(M) < OPT/2. Вес w(H) вычисленного обхода H не превышает веса эйлерова обхода согласно неравенству треугольника, т.е. w(H) < |OPT. Таким образом, полученный алгоритм представляет собой алгоритм 3/2-аппроксимации, время выполнения которого составляет O(n3). □