Гамильтоновы графы. 
Геометрическая теория графов

Гамильтоновы цепи и циклы

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

Рис. 61 Рис. 62 Рис. 63

Рис. 64 Рис. 65

Как показывают рис. 61−65, гамильтонов цикл существует не только для графа додекаэдра, но и для остальных Платоновых графов. На каждом из этих рисунков выделен один из таких замкнутых маршрутов.

Конечный граф называется гамильтоновым, если он обладает либо гамильтоновым циклом, либо гамильтоновой цепью. Ясно, что для каждого графа, для которого существует гамильтонов цикл, можно указать также и гамильтонову цепь. Для этого достаточно разорвать указанный цикл, удалив из него одно ребро (например последнее в цикле). Обратное, вообще говоря, не верно. Так, например, дерево, являющееся простой цепью, вообще не имеет циклов. Далеко не каждый граф содержит гамильтонову цепь (и тем более гамильтонов цикл). К сожалению, до сих пор не получено необходимого и достаточного условия гамильтоновости графов. Более того, не существует хорошего алгоритма (не сводящегося к полному перебору путей) для отыскания гамильтоновых цепей в графах общего вида. В теории гамильтоновых графов известно лишь несколько интересных результатов для некоторых классов графов специального вида.