На этом шаге мы рассмотрим гамильтоновы циклы.

Отметим, что начало исследований так называемых гамильтоновых графов относится к графам многогранников [1, с.70].

В 1857 г. ирландский математик Гамильтон предложил игру, названную "путешествие по додекаэдру". Игра сводилась к обходу по ребрам всех вершин правильного додекаэдра при условии, что ни в одну из вершин нельзя заходить более одного раза. Додекаэдр - это многогранник, гранями которого служат 12 правильных пятиугольников. У него 20 вершин и 30 ребер. Вершины и ребра додекаэдра составляют некоторый плоский граф.

Определение.

Простой цикл в графе - это замкнутый путь, все вершины которого, кроме v₀ и v_n, попарно различны.

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

Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым [2, с.48-49]. Ясно, что всякий гамильтонов граф является полугамильтоновым.

Применим теперь алгоритм с возвратом для нахождения гамильтонова цикла в графе.

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

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

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

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

После этих замечаний приведем реализацию алгоритма поиска гамильтонова пути в связном неориентированном графе:

Программа 1.

//Нахождение всех гамильтоновых циклов в графе,
//заданном структурой Вирта.
#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define Node 20 //Максимальное количество вершин в графе.
typedef int Boolean;
typedef struct L *Lref; // Тип: указатель на заголовочный узел.
typedef struct T *Tref; // Тип: указатель на дуговой узел.

//Описание типа заголовочного узла.
typedef struct L 
{ 
  int Key; //Имя заголовочного узла.
  int Count; //Количество предшественников.
  Boolean Flag; //Флаг посещения узла при обходе.
  Tref Trail; //Указатель на список смежности.
  Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
};

//Описание типа дугового узла.
typedef struct T 
{ 
  Lref Id; 
  Tref Next; 
};

//Описание типа узла стека.
typedef Lref TipElement; 
typedef struct Zveno *svqz;
typedef struct Zveno
{
  TipElement Element; //Указатель на список смежности.
  svqz Sled;
};

class Spisok
{
  private:
    Lref Head; //Указатель на голову списка заголовочных узлов.
    Lref Tail; //Указатель на фиктивный элемент 
               // в конце списка заголовочных узлов.
    int  X[Node+1]; //Результат работы программы.
    void SearchGraph (int, Lref *);
  public:
    Spisok() {//Инициализация списка заголовочных узлов.
              Head = Tail =  new (L); }
    Lref GetHead() { return Head; }
    Lref GetTail() { return Tail; }
    void MakeGraph ();
    void PrintGraph ();
    void Hamilton (int, int);
    void X1 (Lref t) {X[1] = t->Key;};
};

void main ()
{
  Spisok A;
  Lref t; //Рабочий указатель для перемещения 
          // по списку заголовочных звеньев.
  int n=0;

  //Построение графа и вывод его структуры Вирта.
  A.MakeGraph ();
  A.PrintGraph (); cout<<endl;
  //Инициализация и подсчет количества вершин графа.
  t = A.GetHead();
  while (t!=A.GetTail())
    { t->Flag = TRUE; n++; t = (*t).Next; }
  // ------------------------------------ 
  //Нахождение всех гамильтоновых циклов.
  t = A.GetHead();
  A.X1(t);
  t->Flag = FALSE;
  A.Hamilton (2,n);
} 

void Spisok::SearchGraph (int w, Lref *h)
//Функция возвращает указатель на заголовочный узел 
//с ключом w в графе, заданном структурой Вирта с указателем Head. 
{
  *h = Head; (*Tail).Key = w;
  while ((**h).Key!=w) *h = (**h).Next;
  if (*h==Tail)
  //В списке заголовочных узлов нет узла с ключом w.
  //Поместим его в конец списка Head.
  { Tail = new (L); (**h).Count = 0; 
    (**h).Trail = NULL; (**h).Next = Tail; }
}

void Spisok::MakeGraph ()
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу.
{
  int x,y;
  Lref p,q; //Рабочие указатели.
  Tref t,r; //Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.
  cout<<"Вводите начальную вершину дуги: ";
  cin>>x;
  while (x!=0)
  {
     cout<<"Вводите конечную вершину дуги: "; cin>>y;
     //Определим, существует ли в графе дуга (x,y)?
     SearchGraph (x, &p); SearchGraph (y,&q);
     r = (*p).Trail; Res = FALSE; 
     while ((r!=NULL)&&(!Res)) 
       if ((*r).Id==q) Res = TRUE; 
       else r = (*r).Next; 
     if (!Res) //Если дуга отсутствует, то поместим её в граф.
      { t = new (T); (*t).Id = q; 
        (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; } 
     cout<<"Вводите начальную вершину дуги: "; cin>>x;
  }
}

void Spisok::PrintGraph ()
//Вывод структуры Вирта, заданной указателем 
//Head и соответствующей ориентированному графу.
{
  Lref p; //Рабочий указатель.
  Tref q; //Рабочий указатель.

  p = Head;
  while (p!=Tail)
  {
     cout<< (*p).Key << "("; q = (*p).Trail; 
     while (q!=NULL) 
      { cout<<(*(*q).Id).Key; q = (*q).Next; } 
     cout<<")"; p = (*p).Next; cout<<" ";
  }
}

void Spisok::Hamilton (int k, int n)
//Нахождение всех гамильтоновых циклов в графе, структура
//смежности которого заданна указателем t.
{
  int i;  //Параметр цикла.
  Lref t; //Указатель на k-ю вершину частичного решения.
  Tref r;

  SearchGraph (X[k-1], &t);
  r = t->Trail;
  while ( r != NULL )
  {
    X[k] = r->Id->Key;
    if  (k==n+1 && X[k]==X[1])
    {
      for (i=1;i<=n;i++) cout << X[i] << " ";
      cout << X[1] << endl;
    }
    else  
      if (r->Id->Flag)
      {
        r->Id->Flag = FALSE;
        Hamilton (k+1,n);
        r->Id->Flag = TRUE;
      }
    r = r->Next;
  }
}

Текст этой программы можно взять здесь.

Результат работы приложения изображен на рисунке 1:

Рис.1. Результат работы приложения

Программа [3, с.134-135].

   (DEFUN HAMILTCYCLE (LAMBDA (GRAPH)
   ; Построение гамильтонова цикла:
   ; GRAPH   - граф, представленный структурой смежности в
   ;           виде ассоциативного списка,
   ; Результат: гамильтонов цикл в виде списка вершин,
   ;            NIL, если гамильтонова цикла не существует
      (COND ( (NULL GRAPH) NIL )
            (  T  (COND ( (NULL (CDR GRAPH))
                              (LIST (CAAR GRAPH)))
                        (  T  (HC GRAPH (CAAR GRAPH)
                                  (LIST (CAAR GRAPH))
                                  (CDAR GRAPH)) )) ))
   ))
   ; ------------------------------------------
   (DEFUN HC (LAMBDA (GRAPH START VISITED SONS)
   ; GRAPH   - граф, представленный структурой смежности в
   ;           виде ассоциативного списка,
   ; START   - вершина графа - начало гамильтонова цикла,
   ; VISITED - список посещенных вершин графа,
   ; SONS    - список вершин, смежных первой вершине в списке VISITED
      (COND ( (NULL SONS) NIL )
            (  T  (COND ( (AND (MEMBER START SONS)
                               (EQ (LENGTH GRAPH)
                                   (LENGTH VISITED)))
                             (REVERSE VISITED) )
                        ( T (COND
                              ( (MEMBER (CAR SONS) VISITED)
                                  (HC GRAPH START VISITED
                                             (CDR SONS)) )
                              (  T  (OR (HC GRAPH START
                                            (CONS
                                              (CAR SONS) VISITED)
                                            (NEIGHBOUR3 (CAR SONS) GRAPH)
                                        )
                                        (HC
                                           GRAPH START VISITED
                                           (CDR SONS))) )) )) ))
   ))
   ; ---------------------------------
   (DEFUN NEIGHBOUR3 (LAMBDA (X GRAPH)
   ; Функция возвращает список вершин графа GRAPH,
   ;            смежных с вершиной X
      (COND ( (NULL (ASSOC X GRAPH)) NIL )
            (  T  (CDR (ASSOC X GRAPH)) ))
   ))

Текст этой библиотеки можно взять здесь.

Тестовые примеры:

   $ (HAMILTCYCLE '((1 . (2 6)) (2 . (1 3 4)) (3 . (2 4))
   (4 . (2 3 5)) (5 . (4 6)) (6 . (1 5))))
   (1 2 3 4 5 6)
   $ (HAMILTCYCLE '((A . (F D C)) (F . (E D A B))
   (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C))))
   (A F D E B C)

Разберем работу функции HAMILTCYCLE.

Для пустого графа она возвращает пустой список, а для графа, состоящего из единственной вершины - список, содержащий эту вершину.

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

Частичное решение представлено в виде списка VISITED - это список просмотренных вершин в порядке, обратном порядку их просмотра.

Список SONS - это список соседей первой вершины в списке VISITED. С точки зрения частичного решения эта вершина является как раз последней. Поэтому вершины из списка SONS могут входить в продолжения частичного решения.

Если этот список пуст, то продолжение частичного решения невозможно и функция HC возвращает значение NIL.

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

во-первых, начальная вершина содержится в списке SONS и,
во-вторых, если пройдены все вершины графа. Поскольку каждая вершина по условию посещается не более одного раза (это следует из определения частичного решения), то достаточно проверить, что длины списков GRAPH и VISITED равны.

Если оба вышеупомянутых условия выполнены, то список VISITED представляет собой искомый цикл.

Перейдем теперь к случаю, когда продолжение возможно, но не приводит немедленно к построению полного решения. Наша цель продолжить частичное решение. Для этого мы просматриваем список SONS до тех пор, пока не встретим вершину, которой нет в списке VISITED. Если такая вершина не найдена, то продолжение невозможно.

