Практическая работа 16. Нахождение гамильтоновых циклов

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

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

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

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

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

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

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

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

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

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

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

Задание:

1.Запустите IDE Borland C++ 5.02.

2. Откомпилируйте предложенную программу реализации алгоритма поиска гамильтонова пути в связном неориентированном графе:

//Нахождение всех гамильтоновых циклов в графе,//заданном структурой Вирта.#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; }}

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

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

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

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

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) равна числу вершин графа.

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

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

Клика графа

Понятие клики используется в различных социологических теориях (вопросы, связанные с голосованием, альянсами и т.п.), а также в теории игр.

Вспомним определения::

• часть графа G=(V,E) - это такой граф G'=(V',E'), что V' принадлежит V и E' принадлежит E;
• подграфом графа G называется такая его часть G', которая вместе со всякой парой вершин u,v содержит и ребро {u,v}, если только оно есть в G;
• граф называется полным, если любые две его различные вершины соединены ребром.

Определение

Клика графа - это любой максимальный полный подграф.

Не требует никакой изобретательности следующий процесс нахождения клики.

Пусть вершины графа L=(X,U) пронумерованы: X={x₁, x₂,..., x_n}. Выберем вершину x₁, затем первую смежную с ней x_i, потом вторую x_j, смежную с обеими (1<i<j) и т.д. пока возможно, и пусть p - число вершин выявленной таким образом максимальной (по включению) клики. Попытаемся увеличить это число, рассматривая другой вариант процесса: вместо вершины x_k, добавленной к некоторой клике на последнем шаге, добавляем другую вершину x_l, l>k, тоже смежную со всеми вершинами этой клики (если такая x_l есть), в надежде, что продолжение процесса по новой ветви окажется более успешным и даст хотя бы (p+1) -клику; если ни одна замена вершины x_k не приводит к цели, возвращаемся еще на один шаг и т.д.

Задание:

1.Запустите IDE Borland C++ 5.02. Подготовьте запуск исполнимых файлов в консольном режиме.

2. Откомпилируйте предложенную программу нахождения всех клик в графе, заданном структурой Вирта. //Нахождение всех клик в графе, заданном структурой Вирта.#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; }; class Spisok{ private: Lref Head; //Указатель на голову списка заголовочных узлов. Lref Tail; //Указатель на фиктивный элемент                // в конце списка заголовочных узлов. int X[20]; //Результат работы программы. void SearchGraph (int, Lref *); public: Spisok() {//Инициализация списка заголовочных узлов.         Head = Tail = new (L); } Lref GetHead() { return Head; }  Lref GetTail() { return Tail; } void MakeGraph (); void PrintGraph (); void Clique (int, int); void X1 (Lref t) {X[1] = t->Key;};}; void main (){ Spisok A; Lref t; //Рабочий указатель для перемещения           // по списку заголовочных звеньев. Lref t1; int n=0; //Построение графа и вывод его структуры Вирта. A.MakeGraph (); A.PrintGraph (); cout<<endl; //Инициализация и подсчет количества вершин графа. t = A.GetHead(); while (t!=A.GetTail()) { n++; t = (*t).Next; } // ------------------------------------   //Нахождение всех клик в графе Head. for (int i=3;i<=n;i++) { //i - количество вершин в клике (i<=3). cout << "Перечислим все клики длины " << i << endl; t = A.GetHead(); while (t!=A.GetTail()) {  //Инициализация.  t1 = A.GetHead();  while (t1!=A.GetTail())  { t1->Flag = TRUE; t1 = t1->Next; }  A.X1(t); t->Flag = FALSE;  //Отыскание клики с i вершинами, "начинающейся" в вершине t.  A.Clique (2,i); t = t->Next; } }} 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::Clique (int k, int m)//Нахождение всех клик, содержащих m вершин, в графе,//заданном структурой Вирта с указателем Head,//k - количество вершин в частичном решении.{ Tref r,r1; //Рабочие указатели. Lref p,q; //Рабочие указатели. Lref t; //Указатель на k-ю вершину частичного решения. int v;  //Вершина - кандидат на дополнение к частичному решению. Boolean Res; //Флаг клики. Boolean Res1;//Флаг существования ребра. int i;  //Параметр цикла. SearchGraph (X[k-1], &t); r = t->Trail; while (r!= NULL) { v = r->Id->Key; //Проверим, смежна ли вершина v с вершинами X[1],X[2],...,X[k-1]. Res = TRUE; for (i=1;i<=k-1;i++) { //Cуществует ли в графе ребро (X[i],v)? SearchGraph (v, &p); SearchGraph (X[i], &q); r1 = p->Trail; Res1 = FALSE; while (r1!= NULL &&!Res1)  if (r1->Id==q) Res1 = TRUE;  else r1 = r1->Next; Res = (Res && Res1); } if (!Res) r->Id->Flag = FALSE; // --------------------------     if (k==m && Res) //Количество вершин в графе равно m, и //вершины X[1],X[2],...,X[k] образуют клику. {   //Вывод клики на экран дисплея.   for (i=1;i<=k-1;i++) cout << X[i] << " ";   cout << v << endl; } else       if (r->Id->Flag) {   X[k] = r->Id->Key;   r->Id->Flag = FALSE;   Clique (k+1,m);   r->Id->Flag = TRUE; } r = r->Next; }}

Каждый узел в дереве поиска соответствует полному подграфу графа, и каждое ребро соответствует вершине графа. Заметим, что каждая клика порождается много раз: в общем случае клика размера k порождается k! раз.

От общего числа шагов порядка n! могут спасти (не всегда, но часто) следующие два обстоятельства.

1. Если когда-то уже была найдена p -клика, а затем на некоторой ветви процесса образовалась q -клика от присоединения (к какой-то другой, вообще говоря, клике) вершины x_j с номером j>=0n-p+q, то развивать эту ветвь не имеет смысла, ибо ни одной клики с числом вершин более p она все равно дать не может.

 

1. Пусть из некоторой сформированной клики F мы удаляем последнюю присоединенную вершину x_k и вместо нее собираемся добавить x_l с l>k; это заведомо не имеет смысла делать, если все вершины клики F\x_k, смежные с x_l, смежны также с x_k.

Весь процесс с учетом этих двух обстоятельств представляет собой частный случай хорошо известного метода ветвей и границ, предлагался в разное время (устно и письменно) многими авторами, и установить приоритет здесь затруднительно.