|
Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali kompyuter injiniring fakulteti
|
| bet | 1/4 | | Sana | 11.11.2022 | | Hajmi | 0.74 Mb. | | #29855 |
Bog'liq Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari u ffJhTciKTsOMpxLHuJGUjWEIeUAiplNL7WwhnrHw, sodapdf-converted, Kasb tanlashga yo‘llash, Ijara shartnoma 1680543268498, Using Technology and Collaboration to Support Reading Comprehensi, mustaqil ish, EhtimolExcel, mavzu04, Reja, Hujjat (2), mm, 2-mustaqil, 2-mavzu-1, Cho’yanlarni mikrostrukturalarining tahlili
O'ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI
KOMPYUTER INJINIRING FAKULTETI
KI-11/19 (C) GURUH TALABASINING
DISKRET TUZILMALARI
FANIDAN
MUSTAQIL ISHI
Bajardi: Omonov A
Qabul qildi: Ro'zmurodov I
Qarshi-2021
Mavzu: Graflarni bo'yash. Grafning xromatik soni. To'rt xil rang haqidagi gipoteza. Kyonig teoremasi. Grafning xromatik sonini topishning evr istik algoritmi
Reja:
Graflarni bo'yash
Grafning xromatik soni
To'rt xil rang haqidagi gipoteza
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.
Ta’rif. Aytaylik garf va ranglar toplami deb ataluvchi biror bir to‘plam berilgan bo‘lsin. Har qanday akslantirishga G grafni bo‘yash deyiladi. Bo‘yash to‘g‘ri deyiladi, agar qo‘shni uchlar turli xil ranglarga bo‘yalgan bo‘lsa, ya’ni
G grafni to‘g‘ri bo‘yashni qurish uchun zarur bo‘lgan, minimal ranglar soniga xromatik son deyiladi va kabi belgilanadi.
Ikki ulushli graf uchlar to‘plamini ikkita to‘plam ostiga bo‘lish mumkin va bu to‘plamdagi elementlar bir biriga qo‘shni bo‘lmaydi, u holda grafning bunday uchlari ikki xil rangda to‘g‘ri bo‘yash mumkin, ya’ni ikki ulushli graf xromatik soni 2 ga teng.
Xromatik soni 2 ga teng bo‘lgan graf, bixromatik deyiladi.
Kyonig teoremasi. Graf bixromatik bo‘lishi uchun, toq uzunlikdagi sikllari bo‘lmasligi zarur va yetarli.
Umumiy holda grafning xromatik sonini aniqlash trivial savol emas. Lekin grafning xromatik soni bahosiga nisbatan birqancha faktlar ma’lum.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali kompyuter injiniring fakulteti
|
