Muhammad al-Xorazmiy nomidagi tatu qarshi filiali tt va kt fakulteti ax 12-22 guruh talabasi Xushvaqtov Abbosning Diskret Tuzilmalar fanidan tayyorlagan

Muhammad al-Xorazmiy nomidagi
TATU Qarshi filiali

TT va KT fakulteti
AX 12-22 guruh talabasi
Xushvaqtov Abbosning
Diskret Tuzilmalar
fanidan tayyorlagan

5-MUISTAQIL ISHI

1-MAVZU: 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.


Teorema. Agar G=(V,E) graf barcha uchlari darajalari k dan katta bo‘lmasa, u holda grafni to‘g‘ri bo‘yashni qurish uchun (k+1) xil rang yetarli bo‘ladi, ya’ni .

Shuni ta’kidlab o‘tish kerakki, xromatik sonning ushbu bahosi umumiy holda aniqdir, ya’ni shunday graflar mavjudki, ularning uchlarining darajalari k dan oshmaydi, xromatik soni k+1 ga teng. Masalan, to‘liq grafning uchlari darajalari ga teng, xromatik soni esa .
Grafning xromatik sonini baholash masalasida planar graflar muhim o‘rin tutadi. 19-asr oxirida ixtiyoriy planar grafning xromatik soni 5 dan oshmasligi isbotlandi. Lekin, xromatik soni 5 ga teng bo‘lgan planar grafga misol bo‘lmagan. Bu esa, planar grafni 4 xil bo‘yoq bilan to‘g‘ri bo‘yash mumkinligini taxmin qilishga asos berardi. Ushbu masala 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 .
Graf xromatik sonini baholashning bir qancha evristik algoritmlari mavjud. Xasis algaritm deb nomlanuvchi algoritmni keltirib o‘tamiz. Ranglarni  bilan belgilaymiz va ni -rang deb ataymiz.
Xasis algoritm quyidagilardan iborat:
(a) uchlarni biror bir tartibda joylashtiriladi: ;
(b) uchni rangga bo‘yaladi;
(c) agar uchlar bo‘yalgan bo‘lsa, u holda 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 nomerli rang ishlatilishi mumkin. Shuning uchun ham quyidagicha baho o‘rinli.


Теоrema. Agar G graf uchlarining maksimal darajasi d ga teng bo‘lsa, u holda xasis algoritm yordamida graf uchlarini dan ortiq bo‘lmagan rangga bo‘yash mumkin.
Grafda barqaror to‘plamlar

Barqaror to‘plamlar va ular bilan bog‘liq bo‘lgan sonli xarakteristikalar, grafning muhim tarkibiy xossalarini ifodalaydi. Tashqi va ichki barqaror to‘plamlarni farqlashadi.

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
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
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.