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

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

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

Теорема 4. Алгоритм 2 представляет собой алгоритм 3/2-аппроксимации с полиномиальным временем выполнения.

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