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

Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 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 \frac{3}{2} OPT \;</math>. Таким образом, полученный алгоритм представляет собой алгоритм 3/2-аппроксимации, а его время выполнения составляет <math>O(n^3) \;</math>.  <math>\Box</math>

Анализ алгоритма 2 несложен. Примером может служить метрическое пополнение графа, изображенного на рис. 1. Его единственное минимальное остовное дерево состоит из всех сплошных ребер. Оно содержит только две вершины с нечетными степенями. Ребро между этими двумя вершинами имеет вес <math>(1 + \epsilon)(n + 1) \;</math>. Сокращений не требуется; вес обхода, вычисленного алгоритмом, равен <math>\approx 3 n \;</math>. Оптимальный обход состоит из всех пунктирных ребер, а также самого левого и самого правого сплошных ребер. Вес этого обхода составляет <math>(2n - 1)(1 + \epsilon) + 2 \approx 2n \;</math>.