5.2. Нижняя граница из задачи о кратчайшем остове

Для графа с симметричной матрицей весов (расстояний) С, т. е. для неориентированного графа, нижнюю границу для решения задачи коммивояжера можно получить по кратчайшему остову графа следующим образом. Пусть установлено, что ребро входит в оптимальный цикл задачи коммивояжера. Если это ребро удалить из цикла, то получится цепь, состоящая из ребер, проходящая через все вершины, начиная с вершины и оканчивающаяся в Так как вес кратчайшего остова, скажем является нижней границей для веса этой цепи, то длина кратчайшего остова плюс с будет нижней границей для веса оптимального решения задачи коммивояжера.

В общем случае заранее не известно, какие ребра содержатся в оптимальном цикле, но самое длинное ребро в цикле должно быть [15] не короче, чем Здесь вторая ближайшая вершина к вершине Таким образом, величина

является нижней границей веса решения в задаче коммивояжера.