Qayta o ’ qish

Теоrema. 
Agar G graf uchlarining maksimal darajasi 
d
ga teng bo‘lsa, u holda xasis 
algoritm yordamida graf uchlarini 
𝑑 + 1
dan ortiq bo‘lmagan rangga bo‘yash 
mumkin, ya’ni
𝜒(𝐺) ≤ 𝑑 + 1
. 

---

Ta’rif.
Graf uchlarining A to‘plamostisiga tegshli ixtiyoriy ikkita uch qo‘shni 
bo‘lmasa, bunday to‘plamosti
ichki barqaror
deyiladi. Agar ushbu xossani 
buzmasdan birorta ham uch bilan to‘ldirishni iloji bo‘lmasa, bu to‘plam ichki 
barqarorlik xossasiga nisbatan 
maksimal
deyiladi.
Grafning quvvati bo‘yicha maksimal sondagi elementlarga ega bo‘lgan ichki 
barqaror to‘plamining elementlar soniga ichki barqarorlik soni deyiladi va 
quyidagicha belgilanadi 
𝛼(𝐺) = max
𝐴∈𝑉(𝐼)
|𝐴|,
Bunda
𝑉(𝐼)
– G grafning ichki barqaror to‘plamostilar to‘plami.
 Ta’rif.
Agar grafning ixtiyoriy uchi uchun grafning B to‘plamostisida uning 
qo‘shnisi bo‘lsa, B to‘plamostiga 
tashqi barqaror
deyiladi. Agar boshqa birorta 
ham tashqi barqaror to‘plamga ega bo‘lmasa, bu to‘plam 
minimal
deyiladi,
Quvvati bo‘yicha minimal bo‘lgan tashqi barqaror to‘plamning elementlar soniga, 
tashqi barqarorlik soni
deyiladi va quyidagicha belgilanadi 
𝛽(𝐺) = min
𝐵∈𝑉(𝐷)
|𝐵|,
bunda 
𝑉(𝐷)
– G grafning barcha tashqi barqaror to‘plamostilar to‘plami. 
Ko‘rinib turibtiki, ichki barqaror to‘plam maksimal bo‘ladi, faqat va faqat qachonki 
u tashqi barqaror bo‘lsa. Lekin, tashqi barqaror to‘plam har doim ham ichki barqaror 
to‘plam bo‘lavermaydi. 
Ta’rif.
Graf uchlar to‘plamining to‘plamostisi bir vaqtnin o‘zida maksimal ichki 
barqaror va minimal tashqi barqaror bo‘lsa, bunday to‘plamostiga grafning yadrosi 
deyiladi.
Ushbu bobda biz cho'qqilarni bo'yash muammosini ko'rib chiqamiz oddiy grafik. 
Vazifalarni boshlashdan oldin Keling, quyida qo'llaniladigan grafik ta'rifini eslaylik 
grafiklar nazariyasini chuqurlashtirish. Ushbu maqoladagi "grafik" deganda biz 

---

tushunamiz oddiy yo'naltirilmagan grafik (1.1-rasm). Shuni ta'kidlash joizki 
Grafiklar nazariyasining ko'pgina ta'riflari har xilda turlicha berilgan 
manbalar, lekin ular oddiygina turli yondashuvlarni va ko'p qismini namoyish etadi 
bir-biriga zid bo'lmang. Ta'riflarni [2, 3, 4, 5] da topish mumkin. Grafik tartiblangan 
to‘plamlar juftligi (V, E), bunda V bo‘sh bo‘lmagan to‘plamdir. cho'qqilari, E esa 
(vi, vj) shaklning tartibsiz juftliklari to'plami, deyiladi qirralari, bu erda vi va vj V 
to'plamga tegishli. 
•
G = (V, E) grafigining vi va vj uchlari, agar ular qo‘shni deyiladi 
qirra bilan tutashtiriladi, ya’ni E.da chekka (vi, vj) bo‘lsa. 
•
Grafikni aniqlash usullaridan biri qo‘shni matritsadir -[NxN] o'lchamdagi A 
matritsasi, bu erda N - cho'qqilar soni a,i,j elementi, agar grafikdagi i va j uchlari 
qo‘shni bo‘lsa, 1, aks holda 0 bo‘ladi. 
1.1 Grafik misol 
Keling, grafikni bo'yash masalasini batafsil ko'rib chiqaylik. Bu vazifa grafik 
nazariyasida asosiylaridan biri hisoblanadi, chunki u NP to'liqlar sinfiga kiradi va bu 
sohadagi boshqa ko'plab muammolar unga qisqartiriladi. Grafik bo'yash kitob 
cho'qqi, chekka va jami [6] bo'lishi mumkin, ammo har uchala variant ham 

---

muammolarni bir-biriga qisqartirish mumkin, shuning uchun biz faqat tepalikni 
ko'rib chiqamiz rang berish grafigi."Grafikni bo'yash - bu unga ranglarning shunday 
tayinlanishi ikkita qo'shni cho'qqi bir xil qabul qilmaydigan cho'qqilar ranglar." 
1.2-rasmdagi grafikni bo'yash varianti. 1.1 
Rang berish vazifasi minimal sonni topishdir Grafikni bo'yash uchun ranglar. 
Bunday yechim deb ataladi optimal. Shaklda. 1.2 grafikning optimal ranglanishini 
ko'rsatadi, shaklda ko'rsatilgan. 1.1. Muammoning ma'lum birlashgan algoritmi yo'q 
polinom vaqtida yechim topish. Bular uchun variantlar mavjud faqat ma'lum turdagi 
grafikalar uchun echimlar. Yagona yondashuv Optimal echimni topish - bu 
variantlarni qidirish. Biroq noto'g'ri qidirish uchun turli yondashuvlar va algoritmlar 
taklif etiladi, taxminiy yechim, uni topish optimalga qaraganda ancha oson. Ulardan 
ba'zilari qanday ishlashi haqida qisqacha ma'lumot. 
 
•
Ketma-ket sanash algoritmlari. Bunday algoritmlar ketma-ket ajratilgan ranglar 
guruhlari. Har bir bosqichda ular ajratilmagan qo'shishga harakat qiladigan
cho'qqilar guruhicho'qqilarni rangi bo'yicha tartiblashguncha. 
•
Ochko'z algoritmlar. Ochko'z algoritmlar cho'qqilarni bo'yicha tartiblaydi har 
qanday qoida (ko'pincha ular ishlatadigan misollar mavjud cho'qqilarning darajalari) 

---

va ularga mos kelmaydigan ranglarni ketma-ket belgilang ularga tutash cho'qqilar 
bo'yalgan. 
•
Bit amallaridan foydalangan holda algoritm. Algoritm shunga o'xshash birinchisi, 
lekin bitli operatsiyalar yordamida matritsalar ustida ishlaydi. Bunday yondashuv 
ish vaqtini bir necha marta qisqartirishga imkon beradi [7]