9-ma’ruza. Saytlarni aylanish va tanlash algoritmlari. Reja

var used[q]: boolean init false barcha u Out(this) uchun ;
pre : site init u def ;
Initsiator uchun (bir marta bajariladi) :
begin pre := this ; tanlovuOut(this);
used[u] := true ; outtoken to u ;
end
S dan token qabul qilinganda barcha jarayonlar uchun:
begin if pre= udef then pre:= s;
if uOut(this) : used[u]
then return(OK)
else if uOut(this): (upre&used[u])
then begin tanlash uOut(this) \ {pre} сused[u] ;
used[u] := true ; outtoken to u
end
else begin used[pre] := true ;
outtoken to pre
end
end

Har bir saytning jarayoni har bir kanal orqali bir marta marker yuborganligi sababli, har bir jaraayon har bir kanal orqali bir marta marker qabul qiladi. Har safar marker u noinitsiatori tomonidan egallanganda u jarayon yuborganiga nisbatan bir marta ko`p marker qabul qiladi. Bundan ko`rinib turibdiki, u ga to`qnashgan kanallar soni u da ishlatilgan kanallar sonini hech bo`lmaganda bittaga oshiradi. Bunda u jarayonni yakunlamaydi, markerni keyingisiga yuboradi. Jarayon initsiator – saytda yakunlanadi.

Quyida har bir jarayon marker yuborgach algoritm yakunlanishi ko`rsatilgan.

1. 
   Initsiatorda tutashgan barcha kanallar ikki yo`nalishda bir martadan o`tilishi kerak. Initsiator tomonidan marker barcha kanallar bo`yicha yuborilgan bo`lishi kerak, aks holda algoritm yakunlanmaydi. Initsiator qancha marker yuborgan bo`lsa shuncha marker qabul qiladi; har safar initsiator boshqa kanal orqali marker qabul qilganda, marker har bir kanal orqali bir martadan yuboriladi.
   
2. 
   Har bir jarayon va barcha kanallar uchun tutashganlar har bir yo`nalishda bir martadan o`tilishi kerak. Buni teskari qabul qilsak, u sifatida birinchi uchragan jarayonni tanlaymiz, bunda yuqoridagilar bajarilmaydi va (1) punktga asosan u initsiator hisoblanmaydi. u tanlovidan va u o`zidan oldingisiga marker yuborganligidan ko`rinib turibdiki, barcha kanallar va tutashganlar pre (u) ikki yo`nalishda bir martadan o`tilgan. u barcha tutashgan kanallardan marker yuborishda foydalangan, lekin marker oxirida initsiatorda qolganligi sababli, u qancha marker yuborgan bo`lsa shuncha marker qabul qildi, shuningdek u har bir tutashgan kanal orqali bir martadan marker qabul qildi. Bu yerda biz fikrlar qarama – qarshiligiga duch keldik.
   
3. 
   Barcha jarayonlar bajarilishi kerak va har bir kanal ikki yo`nalishda o`tilishi kerak. Agar bajarilmagan jarayonlar mavjud bo`lsa, u va s qo`shnilari mavjud bo`ladi, bunda u bajarilgan s esa bajarilmagan bo`ladi. Bu u ning barcha kanallari orqali ikki yo`nalishda o`tilganligiga qarshilik bildiradi. (2) punktga asosan barcha jarayonlar bajarilishi kerak va barcha kanallar ikki yo`nalishda o`tilishi kerak.
   

Tarri algoritmining har bir yechilishi graf daraxtining asosini aniqlaydi. Daraxtning ildizida initsiator joylashgan, har bir u noinitsiator esa hisoblash so`nggida o`zidan avvalgi pre o`zgaruvchisini daraxtga kiritadi.