Гамильтонов цикл. Взвешенные графы

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

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

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

Решение первой подзадачи связано с построением гамильтонового цикла.

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

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

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

Практическую ценность такого условия можно показать на примере задачи о прохождении коня через все клетки шахматной доски, не заходя ни на одну дважды. Известно, что гамильтонова цепь для данной задачи существует, и не единственная. При этом, сформулированное ранее достаточное условие требует для каждой вершины степень не менее 32, хотя реальные степени находятся в диапазоне от 2 до 8.

Что касается второй подзадачи, то решить ее в принципе просто, поскольку число всех маршрутов конечно. Для этого нужно организовать полный перебор всех маршрутов, вычислить их длины и выбрать самый короткий. Если число городов невелико, то полный перебор всех маршрутов, например, начинающихся и заканчивающихся в городе А, можно хорошо организовать воспользовавшись вспомогательным графом, называемым граф – дерево, а также введя понятие взвешенного графа.

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

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