Задача коммивояжера. Вопросы теории

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