# di,j+dj,k&gt;di,k.

di,j+dj,k&gt;di,k. Рассмотрим идею алгоритма. Шаг1. Строится каркас минимального веса (алгоритмы Прима или Краскала). Примечание. Это не есть первое приближение, как в предыдущем алгоритме. Шаг 2. Путем дублирования каждого ребра каркас преобразуется в эйлеров граф. Шаг 3. Находим в построенном графе эйлеров цикл. Шаг 4. Эйлеров цикл преобразуем в гамильтонов цикл (или маршрут коммивояжера). Метод преобразования: последовательность вершин эйлерова цикла сокращается так, чтобы каждая вершина графа в получившемся цикле встречалась ровно один раз. Шаг 5. Закончить работу алгоритма. Получено приближенное решение задачи коммивояжера. Покажем , что стоимость приближенного решение CostAp не превосходит удвоенной стоимости оптимального решения CostBet. Пусть стоимость каркаса - CostFr. Тогда CostFr&lt;CostBet, так как при удалении из оптимального пути коммивояжера ребра получаем каркас с весом не большим, чем CostAp. Из правила построения эйлерова графа получаем, что вес построенного эйлерова

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа