32. Постановка задачи коммивояжера на языке теории графов.

Задача коммив-ра может быть сформ-на как зад. на графе в след. постановке: построить граф G(X, A), вершины кот. соотв-ют городам в зоне коммив-ра, а дуги отображают коммуникации, соединяющие пары городов. Пусть длина a(х, у) > 0 каждой дуги (х, у) є А равна расстоя­нию, стоимости или времени. Контур, включающий каждую вершину графа G хотя бы один раз, называется маршрутом коммивояжера. Контур, вкл. кажд. вершину графа G ровно 1 раз, наз-ся гамильтоновым контуром (по имени ирландского математика Вильяма Роуана Гамильтона, ко­т. в 1859 г. 1ым начал изучение этих задач).

Города — это вершины графа. Дороги между городами — это ориентированные ребра графа. Длина соотв-щей дороги — это вес ребра. Граф должен быть полным, т.е. в нем имеются все возможные ребра. Если граф не явл. полным, то его можно дополнить недостающими ребрами с весом. Путь, кот. требуется найти, - это ориентированный оставный, простой цикл, минимального веса в графе. Такие циклы называются гамильтоновыми.

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