Задача коммивояжёра: различия между версиями

С задачей коммивояжёра связана задача о поиске [[гамильтонов цикл|гамильтонового цикла]]. Примером такой задачи является [[задача о ходе коня]], известная по крайней мере с [[XVIII век]]а{{sfn|''Gross J. L., Yellen J.'' Graph theory and its applications, 2006|loc=с. 275}}. [[Эйлер, Леонард|Леонард Эйлер]] посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию», датированную 1759 годом<ref>Euler, Leonhard, [https://scholarlycommons.pacific.edu/euler-works/309/ Solution d’une question curieuse que ne paroit soumise à aucune analyse], Mémoires de l’académie des sciences de Berlin, 15 (1759) 1766, p. 310—337.</ref>. Другим примером задачи на поиск гамильтонового цикла является [[икосиан]]: математическая головомка, в которой надо пройти по [[додекаэдр]]у (графу с 20 узлами) побывав в каждой вершине ровно один раз. Эта задача была предложеннаяпредложена [[Гамильтон, Уильям Роуэн|Уильямом Гамильтоном]] в XIX веке, он же определил класс таких путей.