Lekciya 13. Saytlardı shetlep ótiw algoritmları Joba: Tolıq graftı shetlep ótiw algoritmi

Giperkub shetlep ótiw algoritmı
Graflar teoriyasında n ólshemli kublar yamasa giperkublar dep atalatuǵın qn grafi málim. Bul toplam qn = K2 Qn - 1, Q = K2 formulaları menen xarakterlenedi. Bul erda K2-eki tóbelikke iye bolǵan tolıq graf, yaǵnıy bir qabırǵa menen baylanısqan eki tóbelik. " «» Operatsiyası - graflardı kóbeytiw.
A hám B grafları ushın bul operatsiya tómendegishe anıqlanadı.
Operatsiya nátiyjesi C = A x B grafigi bolıp, onıń kóplegen ústinleri a hám B, v (C) = v (A)x v (B) ústinleriniń kóp sanlı Kartal jumısı menen óz-ara bir-birine baylanıslı.
Kóp qabırǵa E (C) count C kóplegen qabırǵalar E (a) hám E (B) tárepinen islep shiǵarıladı.
v₁ V(C) dıń joqarı bólegi (a₁ , b₁), a₁ V(A), b₁ V(B) jup tóbesine, hám v₂ V(C) bolsa (a₂ , b₂), a₂ V(A), b₂ V(B) jup tóbege, keyin v1 v2 qońsılas (olardıń arasındaǵı qabırǵa ámeldegi), eger eki shárttenn biri orınlansa :
1 ) a1 = a2 hám b1 qońsılas b2 ;
2) b 1 = b2 hám A1 qońsılas a2 ;

Giperkub Q 1 = K2, yaǵnıy geometriyalıq sırtqı kórinislerdi súwretlew kózqarasınan " segment" bolıp tabıladı. 2 vertices óz ishine aladı. Olardıń hár birewiniń dárejesi birlikke teń. Grafika teoriyası kózqarasınan Giperkub Q2 tórtew vertikaning aylanıwı, geometriyalıq kóriniste-kvadrat. Hár bir vertexning dárejesi 2. Q3 giperkub geometriyalıq súwretnıń tóbeleri hám qırları menen ańlatılıwı múmkin - kub. Bul giperkub 8 dárejedegi 3 vertikalların óz ishine aladı.

Sol munasábet menen, vertex nomerleriniń n bıyt - ekilik súwretsı menen qatarlardı kodlaw qolay : 000... 0 den 111... 1 ge shekem. Nomerdiń shep múyeshi (sızıq belgisi) nol dep ataladı, oń (n - 1) - m. keyin olardıń kodları bir bıyt menen anıq parıq etetuǵın bolsa, eki tóbelik giperkubaga jalǵanǵan. Mısal ushın, 010 kodı menen birge bolǵanlar 110, 000, 011 kodları menen joqarı boladı.
Hár bir túyin ol intsident qabırǵalar 0 den n - 1 gacha nomerler menen ózgertiliwi múmkin, sol sebepli 0 qabırǵa nomeri ol túyinin ol túyinine ol túyinine ol túyinine jalǵanadı, onıń kodı ol kodınan nol aǵımında parıq etedi. Soǵan kóre, 1-sanlı qabırǵa birinshi taypa daǵı kod daǵı parq hám basqalar menen tepaga baradı.
Giperkub ushın algoritm daǵı háreketler.

Iniciator ushın (bir ret ámelge asıriladı ):

kanallarning qandayda-birı da bul baspa menen jalǵawmadi
Markerdi alıwda hár bir process ushın (júzimen, k):
begin if k=2ⁿ then return(OK)
else begin пусть l - наибольший номер, такой, что 2^l|k;