29-сур. Керуші ағаш құрудың екі әдісі
Тереңдікке және кеңдікке іздеу процедураларын керуші ағаштарды
табу үшін қолдануға болады. Екі жағдайда да v шыңынан u
шыңына жету
ағашқа {v,u} қабырғасын қосуға әкеледі.
Байланысқан графтың керуші ағашын тереңдікке іздеу әдісімен табу
алгоритмін қарастырайық. G=
E> бастапқы графы ТІЗІМ[v], v€V
инциденттілік тізімдерімен берілген. Алгоритмді WGD(v) процедурасы
арқылы жүзеге асырамыз:
1 PROCEDURE WGD(v);
{ ЖАҢА, ТІЗІМ, Т (бұтақтар жиынтығы) айнымалылары- глобалды}
2 BEGIN ЖАҢА [v] := false;
3 FOR u
∈
ТІЗІМ [v] DO
4 IF ЖАҢА [u] THEN BEGIN
5 Т := Т {v, u}; {жаңа бұтақ қосу}
∪
6 WGD(u)
7 END
8 END {WGD};
Негізгі бағдарлама
1 BEGIN
2 FOR u
∈
V DO ЖАҢА [u] := true; { инициализациялау }
3 Т := ;
∅
4 WGD( r ) {г – ерікті шың }
5 END
Мұндай алгоритм ерікті байланысқан графтың ерікті ағашын дұрыс
құратындығын дәлелдеуге болады. Бұл үш фактордан шығады:
1) Т жиынтығына жаңа {v, u} (5 жол WGD) бұтағын қосу сәтінде Т> ағашта r-дан v-ға апаратын жол болады. Сөйтіп, алгоритм байланысқан
граф құрады;
2) Т жиынтығына қосылатын әрбір жаңа {v, u} бұтағы қарастырылып
кеткен v шыңын жаңа u шыңымен қосады. Осыдан құрылған
графының циклдері болмайды. (Шындығында, циклді тұйықтайтын соңғы
бұтақ қарастырылып кеткен екі шыңды қосу керек);
3) тереңдікке іздеудің қасиетінен WGD бағдарламасы байланысқан
графтың барлық шыңдарын қарастыратыны шығады.
Яғни, біздің алгоритм бойынша құрылған графы G графының
керуші ағашы болып табылады. Алгоритмді есептеу күрделілігі C(n+m) ретті
болады, яғни тереңдікке іздеу сияқты.
Біздің мысал үшін тереңдікке іздеу арқылы құрылған керуші ағаш 30,а-
сур. көрсетілген. Іздеу басталатын г шыңы ағаш тамыры болып табылады.
ағашында ерікті шыңнан тамырына дейін бір жол бар екені анық. <V,
T> ағашының түрлі екі v және u шыңдары үшін егер u шыңынан тамырға
апаратын жолда v жатса, онда u шыңы v ұрпағы болады деп айтамыз.
30-сур. Тереңдікке және кеңдікке іздеу арқылы құрылған
керуші ағаштар
Осы сияқты әдіспен кеңдікке іздеу әдісін қолданып, керуші ағаш
құруға болады. Бұл әдісті іске асыратын алгоритмді былай жазуға болады:
1
BEGIN
2 FOR u
∈
V DO ЖАҢА [u] := true; { инициализациялау }
3 Т :=
∅
; {осы уақытқа дейін табылған бұтақтар жиынтығы }
4 КЕЗЕК :=
∅
; КЕЗЕК <= г;
5 ЖАҢА [г] := false; {r – керуші ағаштың тамыры}
6 WHILE КЕЗЕК ≠
∅
DO BEGIN
7 v <= КЕЗЕК;
8 FOR u
∈
ТІЗІМ [u] DO
9 IF ЖАҢА [u] THEN BEGIN
10 КЕЗЕК <=u; ЖАҢА [u] := false; Т := Т
∪
{v, u}
11
END
12
END
13 END
Жоғарыда жасалған талдаулар арқылы берілген алгоритм ерікті
байланысқан граф үшін керуші ағашты 0(n+m) қадам ішінде, яғни C(n+m)
артық емесқадам ішінде құратындығын көрсетуге болады.
30,6-суретте біздің мысал үшін кеңдікке іздеу әдісімен құрылған ағаш
көрсетілген.
Кеңдікке іздеудің айтылып кеткен артықшылықтары келесі
қорытындыға әкеліп соғады.
- G = ерікті байланысқан графы үшін кеңдікке іздеу
әдісімен құрылған керуші ағаш болсын. Онда v ерікті шыңынан г
тамырына апаратын G графындағы v-дан г –ге ең қысқа жол болады.
Керуші ағаштар жайындағы барлық талдауларды ерікті, байланыты
болуға міндетті емес графтарға қолдануға болады. G ерікті графының
циклсіз максималды бағыныңқы графы G графының керуші орманы деп
аталады. K байланыстылық компоненті бар графтың керуші орманы сол
компоненттердің керуші ағаштарымен анықталады, яғни оның n-k-1
қабырғасы бар.
Керуші ағашты табу мәселесімен графтан циклдердің фундаменталды
жиынтығын табу мәселесі тығыз байланысты.
Графтан циклдердің фундаменталды жиынтығын
табу
Егер G =
графының керуші ағашына е
∈
Е\Т ерікті
хордасын қоссақ, онда шыққан С = бағыныңқы графында нақты
бір цикл бар (мұнда цикл деп элементарлы циклді айтамыз. Бұл циклді Се
деп белгілейміз. С = {С
е
: е
∈
Е \ Т} жиынтығын G графының фундаменталды
жиынтығы ( керуші ағашына қатысты) деп атаймыз. "Фундаменталды"
деп атауымыз G графының әрбір циклін G жиынтығының циклдерінен оңай
алуға болатындығымен байланысты.
Циклдердің фундаменталды жиынтығын табудың қолданбалы мәні
бар, мысалы, электр тізбектерінің анализі кезінде. Нақтырақ, берілген электр
тізбегіне сәйкес графтың әрбір фундаменталды цикліне кернеуге арналған
Кирхгоф заңын сәйкестендіруге болады: циклдің бойымен түскен кернеулер
қосындысы 0-ге тең. Циклдердің фундаменталды жиынтығын табу тізбектің
математикалық сипаттамаларында тәуелсіз теңдеулерді көрсетуге мүмкіндік
береді.
Енді циклдердің фундаменталды жиынтығын табудың қарапайым
алгоритмін сипаттайық. Алгоритм тереңдікке іздеуге негізделген және
керуші ағашты табудың рекурсивті алгоритміне аналогиялы құрылымға ие.
Іздеу прцесінде кездескен әрбір жаңа шың СТЕК кестесінде
көрсетілген стекке орналастырылып, қолданылғаннан кейін жойылады.
Стекте берілген уақыт моментінде қарастырылып жатқан v шыңынан
басталып, тамырына апаратын шыңдар тізбегі орналасады.
Сондықтан, егер біз қарастырып жатқан {v, и} қабырғасы циклді
тұйықтаса (яғни WGN[v] > WGN[u] > 0 b және стектің жоғарғы элементінің
астында орналасса), онда u шыңы стекте орналасқан және {v, u}
қабырғасымен тұйықталған циклі стектің v-ден бастап, u шыңына дейінгі
элементтер тобымен көрсетілген.
1 PROCEDURE
ЦИКЛ
(
V
);
{d, num, СТЕК, ТІЗІМ, WGN айнымалылары- глобалды}
2 BEGIN d := d+1; CTEK[d] := v; num := num+1; WGN[ ] := num;
3 FOR u
∈
ТІЗІМ [v] DO
4 IF WGN[u] = 0 THEN цикл(г)
5 ELSE IF (u
≠
CTEK[d-l]) and (WGN[v] > WGN[u]) THEN {{v,
u} қабырғасы жаңа циклді тұйықтайды)
6 шыңдары бар циклді жазып алу
7 CTEK[d], CTEK[d-l],.... СТЕК[с], мұнда СТЕК[с] = u
8 d:=d-l {қолданылған v шыңы стектен жойылады }
9 END (цикл};
Негізгі бағдарлама:
