25-Graflarni bo‘yash

Тео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 .

Mashqlar
1. Graf uchlarini to‘g‘ri bo‘yang.

a) b) c)

2. Graf uchlarini to‘g‘ri bo‘yang.

a) b) c)

3. Grafning xromatik soni topilsin.

a) b)

4. Grafning xromatik soni topilsin.
a) b) c) d)
5. Grafning xromatik soni topilsin.

a) b) c)

6. Xromatik soni 3ga teng bo‘lgan, lekin uzunligi 3 ga teng bo‘lgan sikllarni o‘z ichiga olmagan graf qurilsin.
7. Xromatik soni 4 ga teng bo‘lgan, lekin to‘liq grafga izomorf bo‘lgan grafostini o‘z ichiga olmagan grafga misol qurib bering.
8. Graf bixromatik bo‘lgandagina, ikki ulushli bo‘lishini ko‘rsating.
9. Xromatik soni 2 ga teng bo‘lgan grafda, Gamilton sikli bo‘lishinig zaruriy sharti, turli xil ranglarga bo‘yalgan uchlar sonining teng ekanligini ko‘rsating.
10. Aytaylik graf uvhlarini [1,4], [2,5], [3, 8], [5,12], [6,12], [7,14] [13,14] yopiq intervallar tasvirlasin, qirralar esa ushbu intervallarning kesishishini tasvirlasin. Grafni rasmda tasvirlang va uning xromatik sonini toping.

11. Uchlarni nomerlanish tartibida joylashtirib, xasis algoritmni qo‘llagan holda xromatik son bahosi topilsin.

12. Talabalarning 10 ta A, B, C, D, E, F, G, H, J, I guruhidan har biri 8 xil sport musobaqalarida qatnashishi mumkin. Har bir musobaqaga qatnashish uchun quyidagicha guruhlardan talab tushdi.

Musobaqa	1	2	3	4	5	6	7	8
Qatnashuvchilar	A,B,C,D	A,C,D,E	B,D,F,G	C,F,G,H	A,H,J	H,I,J	G,H,J	E,I

Agar umumiy qatnashuvchiga ega bo‘lgan musobaqalar turli xil kunda o‘tqazilishi shart bo‘lsa, barcha musobaqalarni o‘tqazishning eng kam kuni topilsin.

13. O‘n bir talaba A, B, C, D, E, F, G, H, J, I va К larning har biri, ushbu semestrda o‘qilayotgan 6 xil kurslarning bir nechtasiga qatnashadi.

kurslar	1	2	3	4	5	6
talabalar	A,B,C,D	A,C,D,E	B,D,F,G	C,F,G,H	A,H,J	H,I,J

Agar talaba ikkita kursga ham qatnashishi aniq bo‘lsa, ular turli o‘quv juftliklarida o‘qilishi uchun tuziladigan dars jadvalidagi eng kam dars juftliklari soni topilsin.

14. Uchlarni quyidagi tartibda joylashtirgan holda, xasis algoritmdan foydalanib rasmdagi graf bo‘yalsin
a) 1, 2, …, 8;
b) 8, 7, …, 1.



Grafni 4 xil rangga to‘g‘ri bo‘yash mumkinmi?
15. Oldingi mashqni uchlarni quyidagicha tartibda joylashtirib yeching
a) uchlar darajalarini o‘sish tartibida;
b) uchlar darajalarini kamayish tartibida.
16. Aytaylik G graf to‘liq grafdan bitta qirrasini olib tashlash hisobiga hosil qilingan bo‘lsin. G grafning xromatik soni n-1 ga tengligini isbotlang.
17. to‘liq graf n ta uchli va xromatik soni n ga teng bo‘lgan yagona graf ekanligini isbotlang.
18. Aytaylik G n ta uchli, d darajali regulyar graf bo‘lsin.
a) To‘g‘ri bo‘yash amalga oshirilganda, bir xil rangga bo1yallishi mumkin bo‘lgan uchlarning maksimal soni topilsin;
b) ekanligi isbotlansin.
19. Ixtiyoriy k uchun shunday bixromatik graf mavjudki, uning uchlarini qandaydir joylashish tartibi xasis algoritmni k bo‘yashlar soniga olib kelishi isbotlansin.
20. Har doim graf uchlarining shunday joylashish tartibi mavjudki, xasis algoritmni optimal bo‘yashlar soni olib kelishi isbbotlansin.

1.