5.3. Двойственность

Определим как остовный подграф неориентированного графа образованный вершинами и теми ребрами графа которые использованы в оптимальном цикле коммивояжера. Аналогично определим графы образованные теми же вершинами, но ребра которых берутся из оптимальных решений задачи о назначениях и задачи о кратчайшем остове соответственно.

Граф обладает следующими свойствами:

(1) граф является связным, т. е. каждую вершину можно соединить с любой другой вершиной цепью,

(2) степень каждой вершины равна 2, т. е. каждая вершина инцидентна двум ребрам.

На рис. 10.9 (а) приведен пример -вершинного графа G (TSP).

Граф G(AP) не обязательно обладает свойством (1), как это видно из рис. 10.9 (б), но по определению обладает свойством

(2). Если, однако, окажется, что для решения задачи о назначениях выполняется и свойство (1), то это решение будет также решением задачи коммивояжера.

Для графа G(SST) свойство (1) выполняется по определению, во он может не иметь свойства (2). Если же окажется, что для кратчайшего остова свойство (2) выполняется — за исключением двух «конечных» вершин (скажем, которые необходимо имеют степень то кратчайший остов будет также кратчайшей цепью, проходящей через все вершин.

Рис. 10.9. Графы задач коммивояжера, о назначениях и о кратчайшем остове,

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

Таким образом, решения задач о назначениях и кратчайшем остове являются двойственными в том смысле, что они обладают свойствами, являющимися дополнительными по отношению к свойствам задачи коммивояжера. Теперь обнаруживаются два пути, могущие привести к решению последней задачи.

(I) Использовать решение задачи о назначениях (для которого выполняется свойство и добиться, чтобы это решение подчинялось свойству (1). (II) Использовать решение задачи о кратчайшем остове (для которого выполняется свойство и добиться выполнения свойства (2).

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