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

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

С понятием гамильтоновых циклов тесно связана так назы­ваемая задача коммивояжера: в нагруженом графе G опреде­лить гамильтонов цикл минимальной длины (иными слова­ми, коммерсант должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один paз, и при этом стоимость такой поездки должна быть мини­мальной.

На первый взгляд, понятие гамильтонова цикла сходно c понятием эйлерова цикла. Приведенные в таблице графы, где первый столбец соответствует случаям существования, второй столбец – не существования гамильтоновых циклов, а строки – случаям существования (первая строка и не существования (вторая строка) эйлеровых циклов, показывают независимость этих понятий.

1 2

1

2

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

Рассмотрим класс графов, в которых заведомо суще­ствуют гамильтоновы цепи и циклы – это полные графы. Очевидно, что в полном графе всегда существуют гамильтонов цикл, а также гамильтоновы цепи, соединяющие две произ­вольные вершины этого графа, т.к. любая вершин полного графа смежна со всеми остальными вершинами Таким образом, простейшим до­статочным условием существования гамильтоновых цепей и цик­лов в графе является его полнота. Приведем также простейшие необходимые условия. Очевидным необходимым условием суще­ствования гамильтоновых цепей и циклов в графе G является связность G. Более тонким необходимым условием существова­ния гамильтонова цикла в графе G является следующее утверждение (примем его без доказательства):

Если граф G обладает гамильтоновым циклом, то в нем отсутствуют точки сочленения.

Приведем наиболее простые методы выделения в графе G(V,X), где V = {v₁, …, v_n}, гамильтоновых циклов и цепей. Наиболее простым из них является метод перебора всевозможных перестановок v_i1, …, v_in множества V. Если перестановка является маршрутом в G, то эта перестановка – гамильтонова цепь. По окончании перебора всех возможных перестановок будут выделены все гамильтоновы цепи.

Для выделения гамильтоновых циклов перебираем всевозможные перестановки v₁, v_i1, …, v_in-1 . Если v₁, v_i1, …, v_in-1, v₁ – маршрут в графе G, то это гамильтонов цикл.

При выделении всех гамильтоновых цепей необходимо перебрать n! Перестановок, при выделении гамильтоновых циклов – (n – 1)! перестановок.

Описанный метод не учитывает информацию о графе. Рассмотрим метод, аналогичный предыдущему, но учитывающий информацию о графе. Составим всевозможные последовательности вершин v_i1, …, v_ir , где v_i1  V, v_i2  G(v_i1)\{v_i1}, …, v_ir  G(v_ir-1)\{v_i1, …, v_ir-1}, G(v_ir) \{v_i1, …, v_ir}= , где G(v_ir) – множество образов вершины v_ir. Тогда в каждом случае, когда r = n, последовательность v_i1, …, v_ir – гамильтонова цепь. Соответственно, когда r = n, v_i1  G(v_in), последовательность v_i1, …, v_ir, v_i1 – гамильтонов цикл.

При этом выделяются все гамильтоновы циклы и цепи.