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

   Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющая неравенству треугольника.

Доказательство. Если удалить любое ребро гамильтонова обхода G, получим остовное дерево G.

Доказательство. Согласно лемме 1, <math>w(T) \le OPT \;</math>. Поскольку мы удваиваем каждое ребро T, вес T’ составляет <math>w(T') = 2w(T) \le 2 OPT \;</math>. В результате сокращения обхода на шаге 3 путь в T' заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, <math>w(H) \le w(T') \;</math>. Это доказывает утверждение по поводу эффективности аппроксимации.

Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным.

Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. Паросочетание M для графа G называется паросочетанием на <math>U \subseteq V \;</math>, если все ребра M состоят из двух вершин подмножества U. Такое паросочетание называется [[совершенное паросочетание|совершенным]], если каждая вершина из U инцидентна ребру из M.

   Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющей неравенству треугольника.