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

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

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

Гамильтоновым путем в ориентированном графе называется путь S(x₁, …, x_n), проходящий через все вершины графа, притом только по одному разу.

Гамильтоновым контуром называется контур М(х₀, x₁,…, x_n, x₀) в ориентированном графе G(X), если он проходит через все вершины графа, притом только по одному разу.

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

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

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

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

1. Теорема Кёнига. В полном конечном графе всегда существует гамильтонов путь.

2. Если в графе G(X) с n вершинами для любой пары вершин х_i и х_j справедливо неравенство

m(x_i) + m(x_j) ³ n – 1,

где m(x_i), m(x_j) – степени вершин х_i и х_j, то граф G(X) имеет гамильтонову цепь.

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