25-Graflarni bo‘yash

25-Graflarni bo‘yash

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, ya’ni .