Qayta o ’ qish

 
Grafikni bo'yash algoritmi 
Keyinchalik, sifatida tuzilgan yangi grafik rang berish algoritmini ko'rib chiqing 
ochko'z algoritm. Aksariyat hollarda, avval aytib o'tilganidek, ochko'zlik 
Algoritmlar cho'qqilarni darajalari (yoki nisbiy darajalar, ya'ni rangli cho'qqilarni 
hisobga olmasdan darajalar). Bu mantiqiy,chunki bunday cho'qqilarni ranglash eng 
ko'p keltiradi tizimga ma'lumot: bunday cho'qqilarni bo'yash bilan biz rang bera 
olmaymiz bu cho'qqi uchun tanlangan rangda ko'proq ranglar. Uchun ishlab 
chiqilgan algoritmdan faqat cho'qqilar darajasidan foydalanishga qaror qilindi 
ikkinchi darajali omil sifatida. Taqqoslash uchun asosiy omil bu edi cho'qqisini endi 
bo'yash mumkin bo'lmagan ranglar soni tanlanadi. Lekin ko'p hollarda, bu 

---

yondashuv ranglarning to'liq hovuzini tashkil qiladi, chunki birinchi navbatda 
qo'shish kerak bo'lgan cho'qqilarni ko'rib chiqadi rang. Bundan tashqari, algoritmdan 
foydalanish kerakligini bilish rejalashtirish muammosini hal qilish, biz nafaqat 
buyurtma beramiz cho'qqilarni, balki ranglarni ham cho'qqilarning taqsimlanishini
amalga oshirish uchun va shunga mos ravishda va yuk, ko'proq bir xil. Kirish sifatida 
algoritm standart fayllarni oladi DIMACS formatidagi grafiklarni tavsiflash uchun 
[8], bu esa undan foydalanish imkonini beradi grafiklarni bo'yash uchun alohida 
dastur. Fayl bir marta o'qiladi, keyingi ish qo'shni matritsa bilan sodir bo'ladi. 
Algoritmda quyidagi bosqichlarni ajratib ko'rsatish mumkin: 
1. Fayldan ma’lumotlarni o‘qing va uning asosida qo‘shnilik matritsasini tuzing. 
2. O'z ichiga olgan rang vektorini (dastlab bo'sh) boshlang mos keladigan rangga 
bo'yalgan uchlari vektori. Bu yerda rangli vertex qo'shilgan 
3. Cho‘qqilar vektorini hosil qiling. Cho'qqilar haqidagi ma'lumotlarni saqlash 
uchun Vertex klassi grafikdagi cho'qqilar sonini, uning darajasini va darajasini o'z 
ichiga olgan holda yaratilgan rang berish mumkin bo'lmagan ranglar vektori. 
4. Cho'qqilar vektorini ustuvorlik bo'yicha tartiblang. Vertex ustuvorligi ko'proq 
ranglarda bo'yash mumkin bo'lmasa ko'proq; agar ranglar soni teng bo'lsa, u holda 
yuqori darajaga ega cho'qqi ko'proq ustuvor hisoblanadi. 
5. Eng kam uchraydigan ranglarni tekshirib, tepa uchun rangni tanlang. Barcha 
mavjud ranglar raqam bo'yicha tartiblangan vektorda saqlanadi berilgan rangga ega 
uchlari. Kirish tekshiriladi ko'rib chiqilayotgan rangni bo'yab bo'lmaydigan ranglar 
vektoriga aylantiring yuqori.