В противном случае вычисляется выражение

   (OR  (HC GRAPH START (CONS (CAR SONS) VISITED)
            (NEIGHBOUR3 (CAR SONS) GRAPH))
        (HC GRAPH START VISITED (CDR SONS)))

Это ключевой момент поиска с возвращением. Если при первом вызове функции HC вычисляется значение, отличное от NIL, то это означает, что продолжение (CONS (CAR SONS) VISITED) достроено до полного решения. Это решение и возвращается на верхний уровень. В противном случае с помощью второго вызова функции HC делается попытка найти продолжение, отличное от (CONS (CAR SONS) VISITED).

Обратите внимание на то, что весь механизм возврата оказался "спрятанным" в рекурсию. Это позволило сделать программу ясной и компактной.

Функция HAMILTCYCLE прекратит работу, как только найдет первый гамильтонов цикл или просмотрит все возможности.

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

Замечания.

Следующие четыре неориентированных графа демонстрируют отсутствие тесной взаимосвязи между существованием эйлеровых и гамильтоновых циклов:
```
   1) эйлеров и гамильтонов:
      {1,2},{2,3},{3,4},{4,1};
   2) неэйлеровы и гамильтоновы:
      a) {1,2},{2,3},{3,4},{2,4},{4,5},{5,1};
      b) {1,2},{2,3},{3,4},{2,4},{4,6},{1,6},{4,5},{5,6};
   3) эйлеровы и негамильтоновы:
      a) {1,2},{2,3},{3,4},{4,1},{4,5},{5,2},{2,6},{6,4};
      b) {1,2},{2,3},{3,5},{5,6},{6,4},{1,4},{2,7},{7,4},{2,8},
         {8,5},{4,5};
   4) неэйлеров и негамильтонов:
      {1,2},{2,3},{3,4},{4,1},{4,5},{5,2}.
```
    Однако, двойственность между эйлеровыми и гамильтоновыми циклами (замена вершины на ребро и наоборот) приводит к тесной связи между этими двумя понятиями в применении к неориентированному графу G и соответствующему ему реберному графу, определяемому ниже.

Определение [4, с.237].
Реберный граф G_l графа G имеет столько же вершин, сколько ребер у графа G. Ребро между двумя вершинами графа G_l существует тогда и только тогда, когда ребра графа G, соответствующие этим двум вершинам, смежны (т.е. инцидентны одной и той же вершине графа G).

    Верны два следующих утверждения о взаимоотношении между эйлеровыми и гамильтоновыми циклами, принадлежащие Ф.Харари [4, с.237].
    1. Если граф G имеет эйлеров цикл, то граф G_l имеет как эйлеров, так и гамильтонов циклы.
    2. Если граф G имеет гамильтонов цикл, то граф G_l также имеет гамильтонов цикл.
    Обращение этих утверждений неверно!
Пусть G - граф с n вершинами v₁, v₂, ...,v_n, степени d_i которых удовлетворяют неравенствам d₁<=d₂<= ... <=d_n-1<=d_n.
    Граф G имеет гамильтонов цикл, если выполняется одно из следующих условий:

условие Дирака: d₁>=n/2;
условие Поша: d_k >= k+1 для k<n/2;
условие Бонди: из d_l<=l и d_k<=k следует, что d_l+d_k>=n (k<>l);
условие Хватала: из d_k<=k<=n/2 следует, что d_n-k>=n-k.

    Обратим также Ваше внимание на условие Дирака в другой формулировке.

Теорема Дирака.
Обозначим R(v) - степень вершины v в графе. Если в простом графе с n>=3 вершинами R(v)>=n/2 для любой вершины v, то граф является гамильтоновым.
Каждый гамильтонов цикл можно характеризовать с помощью матрицы смежностей (x_ij) размера n*n, имея в виду, что x_ij=1, если ребро (i,j) принадлежит C, и x_ij=0 в противном случае.
Толщиной графа G (обозначается l(G)) называется число вершин в самой длинной простой цепи графа. Если граф G гамильтонов, то толщина l(G) равна числу вершин графа.

[5, с.48]. Простейший пример негамильтонова графа - это тэта-граф, графическое изображение которого похоже на греческую букву "тэта":

                            o --------- o
                            ¦           ¦
                            o --- o --- o
                            ¦           ¦
                            o --------- o

⁽¹⁾ Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, опитимизация. - М.: Наука, 1981. - 341 с.
⁽²⁾ Уилсон И.Р., Эддиман А.М. Практическое введение в ПАСКАЛЬ. - М.: Радио и связь, 1983. - 143 с.
⁽³⁾ Крюков А.П., Радионов А.Я., Таранов А.Ю., Шаблыгин Е.М. Программирование на языке R-Лисп. - М.: Радио и связь, 1991. - 192 с.
⁽⁴⁾ Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.
⁽⁵⁾ Березина Л.Ю. Графы и их применение. - М.: Просвещение, 1979. - 143 с.

На следующем шаге мы познакомимся с кликами.

Предыдущий шаг Содержание Следующий шаг