Понятие о гамильтоновых циклах

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

Распространенная интерпретация задачи о гамильтоновых циклах состоит в следующем. Обед накрыт на круглом столе. Среди гостей некоторые являются друзьями. При каких условиях можно рассадить всех так, чтобы по обе стороны каждого из присутствующих сидели его друзья?

Подобная задача сформулирована и решена Киркманом. Одиннадцать министров ежедневно садятся за круглый стол. Как их рассаживать, если желательно, чтобы каждый из них имел на каждом заседании новых соседей? Сколько дней это может продолжаться?

Эта задача сводится к отысканию наибольшего числа гамильтоновых циклов без общих ребер в полном графе с одиннадцатью вершинами . В данном случае существует только пять циклов без общих ребер:

,

,

,

,

.

Эти циклы получаются вращением линии, проведенной на рис. 3 в направлении стрелок. В более общем случае вершин можно найти гамильтоновых циклов без общих ребер.

c i

b k

d

j

f h

Рис. 3. Гамильтоновы циклы в задаче Киркмана

В применениях графов к играм вершины соответствуют различным позициям. Таким образом, существование гамильтонова цикла равносильно существованию циклической последовательности ходов, содержащей каждую позицию по одному разу. Примером является известная задача о шахматном коне: можно ли, начиная из произвольного поля на доске, ходить конем в такой последовательности, чтобы пройти через каждое из 64 полей и вернуться в исходное? Эта задача имеет несколько вариантов решений.

Гамильтоновой цепью в графе называется простая цепь, проходящая через все вершины по одному разу.

Если в графе не существует гамильтоновых циклов, то можно искать сумму непересекающихся простых циклов, проходящих через все вершины.

В орграфах можно искать орциклы, проходящие через каждую вершину по одному разу.

К гамильтоновым циклам относится так называемая задача о коммивояжере. Район, который должен посетить коммивояжер, содержит какое-то количество городов. Расстояния между ними известны, и нужно найти кратчайшую дорогу, проходящую через все пункты и возвращающуюся в исходный. Эта задача имеет ряд приложений в исследовании операций, например в вопросах о наиболее эффективном использовании подвижного состава или оборудования.

В задаче о коммивояжере города можно представить как вершины графа , в котором каждой паре вершин приписывается расстояние . Если вершины не инцидентны, то полагают . Тогда задача состоит в том, чтобы найти такой гамильтонов цикл , для которого сумма

минимальна. Так как обычно речь идет только о конечном числе вершин, задача может быть решена перебором. Однако, никакого эффективного алгоритма решения этой задачи до сих пор не известно. Имеются некоторые частные схемы для отдельных случаев. Например, частную задачу определения кратчайшей воздушной линии, соединяющей все столицы штатов в США, просчитали до конца Данциг, Фалкерсон и Джонсон.

В отличие от эйлеровых циклов критерий существования гамильтоновых циклов не известен. Более того, иногда даже для конкретных графов бывает очень трудно решить, можно ли найти такой цикл.