1. To'plamlar, ularning berilish usullari va ular ustida amallar

28. Tekis graflar haqida Eyler formulasi.
Agar graf tekislikda geometrik ifodalanishga ega bo’lsa, u holda bunday graf tekis (yassi) graf deb ataladi. Tekislikka yotqizilgan graf tekis graf deyiladi.
Tearema (Eyler 1752): Tekis va bog’lamli G=(V,U) graf uchun m+r=2+n tenglik o’rinlidir, bu yerda r -yoqlari soni.
T e o r e m a . Agar biror graf yoki grafga gomeomorf bo‘lgan qism grafga ega bo‘lsa, u holda bu graf tekislikda yotuvchi bo‘lmaydi.
31. Graflarni bo’yash.
Graflarni bo’yash masalasi quyidagicha paydo bo’lgan: geografik kartani bo‘yash uchun ixtiyoriy 2 ta qo‘shni davlatni rangi har xil bo‘lishini ta’minlashda 4 xil rang yetadimi. Ko‘priklarsiz bog`langan tekis multigraf karta deb ataladi.
funksiya mavjud bo‘lib, unda dan k gacha raqamlardan iborat va
chegara rangi, G- esa k-rang hisoblanadi( qo‘shni chegaralar turli xil
bo‘lganda). K- rang mavjud bo‘lsa, karta k- bo‘yalgan deyiladi. 1879 yilda
britaniyalik matematik A. Keli kartalarni bo‘yash muammosini 4 ta rang gipotezasi
orqali ta`riflab berdi.
Ta’rif: Agar geometrik ikkilik graf G* uchi k- bo‘yalgan bo‘lsa, karta G
k-bo‘yalgan deyiladi.
Ta`rif. Agar bixromatik graf deyiladi, agar χ(G)=2 bo’lsa.
Teorema. Ixtiyoriy 3 ta sikldan kam bo‘lmagan yassi graf 3 xil rangda
bo‘yaladi.
To‘rt xil rang gipotezasi masalasini quyidagi uchta tasdiq yordamida hal qilinadi:
1. Ixtiyoriy yassi graf 4 xil rangda bo‘yaladi.
2. Har bir kub karta 4 ta rangda bo‘yaladi.
3. 3 xromatik indeks ixtiyoriy kub kartaga teng bo‘lishi mumkin.
Teorema. (to‘rtta bo‘yoqlar haqida teorema) Agar G planar graf bo‘lsa,
unda χ(G)≤4.
32. Grafning xromatik soni.
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.
33. Kyonig teoremasi.