Формализуем условие в терминах теории графов

Формализуем условие в терминах теории графов. Города  будут вершинами графа, а дороги между городами — ориентированными (направленными) ребрами графа, на каждом из которых задана весовая функция: вес ребра — это длина соответствующей дороги. Путь, который требуется найти,  это — ориентированный остовный простой цикл минимального веса в орграфе (напомним: цикл называется остовным, если он проходит по всем вершинам графа; цикл называется простым, если он проходит по каждой своей вершине только один раз; цикл называется  ориентированным, если начало каждого последующего ребра совпадает с концом предыдущего; вес цикла — это сумма весов его ребер; наконец, орграф называется полным, если в нем имеются все возможные ребра); такие циклы называются также гамильтоновыми.

            Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес  ¥, считая, что  ¥ — это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом ¥  можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе.

            Отсюда следует, что задачу о коммивояжере достаточно решить для полных орграфов с весовой функцией. Сформулируем  теперь это в окончательном виде: пусть  — полный ориентированный граф  и  — весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

Ссылка на основную публикацию
Adblock detector