Qayta o ’ qish

---

Muxammad al-Xorazmiy nomidagi Toshkent 
axborot texnologiyalari universiteti 
 
Ma
’
lumotlar tuzulmasi va algoritmlar Fanidan 
qayta o
’
qish

 

MUSTAQIL ISHI 
 
 
Mavzu: 
Graflarni bo’yash. Graf xromatik sinfi va 
xromatik soni. Bixromatik graflar
 
 
 
 
Guruh: MTH002
 
(223-21) 
Bajardi:
Hamroyev Shaxzod Baxtiyor o
’
g
’
li
Tekshirdi: 
Normonov Otabek Abdigapparovich
Toshkent- 2023 

---

25-variant

REJA: 
1.
 
Kirish 
2.
 
Graflarni bo’yash
3.
 
Graf xromatik sinfi va 
xromatik soni.
4.Bixromatik graflar 
5.Xulosa 

---

Kirish: 
Grafik nazariyasi so'nggi bir necha yil ichida faol rivojlandi.bir necha o'n yillar. Bu 
tez kengayishi bilan bog'liq Grafiklar nazariyasini qo'llash sohasi, muammolar soni 
grafik nazariyasi usullari yordamida yechish mumkin. Masalan, navigatsiya va 
tarmoq bilan bog'liq vazifalar uchun asosiy, grafikdagi eng qisqa yo‘lni topish 
masalasidir. Yana bir dolzarb mavzu vazifa - bu rejalashtirish muammosi. Vazifa 
nazarda tutadi mutlaqo har qanday jadvalni tuzish: maktab jadvalidan tortib to 
korxonada ishlash tartibi. Ushbu vazifada cheklovlar vazifalarni (darslar, ish va 
boshqalar) bajarishning mumkin emasligi. bir vaqtning o'zida bir nechta sabablarga 
ko'ra. Bu muammo doimo paydo bo'ladi turli vaziyatlar, shuning uchun uni hal qilish 
uchun, samarali algoritm. 
 
Grafiklar nazariyasining qiyin muammolaridan biri topish masalasidir grafikning 
xromatik raqami, ya'ni ranglarning minimal soni, grafikning uchlarini ranglash 
uchun kerak. Har xil bu muammoni hal qilish uchun algoritmlar, ammo, samarali 
algoritm izlash davom etadi. Vertex rang berish ko'plab muammolarni 
modellashtirishga imkon beradi rejalashtirish. Xususan, grafikni bo'yash 
algoritmidan foydalanib, mumkin rejalashtirish muammosini hal qilish. 
Grafni bo‘yash
. Grafning xromatik soni. Kyonig teoremasi (grafning 
bixromatikligi). Planar grafni to‘g‘ri bo‘yash hadidagi teorema. Graf xromatik 
sonini topishning evristik algoritmi.