next up previous
Next: Нижняя оценка стоимости оптимального Up: Элементы теории Previous: Элементы теории

Классы эквивалентности

Если для каждого ребра, входящего в вершину $ \mathbf{V_i}$, к стоимости этого ребра $ \mathbf{\sigma_{ij}}$ прибавить величину $ \mathbf{\epsilon_i}$, и для каждого ребра, исходящего из вершины $ \mathbf{V_i}$, к стоимости добавить величину $ \mathbf{\tau_i}$, то суммарная стоимость любого обхода увеличится на постоянную для всех обходов величину, т.е. $ \mathbf{S_{new}=S_{old}+\epsilon_i+\tau_i}$. Это означает, что оптимальный обход не изменится, изменится только его стоимость на известную заранее величину, и вместо начальной задачи с тем же успехом можно искать решение задачи модифицированной. В случае симметричной матрицы стоимостей, т.е. неориентированного графа, обе добавляемых величины должны быть равны. Будем называть две индивидуальных симметричных $ \mathbf{TSP}$-задачи со стоимостями $ \mathbf{\sigma_{ij}}$ и $ \mathbf{\hat\sigma_{ij}}$ эквивалентными, если существует такой вектор $ \mathbf{E}$ добавленных стоимостей $ \textbf{(термин!)}$, что

$\displaystyle \mathbf{\hat\sigma_{ij}=\sigma_{ij}+E_i+E_j}$

В несимметричном случае для эквивалентности задач должны существовать два вектора $ \mathbf E$ и $ \mathbf F$ добавленных стоимостей, таких, что

$\displaystyle \mathbf{\hat\sigma_{ij}=E_i+\sigma_{ij}+F_j}$

Аналогично легко убедиться, что если для каждого ребра графа прибавить к его стоимости одну и ту же величину, то задача останется в этом же классе эквивалентности. Это позволяет считать минимальную стоимость ребра графа равной 0 (слипшиеся точки).

Для ориентированного графа назовём функцию $ \mathbf{Offset\left(i, \sigma_{in}, \sigma_{out}\right)}$ тернарной функцией или операцией смещения для вершины $ \mathbf i$. Эта операция применима к каждому входящему в вершину $ \mathbf{v_i}$ ребру и увеличивает его стоимость на $ \mathbf{\sigma_{in}}$. Она же применима к каждому исходящему из вершины $ \mathbf{v_i}$ ребру и увеличивает его стоимость на $ \mathbf{\sigma_{out}}$. Величины $ \mathbf{\sigma_{in}}$ и $ \mathbf{\sigma_{out}}$ могут иметь любые значения и знаки. Для неориентированного графа (т.е. для графа с симметричной матрицей) операция смещения бинарна с двумя параметрами: $ \mathbf{i}$ и $ \mathbf{\sigma}$. Любая операция смещения оставляет задачу в том же классе эквивалентности.

Множество индивидуальных задач $ \mathbf{TSP}$ разделяется на смежные классы эквивалентных между собой задач. Возникает потребность развить теорию, найти в каждом классе экстремальные элементы, т.е. такие задачи, которые приводили бы к решению кратчайшим путём. В других ветвях математики такие элементы часто называются нормальными, каноническими, и т.д.

Сразу можно заметить, что искать алгоритмы решения $ \mathbf{TSP}$-задачи для графов с выполненным неравенством треугольника, или для планарных графов, вероятно, бессмысленно, и эти темы следует закрыть. Действительно, для любого графа $ \mathbf{TSP}$-задачи с нарушениями неравенства треугольника можно построить такую ей эквивалентную, для которой это неравенство соблюдается. Добиться этого можно, просто прибавив к стоимости каждого ребра большую величину, например, равную максимальной стоимости ребра в первоначальном графе. Либо кропотливо модифицировать каждый проблемный треугольник, выполняя операцию с положительным вычисленным смещением для нужной вершины. Следует отметить, что неравенство треугольника устойчиво к положительным смещениям, и, значит, новых нарушений неравенства треугольника не возникнет.

У планарного графа стоимость ребра равна его длине. Для любых четырёх вершин графа $ \mathbf{A,B,C,D}$ с точностью до переименования вершин выполняется одно из двух равенств:

$\displaystyle \mathbf{S_{\Delta BCD}=S_{\Delta ABC}+S_{\Delta ABC}+S_{\Delta ABD}}$

$\displaystyle \mathbf{S_{\Delta ABC}+S_{\Delta BCD}=S_{\Delta ABD}+S_{\Delta ACD}}$

В этих формулах $ \mathbf{S_{\Delta}}$ - площадь соответствующего треугольника, данную величину можно выразить через длины рёбер по формуле Герона, и тогда становится ясно, что у $ \mathbf{TSP}$-задачи с планарным графом существует ей эквивалентная с непланарным графом.

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