Усвояне на похватите за представяне на графи в по, програмна реализация на графи и решаване на задачи над графи

ЛУ-10

Графи

Алгоритмите за графи представляват голям интерес, защото голям брой задачи могат да се сведат до задачи над графи.[8]. Графът може да се разглежда като абстрактно представяне на реални обекти и системи. Например пътната мрежа в една област може да се представи чрез тегловен граф, в който възлите , например, са населените места, а ребрата са пътните връзки между тях, а теглата са разстоянията в км между отделните населени места. С графи могат да се представят още: железопътна, енергийна, водопроводна, отоплителна, компютърна или друга сехеми. Дори строежа на една молекула може да се представи чрез граф[8].

Представянето на граф може да бъде външно или вътрешно. Външното е чрез файл, а вътрешното – чрез матрица на съседство, два масива или чрез списък на съседство.

Един граф може да бъде ориентиран(насочен) или неориентиран (ненасочен, двупосочен).

Пример за представяне на насочен граф (фиг.10.1) чрез матрица на съседство, е даден в[9] - фиг.10.2. Представянето на дадения граф с два масива е направено на фиг.10.3.

	0	1	0	0	0
2	0	0	1	0	0
3	0	0	0	0	0
4	0	1	1	0	0
5	1	0	0	1	0
	1	2	3	4	5

фиг.10.1 Примерен насочен граф фиг.10.2 Матрица на съседство

На фиг.10.3 е дадено предтсавяне на графа с два масива G и N, при което в G за всеки възел, се записват последователно неговите съседни възли. В масива N , за всеки възел се задава индексът на първия му съседен възел от масива G.

Много алгоритми за графи са посветени на задачата за намиране на пътища от определен вид. Такава, например, е задачата за търговския пътник, при която се търси Хамилтонов цикъл при зададена определена

v	1	2	3	4	5	6
N[v]	1	2	3	4	6	8

k	1	2	3	4	5	6	7	8
G[k]	2	3	0	2	3	1	4	-

Задачата се формулира така: Да се определи дали в даден насочен граф съществува път с дължина К между два възела – А и В.

Алгоритмите за решаване на задачи с графи са предимно рекурсивни[8]. Идеята за рекурсивно решение на тази задача е следната: Път с дължина К, между А и В съществува , ако съществува съсседен на А връх С, такъв, че да съществува път от С до В с дължина (К-L ) , където L е дължина на пътя от А до С.

Една функция за реализиране на тази идея е следната:

void F_road(int k, int a, int b){

if(k==1)

fp=1;

fp=0;

fp=0;

if (By_me(a,c))

if (F_road(k-1,c,b))

fp=1;

}

, а функцията By_me(int a, int b) връща 1 или 0 (истина или лъжа) ако връх b е съседен на a, или не е (съответно), и има следната дефиниция:

return matrix[a][b];

matrix[N][N] е двумерен масив, който представя матрицата на съседство на възлите на насочения граф. Елемeнтът matrix[a][b] =1, ако възли a и b са съседни, matrix[а][b] =0 - в противен случай.

Въпроси по темата и задачи за изпълнение: