Дальнейшее изложение - только для неориентированных связных полных графов,
.
Если граф не полный, то можно превратить его в полный, приписав недостающим рёбрам достаточно большую стоимость, например, равную общей сумме всех стоимостей рёбер первоначального графа, либо присвоив специальное значение
с естественными операциями сравнения и сложения.
Для каждого графа
можно построить его подграф
- Минимальное Остовное Дерево -
. Этот подграф соединяет все вершины графа между собой, причём суммарная стоимость всех рёбер данного подграфа
минимальна. Если в графе
существуют рёбра равной стоимости, то подграф
, возможно, не единствен, но множества стоимостей рёбер, входящих в какой-либо подграф
, совпадают, и значит, суммарная стоимость одна и та же, хотя порёберный состав разных
может быть различным.
Пусть
- граф оптимального обхода.
Обозначим
- суммарная стоимость всех рёбер, входящих в оптимальный обход
. Это есть цена решения индивидульной
- задачи. Таких обходов может быть несколько, с одной и той же величиной
.
Обозначим, далее,
- суммарная стоимость рёбер подграфа
,
- максимальная стоимость ребра в оптимальном обходе
,
- максимальная стоимость ребра в подграфе
.
Утверждение:
Доказательство: Вынем из оптимального обхода ребро с максимальной стоимостью . Тогда получаем некоторый линейный подграф исходного графа - незамкнутый гамильтонов путь, проходящий через все вершины графа ровно по одному разу. Обозначим - суммарную стоимость всех рёбер этого подграфа. Очевидно, что
Затем вынем из подграфа ребро с максимальной стоимостью . Нет никаких проблем с неоднозначностью . Тогда подграф распадётся на два собственных подграфа и , каждый из которых является графом-деревом. В любом обходе первоначального графа должны существовать по крайней мере два разных ребра, соединяющих подграфы и . Стоимость любого из этих рёбер не ниже, чем . Очевидно, что