Гамильтоновы циклы

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

Решение задачи на языке Pascal

Дан связный неориентированный граф G. Требуется найти все гамильтоновы циклы графа, если они есть.

Метод решения - перебор с возвратом (backtracking). Начинаем поиск решения, например, с первой вершины графа. Предположим, что уже найдены первые k компонент решения. Рассматриваем ребра, выходящие из последней вершины. Если есть такие, что идут в ранее не просмотренные вершины, то включаем эту вершину в решение и помечаем ее как просмотренную. Получена (k+1) компонента решения. Если такой вершины нет, то возвращаемся к предыдущей вершине и пытаемся найти ребро из нее, выходящее в другую вершину. Решение получено при просмотре всех вершин графа и возможности достичь из последней первой вершины. Решение (цикл) выводится, и продолжается процесс нахождения следующих циклов. Пример графа и часть дерева, показывающего механизм работы данного метода.

Логика решения.

procedure Gm(k:integer); {* k - номер итерации*}

{*глобальные переменные*}

{* А - матрица смежности, St - массив для хранения порядка просмотра вершин графа, Nnew - массив признаков: вершина просмотрена или нет*}

var j,v: integer;

begin

v:=St[k-l]; {*номер последней вершины*}

for j:=l to N do if (A[v,j]<>0) then {*есть ребро между вершинами с номерами v и j*}

if (k=N+l) and (j=l) then <вывод цикла> else if Nnew [j] then {* вершина не просмотрена*}

begin St[k]:=j; Nnew[j]:=false;

Gm(k+1) ; Nnew [j ]: =true; end;

end;

Фрагмент основной логики.

…………..

St[l]:=l; Nnew[l]:=false; Gm(2);

Решение задачи на языке С++

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

#include <iostream.h>

#include <stdio.h>

FILE* fi = fopen("g_graph.txt", "r" ) ; // Файл с матрицей смежности

FILE* fo = fopen("g_cycle.txt", "w") ; // Файл с найденными циклами

bool **graph; //Матрица смежности для хранения графа

int n; //Количество вершин в графе

const int vertex = 1; // первая вершина при поиске

int *St; //Массив для хранения просмотренных вершин

int *Nnew;//Массив признаков: вершина просмотрена или нет

void out_way(int n){ //Процедура вывода Гамильтонова цикла

for (int i=0;i<n;i++)

fprintf (fo,"%d\ ",St[i]);

fprintf (fo,"%d\n", vertex) ; }

void gamilton_path(int k){

int v = St[k-1]; // текущая вершина

for(int j = 0;j < n;j++)

if (graph[v] [j]==l) // есть ребро между v и j

if (k==n && j ==vertex) out_way (n) ; //прошли все вершины

else

if(Nnew[j]){// вершина не просмотрена

St[k]=j;// добавляем ее к пройденному пути

Nnew[j]=false; // просмотрена

gamilton_path(k+1); //строим путь

Nnew[j]=true; //возвращаемся назад и строим другие циклы }}

int main(){

fscanf (fi,"%d", &n); //Считываем количество вершин

St = new int[n];

Nnew = new int[n];

for (int i = 0;i < n;i++)Nnew[i]=1; // Нет просмотренных вершин

graph = new bool*[n]; for(int i=0;i<n;i++){

graph[i] = new bool[n]; //выделяем память под строку

for (int j=0;j<n;j++){

fscanf (fi,"%d",&graph[i][j]);}}

Nnew[vertex]=false; //первая вершина уже просмотрена

St [0]=vertex; // вершина с которой начали проход

gamilton_path(1);//параметр означает количество пройденных вершин

fcloseall();

return (0);}