Гамильтонов путь
В математической области теории графов гамильтонов путь (или отслеживаемый путь ) — это путь в неориентированном или ориентированном графе, который посещает каждую вершину ровно один раз. Гамильтонов цикл (или гамильтонова схема ) — это гамильтонов путь, который является циклом . Определение того, существуют ли такие пути и циклы в графах, является гамильтоновой задачей пути , которая является NP-полной .
Гамильтоновы пути и циклы названы в честь Уильяма Роуэна Гамильтона , который изобрел икосианскую игру , теперь также известную как головоломка Гамильтона , которая включает в себя поиск гамильтонова цикла в графе ребер додекаэдра . Гамильтон решил эту проблему, используя исчисление Икоса , алгебраическую структуру , основанную на корнях из единицы и имеющую много общего с кватернионами (также изобретенными Гамильтоном). Это решение не распространяется на произвольные графы.
Несмотря на то, что они названы в честь Гамильтона, гамильтоновы циклы в многогранниках также были изучены годом ранее Томасом Киркманом , который, в частности, привел пример многогранника без гамильтоновых циклов. [1] Еще раньше гамильтоновы циклы и пути в графе коня на шахматной доске , конном туре , были изучены в 9 веке в индийской математике Рудратой , и примерно в то же время в исламской математике аль - Адли ар-Руми . . В Европе 18 века рыцарские туры были опубликованы Абрахамом де Муавром и Леонардом Эйлером . [2]
Гамильтонов путь или отслеживаемый путь — это путь , который посещает каждую вершину графа ровно один раз. Граф, содержащий гамильтонов путь, называется трассируемым графом . Граф называется гамильтоновым, если для каждой пары вершин существует гамильтонов путь между двумя вершинами.
Гамильтонов цикл , гамильтонова схема , обход вершины или цикл графа — это цикл , который посещает каждую вершину ровно один раз. Граф, содержащий гамильтонов цикл, называется гамильтоновым графом .
Подобные понятия могут быть определены для ориентированных графов , где каждое ребро (дугу) пути или цикла можно проследить только в одном направлении (т. е. вершины соединены стрелками, а ребра прослеживаются «хвост к голове»).
