Первая страница / Визуализаторы / Графы. Циклы и разрезы / Гамильтоновы циклы и цепи. Метод Робертса и Флореса /

Описание алгоритма

Вводное описание

Цикл называется гамильтоновым, если он содержит все вершины графа. Цепь называется гамильтоновой, если она содержит все вершины графа.

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

Метод Робертса и Флореса, подробное описание

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом и Флоресом [2, 3]. Начинают с построения (k×n) матрицы M = ||m[i][j]||, где элемент m[i][j] есть i-ая вершина (скажем xq), для которой в графе G = (X, Г) существует дуга (xj, xq). Вершины xq в множестве Г(xj) можно упорядочить произвольно, образовав элементы j-ого столбца матрицы M. Число строк k матрицы M будет равно наибольшей полу-степени исхода вершины.

Метод состоит в следующем. Некоторая начальная вершина (скажем xj) выбирается в качестве отправной и образует первый элемент множества S, которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например a) в столбце x1. Затем к множеству S добавляется первая возможная вершина (например, вершина b) в столбце a, потом добавляется к S первая возможная вершина (например, вершина c) в столбце b и т. д. Под "возможной" вершиной мы понимаем вершину, ещё не принадлежащую S. Существуют две причины, препятствующие включению некоторой вершины на шаге r в множество S = {x1, a, b, c, …, xr-1, xr}. Или (1) в столбце xr нет возможной вершины, или (2) цепь, определяемая последовательностью вершин в S, имеет длину n-1, т. е. является гамильтоновой цепью.

В случае (2)
(а) в графе G существует дуга (xr, x1) и поэтому найден гамильтонов цикл, или
(б) дуга (xr, x1) не существует и не может быть получен никакой гамильтонов цикл.

В случаях (1) и (2б) следует прибегнуть к возвращению, в то время как в случае (2а) можно прекратить поиск и напечатать результат.

Возвращение состоит в удалении последней включенной вершины xr из S, после чего остается множество S = {x1, a, b, c, …, xr-1}, и добавлении к S первой возможной вершины, следующей за xr, в столбце xr-1 матрицы M. Если не существует никакой возможной вершины, делается следующий шаг возвращения, и т. д.

Литература

  1. Н. Кристофидес (Nicos Christofides) (1978) Теория графов. Алгоритмический подход. 11, стр. 249.
  2. Roberts S. M., Flores B. (1967), An engineering approach to the traveling salesman problem. Man. Sci. ., 13, p. 269.
  3. Roberts S. M., Flores B. (1966), Systematic generation of Hamiltonian circuits, Comm. of ACM, 9, p. 690.