Qayta o ’ qish

to‘rt xil bo‘yoq masalasi
deb yuritila boshlandi. 1976 yilda 
amerikalik olimlar Kennet Appel va Volfgan Xakenlar maxsus kompyuter dasturlari 
orqali 4 xil bo‘yoq haqidagi teoremani isbotlashdi.
Теоrema (to‘rt xil bo‘yoq haqidagi teorema).
Ixtiyoriy G planar graf to‘rttadan 
ortiq bo‘lmagan ranglar bilan tog‘ri bo‘yalishi mumkin, ya’ni 
𝜒(𝐺) ≤ 4
. 
Graf xromatik sonini baholashning bir qancha evristik algoritmlari mavjud. 
Xasis 
algaritm
deb nomlanuvchi algoritmni keltirib o‘tamiz. Ranglarni 
𝐶
1
, 𝐶
2
, … , 𝐶
𝑞
bilan 
belgilaymiz va
𝐶
𝑖
ni
𝑖
-rang deb ataymiz. 
 
Xasis algoritm quyidagilardan iborat: 
(a) uchlarni biror bir tartibda joylashtiriladi: 
𝑣
1
, 𝑣
2
, … , 𝑣
𝑝
; 
(b)
𝑣
1
uchni 
𝐶
1
rangga bo‘yaladi; 
(c) agar
𝑣
1
, … , 𝑣
𝑖
uchlar bo‘yalgan bo‘lsa, u holda 
𝑣
𝑖+1
uchni bu uch bilan qo‘shni 
bo‘lgan uchlarni bo‘yash uchun ishlatilmagan ranglar ichida eng kichik 
 j-
nomerli 
𝐶
𝑗
rangga bo‘yaladi. 
Xasis algoritmdan foydalanilgan holda olingan bo‘yashning optimalligi, uchlarni 
joylashtirishni tanlab olish tartibiga bog‘liq. Har doim uchlarni joylashtirishning 
shunday tartibi mavjudki, xasis algoritmni optimal
𝜒(𝐺)
bo‘yashlar soniga olib 
keladi.
Shuni ta’kidlab o‘tish kerakki, xasis algoritm yordamida grafni bo‘yashda, 
d
darajali uchni bo‘yashdagi erishilmagan ranglar soni 
d
sonidan ortmaydi, demak 
𝑖 ≤
𝑑 + 1
nomerli 
𝐶
𝑖
rang ishlatilishi mumkin. Shuning uchun ham quyidagicha baho 
o‘rinli.