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