9. Экстремальные задачи теории графов: задача коммивояжера, «жадный» алгоритм

Определение. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Определение. Если задача состоит в том, чтобы найти экстремум (максимум или минимум) определенной функции от этих значений, то её принято называть экстремальной задачей.

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

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

Рассмотрим один из них, относящийся к классу так называемых «жадных» алгоритмов. Он состоит в следующем:

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

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