25-Graflarni bo‘yash

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.