Мрежа на дейностите. Метод на критичния път

5.11.1.Хамилтонов цикъл. Задача за търговския пътник

Съществуват две класически задачи, свързани с хамилтонови графи:

• 
  проверката дали даден граф е хамилтонов;
  
• 
  намиране хамилтоновия цикъл с най-малка дължина в тегловен хамилтонов граф (задача за търговския пътник).
  

Тази задача има много общо със задачата за намиране на всички пътища между два зададени върха в безтегловен граф. Всъщност разликите са следните три:

• 
  графът е тегловен;
  
• 
  началният и крайният връх на търсените пътища в графа е един и същ;
  
• 
  трябва да се запомня не само текущия (търсения в момента) път, но и най-краткия от всички намерени до момента пътища;
  
• 
  т
  рябва да се изчислява дължината на всеки намерен път - хамилтонов цикъл и да се помни дължината на най-краткия от тях;
  
• 
  за решение на задачата се приема най-краткият път от всички намерени пътища-хамилтонови цикли;
  
• 
  тъй като търсеният път трябва да бъде хамилтонов цикъл, т.е. трябва да преминава през всички върхове, за начален връх може да се избере всеки връх от графа. За такъв ще изберем 0-ия връх.
  

Ето защо, лесно можем да създадем алгоритъм и да напишем програма за намиране на хамилтонов цикъл с най-малка дължина, като модифицираме съответно алгоритъма и програмата за намиране на всички пътища между два зададени върха в безтегловен граф. Полезно е да си припомним, че алгоритъма и програмата за намиране на всички пътища между два зададени върха в безтегловен граф получихме като модифицирахме алгоритъма за обхождане на граф в дълбочина.

За да изясним алгоритъма ще използваме графа от фиг. 38.

1. По алгоритъма за обхождане на граф в дълбочина, ще получим първия хамилтонов цикъл 0-1-2-3-4-5-0 с дължина 31 и ще го приемем за минимален (най-кратък);

2. За да намерим друг път, ще отстъпим от 0-ия връх в 5-ия и ще обявим 0-ия за непосещаван. Ще отстъпим и от 5-ия връх в 4-ия и ще обявим 5-ия за непосещаван. Ще отстъпим и от 4-ия връх в 3-ия и ще обявим 4-ия за непосещаван. От 3-ия връх можем да продължим напред и да получим втория хамилтонов цикъл 0-1-2-3-5-4-0 със същата дължина.

3. За да намерим друг път, ще отстъпим последователно от 0-ия връх в 4-ия и ще обявим 0-ия за непосещаван. Ще отстъпим и от 4-ия връх в 5-ия и ще обявим 4-ия за непосещаван. Ще отстъпим и от 5-ия връх в 3-ия и ще обявим 5-ия за непосещаван. Ще отстъпим и от 3-ия връх в 2-ия и ще обявим 3-ия за непосещаван. От 3-ия връх можем да продължим напред и да получим третия хамилтонов цикъл 0-1-2-4-3-5-0 със същата дължина 28. Този път (хамилтонов цикъл) е по кратък, затова го приемаме за минимален.

4. По описания начин ще намерим четвъртия хамилтонов цикъл 0-1-4-2-3-5-0 с дължина 31, т.е. той не е по кратък от третия.

5. Пак по описания начин ще намерим петия хамилтонов цикъл 0-4-1-2-3-5-0 с дължина 33, т.е. и той не е по кратък от третия.

Минимален се оказа третият хамилтонов цикъл.

Програма 5.20. Намиране на хамилтънов цикъл с минимална дължина в тегловен граф, предстаен чрез матрица на съседство. Задача за търговския пътник

#include

# include

#include "graf_mat.h"

int tekSum, //Дължина на текущия цикъл

minSum; //Дължина на минималния цикъл

unsigned

*tekCycle, //За масива, съдържащ върховете на текущия цикъл

*minCycle, //За масива, съдържащ върховете на минималния цикъл

*visit; //За масива, регистриращ посетените върхове

//Рекурсивна член-функция за намиране минималния хамилтонов цикъл

void clasGraph::hamDFS(unsigned i, unsigned nivo)

