Графи математика

for k:=1 to n do

if val[k] = 0 then visit(k);

29 end;


Свързаност на графи


Понякога е доста удобно много големи графи да се разбият на по – малки части, които се обработват поотделно. Често е удобно тези части да са компонентите на свързаност на дадения граф. При много задачи (като намирането на всички прости цикли в даден граф или проверката дали даден граф е планарен, т.е. дали може да се начертае в равнината така, че никои две ребра да не се пресичат). Естествено довеждат до разбиването на графа на неговите компоненти на свързаност. Тогава въпроса е как да намерим тези компоненти. За щастие основните алгоритми за обхождане на граф (в широчина и дълбочина) могат лесно да се приспособят така, че да откриват компонентите на свързаност, тъй като те обхождат всички върхове н ададена компонента преди да преминат на следващата. Например един начин за извеждане на компонентите е да се модифицира рекурсивният алгоритъм за търсене в дълбочина, така че да извежда номера на всеки посетен връх на графа и преди всяко нерекурсивно извикване на visit да отпечатва някаква индикация, че започва нова компонента.

Понякога е полезно да има повече от един път между два върха на графа. Граф, в който между всеки два върха има поне два различни пътя се нарича двусвързан. Един връх се нарича точка на свързване ако, след след като го отстраним, броят на компонентите на свързаност на графа се увеличава. Това ни дава друга (и по – удобна) дефиниция за двусвързан граф: това е граф, в който няма точки на свързване. Граф, който не е двусвързан, се разделя на компоненти на двусвързаност.

Определянето на точките на свързване може да стане с малко разширение на алгоритама за търсене в дълбочина. При обхождането на графа този алгоритъм изгражда дърво. Един връх не е точка на свързване ако има поне един наследник, който е свързан (чрез ребро) с по – горен връх. Тази проверка обаче не работи за корена на дървото, тъй като няма върхове, които да са преди него. Но корена е точка на свързване ако има повече от един наследник, тъй като единствения път между наследниците на корена е през самия корен. Тези промени се реализират, като процедурата visit се преработи на функция, която връща най – високата точка (т.е. с най – малък номер) от дървото, “видяна” по време на обхождането.

1 function visit(k:integer):integer;

2 var t:link; m,min:integer;

3 begin

  1. id:=id+1; val[k]:=id; min:=id;

  2. t:=adj[k];

  3. while t<>z do begin

  4. if val[t^.v]=0 then begin

  5. m:=visit(t^.v);

  6. if m<min then min:=m;


Други реферати:
Шинел
Светът на Никотиана в романа Тютюн на Димитър Димов
Шекспировата трагедия Хамлет
Символизмът-българските измерения
Снаха-ценности и цялостност, инфлация и разпад


Изтегли реферата



Снаха-ценности и цялостност, инфлация и разпад - Facebook Image
Сайтът се поддържа от DH Studio | pomagalo1.com © 2012 | Общи условия