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

out (token, 1) through U
Har bir saytning marker qabul qilgandan keyingi harakati (token, k):
begin if k= m*n then return(OK)
else if (kmod n = 0) then out(token,k+1) through U
elseout(token,k+1) through R
end
9.2 va 9.3- rasmlarda 3 x4 va 2 x 5 torlarning aylanish taartibi ko`rsatilgan. Aylanishning initsiator – sayti yulduzcha bilan belgilangan, “OK” harflari esa aylanishning tugaganligini xabar qiladigan saytni bildiradi. Qovurg`a oldida qiymati k ga teng bo`lgan son yozilgan, bu son bu qovurg`a bo`ylab bir saytdan boshqa saytga uzatiladi.

9.2- rasm. 3x4 torning aylanish tartibi.

9.3-rasm. 2 x 5 torning aylanish tartibi.

3. 
   Giperkub aylanishi algoritmi.
   

Graflar teoreyasida q_n graflar sinfi mavjud bo`lib, ular n o`lchamli kublar yoki giperkublar deb ataladi. Bu oila quyidagi formulalar ko`rinishida tuziladi Q<sub>n</sub> = K<sub>2</sub>Q<sub>n – 1</sub> , Q <sub>1</sub> = K<sub>2</sub> . Bu yerda K<sub>2</sub> - bir qovurg`a bilan birlashtirilgan ikki uchli to`liq grafdir. «» amali - ko`paytirish amalidir.
Bu amal A va B graflar uchun quyidagicha bajariladi.
Bu amal natijasi C = AB grafi hisoblanadi, ko`plab uchlar dekat asaridagi A va B graflar uchi ko`pligiga o`xshash qiymatli aloqada bo`ladi, V(C) = V(A) V(B).C grafning E(C) qovurg`alar ko`pligi E(A) va E(V) ko`paytmasidan vujudga keladi. v<sub>1</sub>V(C) uchi ikki uchlardan (a<sub>1</sub> , b<sub>1</sub>), a<sub>1</sub>V(A), b<sub>1</sub>V(B), iborat bo`lsin, v₂V(C) uchi esa ikki uchdan V((a₂ , b₂), a₂V(A), b₂B)bo`lsin, bunda quyidagi shartlardan biri bajarilsa v<sub>1</sub> va v<sub>2</sub> (ular o`rtasida qovurg`a mavjud) chegaradosh hisoblanadi:
1) a<sub>1</sub> = a<sub>2</sub> va b<sub>1</sub>chegaradosh b<sub>2</sub> ;
2) b <sub>1</sub> = b<sub>2</sub> va a<sub>1</sub> chegaradosh a<sub>2</sub> ;
Q <sub>1</sub> = K<sub>2</sub> giperkubi geometric shakllar ko`rinishi nuqtai nazaridan “qirqim” hisoblanadi. U ikki uchdan iborat. Ularning har bir darajasi 1 ga teng. Q₂ giperkubi graflar nazariyasi nuqtai nazaridan to`rt uchdan iborat tsikl, geometric ko`rinishi esa kvadrat hisoblanadi. Har bir uchning darajasi 2 ga teng. Q₃ giperkubi uchlari va qovurg`alari bilan geometric shakl – kubga kub sifatida tasvirlanadi. Bu giperkub uchinchi darajaga ega bo`lgan 8 uchdan iborat.
Umuman olganda Q_n giperkubi n darajadagi 2ⁿuchlardan iborat. Bu bilan uchlarni n dagi qatorlar, bit – uchlar raqamining ikkilik ko`rinishi: 000 … 0 dan 111 … birgacha bilan kodlash qulaydir. Raqamning (qator belgisi) chap razryadini nol razryad deb ataymiz, o`ngini esa (n – 1)-мdeb ataymiz. Shundan giperkubdagi uchlar bir bit bilan farq qilsa chegaradosh bo`ladi. Masalan, 010 kodli uch bilan 110, 000, 011 kodli uchlar chegaradoshdir. Har bir u tugunga tutashgan qovurg`alarni 0 dan n – 1 gacha bo`lgan sonlar bilan raqamlash mumkin, bunda 0 raqamli qovurg`a u tugunni giperkubning, u ning 0 razryaddagi kodidan farq qiladigan kodli tuguniga ulaydi. Shuningdek 1 raqamli qovurg`a 1 razryaddagi kodi farqi bo`lgan uchga boradi va hokazo.
Algoritmda Giperkub uchun amal.
Initsiator uchun (bir marta bajariladi):