Описание алгоритма решения задачи

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«Тюменский Государственный Нефтегазовый университет»

ИНСТИТУТ ГЕОЛОГИИ И НЕФТЕГАЗОДОБЫЧИ

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КУРСОВАЯ РАБОТА

по дисциплине «Дискретная Математика»

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов

Выполнил:

студент группы АСОиУз - 09 -1

Юга М.Н.

Проверила:

старший преподаватель каф. ИВТ, Гапанович И.В.

Тюмень 2012

Оглавление

1) Постановка задачи

2) Описание алгоритма решения задачи

3) Ручной просчет

4) Листинг программы

5) Литература

Постановка задачи

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

Описание алгоритма решения задачи

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

Приведем некоторые наиболее простые методы выделения гамильтоновых цепей и циклов в графе G =(V,X), где V = { v₁,v₂,…,v_n }. Самым простым является метод перебора всевозможных перестановок v_i1,v_i2,…,v_in множества V. Для каждой из них проверяем, является ли v_i1v_i2…v_in маршрутом в G. Если является, то v_i1v_i2 …v_in - гамильтонова цепь в G, в противном случае переходим к другой перестановке. Тогда по окончании перебора будут выделены все гамильтоновы цепи в графе G. Аналогично для выделения гамильтоновых циклов перебираем всевозможные перестановки v₁v_i1v_i2 …v_in-1 множества V, для каждой из которых проверяем, является ли v₁v_i1v_i2…v_in-1v₁ маршрутом в G. Если является, то v₁v_i1v_i2…v_in-1v₁ – гамильтонов цикл в G, в противном случае переходим к следующей перестановке. Тогда по окончании перебора будут выделены все гамильтоновы циклы в графе G. Очевидно, что при выделении гамильтоновых цепей придется перебрать n! перестановок, а при выделении всех гамильтоновых циклов - (n -1)! перестановок. При этом в случае полного графа ни одна из перестановок не окажется отброшенной, т.е. данный метод является эффективным для графов, близких к полным.

Антилексикографический порядок (обозначим <¢) определяется следующим образом: <x1,x2,…xn> <¢ <y1,y2,…,y n> Û существует такое k £ n, что x_k > y_k и x_p = y_p для каждого p > k.

Для примера приведем перестановки множества X = {1,2,3} в антилексикографическом порядке: 123, 213, 132, 312, 231, 321.

Алгоритм генерирования перестановок в антилексикографическом порядке можно сформулировать при помощи рекурсивной процедуры, на вход которой подается m – количество первых элементов массива P = { 1, 2, 3…m }, для которого генерируются перестановки.

Процедура swap() меняет местами элементы в массиве P, а процедура reve () представляет элементы отрезка массива [0..m] в обратном порядке.

Ручной просчет

Пусть имеем граф G = (V, X) заданный матрицей смежности:

	v1	v2	v3
v1
v2
v3

Построим все перестановки множества вершин V = { v₁, v₂, v₃}.

Просматриваем перестановки множества V на предмет наличия гамильтоновой цепи:

{ v₁, v₂, v₃} – нет ребра { v₂, v₃}

{ v₂, v₁, v₃} – гамильтонова цепь.

{ v₁, v₃, v₂} – нет ребра { v₃, v₂}

{ v₃, v₁, v₂} – гамильтонова цепь.

{ v₂, v₃, v₁} – нет ребра { v₂, v₃}

{ v₃, v₂, v₁} – нет ребра { v₃, v₂}

Значит гамильтоновых цепей две:

2 1 3 и 3 1 2
Листинг программы

#include <stdio.h>

#define MAX 1010

int n;

int g[MAX][MAX];

bool used[MAX];

int p[MAX];

bool One;

inline void swap(int &a,int &b) {int t = a;a = b;b = t;}

inline void reve(int x) {int j = 0; while(j < x) {swap(p[j],p[x]);x--;j++;}}

inline bool check(){for(int i = 0;i < n-1;i++) if(!g[p[i]][p[i+1]]) return false; return true;}

void next_perm(int m)

{

if(m == 0)

{

if(check())

{

for(int i = 0;i < n;i++) printf("%d ",p[i]);

printf("\n");

One = true;

}

}else{

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

{

next_perm(m-1);

if(i < m)

{

swap(p[i],p[m]);

reve(m-1);

}

}

}

}

int main()

{

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

scanf("%d",&n);

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

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

scanf("%d",&g[i][j]);

for(int i = 0;i < n;i++) p[i] = i+1;

next_perm(n-1);

if(!One)

printf("No paths");

return 0;

}

Литература

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн Алгоритмы: построение и анализ (второе издание), Вильямс, 2007 г.

2. Д. Кнут Искусство программирования, Вильямс, 2006 г.

3. Ф.А. Новиков Дискретная математика для программистов, Питер, 2000 г.

4. Б.Н. Иванов Дискретная математика. Алгоритмы и программы, Лаборатория базовых знаний, 2003 г.