next up previous
Next: Достаточный признак оптимальности Up: Элементы теории Previous: Классы эквивалентности

Нижняя оценка стоимости оптимального обхода

Дальнейшее изложение - только для неориентированных связных полных графов, $ \mathbf{n\geqslant 4}$.

Если граф не полный, то можно превратить его в полный, приписав недостающим рёбрам достаточно большую стоимость, например, равную общей сумме всех стоимостей рёбер первоначального графа, либо присвоив специальное значение $ \mathbf{+\infty}$ с естественными операциями сравнения и сложения.

Для каждого графа $ \mathbf{\Gamma}$ можно построить его подграф $ \mathbf{\Gamma_{MST}}$ - Минимальное Остовное Дерево - $ \mathbf{\left(Minimal\quad Spanning\quad Tree\right)}$. Этот подграф соединяет все вершины графа между собой, причём суммарная стоимость всех рёбер данного подграфа $ \mathbf{\Gamma_{MST}}$ минимальна. Если в графе $ \mathbf{\Gamma}$ существуют рёбра равной стоимости, то подграф $ \mathbf{\Gamma_{MST}}$, возможно, не единствен, но множества стоимостей рёбер, входящих в какой-либо подграф $ \mathbf{\Gamma_{MST}}$, совпадают, и значит, суммарная стоимость одна и та же, хотя порёберный состав разных $ \mathbf{\Gamma_{MST}}$ может быть различным.

Пусть $ \mathbf{\Gamma_{Opt}}$ - граф оптимального обхода. Обозначим $ \mathbf{S_{Opt}}$ - суммарная стоимость всех рёбер, входящих в оптимальный обход $ \mathbf{\Gamma_{Opt}}$. Это есть цена решения индивидульной $ \mathbf{TSP}$ - задачи. Таких обходов может быть несколько, с одной и той же величиной $ \mathbf{S_{Opt}}$. Обозначим, далее, $ \mathbf{S_{MST}}$ - суммарная стоимость рёбер подграфа $ \mathbf{\Gamma_{MST}}$, $ \mathbf{s_{OptMax}}$ - максимальная стоимость ребра в оптимальном обходе $ \mathbf{\Gamma_{Opt}}$, $ \mathbf{s_{MSTMax}}$ - максимальная стоимость ребра в подграфе $ \mathbf{\Gamma_{MST}}$.

Утверждение:

$\displaystyle \mathbf{S_{Opt}\geqslant S_{MST}+s_{MSTMax}}$

Доказательство: Вынем из оптимального обхода $ \mathbf{\Gamma_{Opt}}$ ребро с максимальной стоимостью $ \mathbf{s_{OptMax}}$. Тогда получаем некоторый линейный подграф $ \mathbf{\Gamma_{Ham}}$ исходного графа $ \mathbf{\Gamma}$ - незамкнутый гамильтонов путь, проходящий через все вершины графа ровно по одному разу. Обозначим $ \mathbf{S_{Ham}}$ - суммарную стоимость всех рёбер этого подграфа. Очевидно, что

$\displaystyle \mathbf{S_{Opt}=S_{Ham}+s_{OptMax}}$

$\displaystyle \mathbf{S_{Ham}\geqslant S_{MST}}$

Затем вынем из подграфа $ \mathbf{\Gamma_{MST}}$ ребро с максимальной стоимостью $ \mathbf{s_{MSTMax}}$. Нет никаких проблем с неоднозначностью $ \mathbf{MST}$. Тогда подграф $ \mathbf{\Gamma_{MST}}$ распадётся на два собственных подграфа $ \mathbf{\Gamma_1}$ и $ \mathbf{\Gamma_2}$, каждый из которых является графом-деревом. В любом обходе первоначального графа $ \mathbf{\Gamma}$ должны существовать по крайней мере два разных ребра, соединяющих подграфы $ \mathbf{\Gamma_1}$ и $ \mathbf{\Gamma_2}$. Стоимость любого из этих рёбер не ниже, чем $ \mathbf{s_{MSTMax}}$. Очевидно, что

$\displaystyle \mathbf{s_{OptMax}\geqslant s_{MSTMax}}$

, так как принятие противоположного приводит к противоречию. Таким образом, первоначальное утверждение доказано. Приятная новость состоит в том, что эта нижняя оценка на самом деле достигается.

Бродников А.П. 2006-11-05
Используются технологии uCoz