|
9-ma’ruza. Saytlarni aylanish va tanlash algoritmlari. Reja
|
| bet | 3/11 | | Sana | 10.08.2024 | | Hajmi | 172,01 Kb. | | #269345 |
Bog'liq 9а-mavzu (1)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.
Giperkub aylanishi algoritmi.
Graflar teoreyasida qn graflar sinfi mavjud bo`lib, ular n o`lchamli kublar yoki giperkublar deb ataladi. Bu oila quyidagi formulalar ko`rinishida tuziladi Qn = K2Qn – 1 , Q 1 = K2 . Bu yerda K2 - 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 = AB 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. v1V(C) uchi ikki uchlardan (a1 , b1), a1V(A), b1V(B), iborat bo`lsin, v2V(C) uchi esa ikki uchdan V((a2 , b2), a2V(A), b2B)bo`lsin, bunda quyidagi shartlardan biri bajarilsa v1 va v2 (ular o`rtasida qovurg`a mavjud) chegaradosh hisoblanadi:
1) a1 = a2 va b1chegaradosh b2 ;
2) b 1 = b2 va a1 chegaradosh a2 ;
Q 1 = K2 giperkubi geometric shakllar ko`rinishi nuqtai nazaridan “qirqim” hisoblanadi. U ikki uchdan iborat. Ularning har bir darajasi 1 ga teng. Q2 giperkubi graflar nazariyasi nuqtai nazaridan to`rt uchdan iborat tsikl, geometric ko`rinishi esa kvadrat hisoblanadi. Har bir uchning darajasi 2 ga teng. Q3 giperkubi uchlari va qovurg`alari bilan geometric shakl – kubga kub sifatida tasvirlanadi. Bu giperkub uchinchi darajaga ega bo`lgan 8 uchdan iborat.
Umuman olganda Qn giperkubi n darajadagi 2nuchlardan 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):
|
| |
