# цикла 2*СostFr.

цикла 2*СostFr. Неравенство треугольника обеспечивает результат: следующую оценку шага 4 - CostAp&lt;2*CostFr, а значит, CostAp&lt;2*CostBet. Рассмотрим пример. Для исходных данных, приведенных в п. 2.1.7, на рисунке жирными линиями выделен каркас минимального веса. Тонкие линии добавляются на шаге 2. Получаем эйлеров граф. Затем эйлеров цикл (маршрут) преобразуется в путь коммивояжера (шаг 4). Согласно неравенству треугольника мы получаем: d2,9+d9,8&gt;d2,8; d2,8+d8,1&gt;d2,1; d2,1+d1,7&gt;d2,7. Суммируя левые и правые части неравенств, получаем: d2,9+d9,8+d8,1+d1,7&gt;d2,7. Для рассмотренного примера CostAp равна 202. Это ~ 1.28*CostBet. Структуры данных. Помимо названных ранее массивов А - матрица расстояний и массива Way - хранение искомого пути, требуется «что-то» для хранение описания каркаса. Пусть это будет массив B (B:array[1..Nmax,1..Nmax] of boolean). Элемент B[i,j], равный true, говорит о том, что ребро (i,j) графа принадлежит каркасу. Общая логика. Begin init;{ввод

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