{

unsigned k;

if (nivo==BrV) { //Намерен е по-кратък цикъл и ...

minSum=tekSum; // ...регистрираме него, като минимален

for (k=0;k

}

return;

if (visit[i]) return;

visit[i]=1;//Регистрираме i-ия връх като посетен и ...

for (k=0;k

if (A[i][k] && k!=i) {

tekCycle[nivo]=k;

tekSum+=A[i][k];

if (tekSum

tekSum-=A[i][k];

}

visit[i]=0;

{

char ime_vh_fl[21]; unsigned k;

fin.open(ime_vh_fl,ios::in);

if (fin.bad()) {cout<<"Няма такъв файл.\n";getch();return;}

fin>>BrV; //Въвеждаме от текстовия файл броя на върховете на графа

clasGraph Graph; //Създава обекта Graph

Graph.make_graf(); //Запълва матрицата на съседство

Graph.display_graf(); //Извежда на екрана матрицата на съседство

if (!(tekCycle=new unsigned [BrV])) exit(0);

if (!(minCycle=new unsigned [BrV])) exit(0);

if (!(visit=new unsigned [BrV])) exit(0);

for (k=0;k

minSum=9999; tekSum=0; tekCycle[0]=1;

Graph.hamDFS(0,0);

cout<<"Mинималният хамилтонов цикъл е 0 ";

for (int i=0; i

cout<<"0 с дължина на пътя " <

}
Програма 5.21. Намиране на хамилтонов цикъл с минимална дължина в тегловен граф, представен чрез масив от списъци на съседство. Задача за търговския пътник

//Хамилтънов цикъл. Задача за търговския пътник.

# include

# include

#include "graf_sp.h"

int tekSum,//Дължина на текущия цикъл

minSum;//Дължина на минималния цикъл

unsigned

*minCycle, //За масива, съдържащ върховете на минималния цикъл

*visit; //За масива, регистриращ посетените върхове

//Рекурсивна член-функция за намиране минималния хамилтонов цикъл

void clasGraph::hamDFS(unsigned i, unsigned nivo)

{

unsigned k;

if (nivo==BrV) { //Намерен е по-кратък цикъл

minSum=tekSum;

for (k=0;k

}

return;

if (visit[i]) return;

visit[i]=1;

rebro *p=a[i].first;

while (p){

k=p->nom;

if (k!=i) {

tekCycle[nivo]=k;

tekSum+=p->teg;

if (tekSum

tekSum-=p->teg;

}p=p->next;

}visit[i]=0;

}
void main()

{

char ime_vh_fl[21]; unsigned k;

fin.open(ime_vh_fl,ios::in);

if (fin.bad()) {cout<<"Няма такъв файл.\n";getch();return;}

fin>>BrV; //Въвеждаме от текстовия файл броя на върховете на графа

clasGraph Graph; //Създава обекта Graph

Graph.make_graf(); //Запълва матрицата на съседство

Graph.display_graf(); //Извежда на екрана матрицата на съседство

if (!(tekCycle=new unsigned [BrV])) exit(0);

if (!(minCycle=new unsigned [BrV])) exit(0);

if (!(visit=new unsigned [BrV])) exit(0);

for (k=0;k

minSum=9999; tekSum=0; tekCycle[0]=1;

Graph.hamDFS(0,0);

cout<<"\nMинималният хамилтънов цикъл е 0 ";

for (int i=0; i

cout<<"0 с дължина на пътя " <

}

5.11.2.Ойлеров цикъл

Ойлер преподавал в университета в Калининград, наричан тогава Кьонигсберг. Градът е разположен на двата бряга и на два острова на р. Прегел. Четирите части на града се свързвали помежду си чрез седем моста, както е показано на фиг. 39.

Фиг. 39. Скица на град Калининград

Гражданите на този град много обичали разходките из града и докато се разхождали се запитали, дали е възможно гражданин на този град да излезе от дома си, да мине по един път през всеки мост и да се прибере отново у дома си. Тази, на пръв поглед проста задача, се оказала такава главоблъсканица, че привлякла вниманието дори на именития Ойлер.

Ойлер представил четирите части от града с кръгчета, а мостовете - чрез линии (фиг.40) и веднага заключил, че описаната разходка не е възможна. За да е възможна, всека част на града (A, B, C и D) трябва да е свързана с останалите с четен брой мостове. Това е така, защото, когато разхождащият се навлезе в терирорията на някоя ч
аст по един мост, трябва да има още един мост, по който да излезе от нея. Има само две изключения от това правило: когато започва и когато завършва разходката.
Фиг. 40. Скица на Ойлер на град Калининград

Представяйки града и неговите мостове по този начин, Ойлер създал първия граф и дефинирал самото понятие граф. Наред с това, той веднага осъзнал, че с това поставя началото на нов дял от математиката – теорията на графите.