Qayta o ’ qish

Rang berish algoritmlarini amalga oshirish 
Krasnova A. Yu.ning nomzodlik dissertatsiyasida “Indisiyalarning matritsalari va 
grafikni bo'yash" oddiy grafikni bo'yash algoritmi taklif etiladi, insidans matritsasi 
va ketma-ketligini hisobga olishga asoslangan shu jumladan, grafik uchlari
to'plamining bo'sh bo'lmagan kichik to'plamlarini tanlash ranglar sonini 
yaqinlashtirishga imkon beruvchi aralashtirish tartibi xromatik raqam. 
Algoritm ketma-ket algoritmning bir variantidir sanab o'tish, lekin aralashish va 
takrorlash bilan. Bunday yaxshilanish natijaning cho'qqilarning dastlabki 
raqamlanishiga bog'liqligini kamaytirishga yordam beradi. Algoritm asl nusxani 
saqlash uchun insidans matritsasidan foydalanadi cho'qqilarni raqamlash, unga 
raqamlar bilan I ustun tayinlanadi. Quyida algoritm [1]. 
1-QADAM. G(V, X) grafigi A qo‘shnilik matritsasi bilan berilgan bo‘lsin. Unga 
asoslanib, quramiz.insidans matritsasi B. Matritsaga ketma-ketlik algoritmini 
qo'llashvertex ranglanishi, biz r rangdagi rang va matritsani olamiz P0 o'zgarishlari 
Bt = P0B bo'lsin. QADAM 2. Aralashtirishlar sonini H o'rnating. 
QADAM 3. Aralashtirish protsedurasining n ta takrorini bajaring. Qayerda biz Bt 
deb taxmin qilamiz 
(0) = P0B va u 
(0) = P0I. 
Keyin k-iteratsiya quyidagicha sodir bo'ladi: 
1. Bs insidans matritsasini tuzing 
(k) = QBt 
(k-1) 
. 
2. Bs matritsaga amal qiling 

---

(k) 
ketma-ket rang berish algoritmi 
tepaliklar va "kengaytirilgan" insidans matritsasi yaratish 
Bs 
(k) chap tomonda unga Is ustunini belgilang 
(k) = QIt 
(k-1). Rang berish 
rk ranglariga va Pk almashtirish matritsasiga, shunday qilib Bt 
(k) = PkBs 
(k) 
. Qayerda 
Bu 
(k) = PkI 
(k) 
." 
Algoritmni amalga oshirishda foydalanishdan voz kechishga qaror qilindi 
insidans matritsalari, chunki grafikning qo'shnilik matritsasi imkon beradi 
ishlatiladigan RAM miqdorini kamaytirish.