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

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


35. O'rmon. Daraxtlar.
Ta`rif. Yo`nalishga ega bo`lmagan graf daraxt deyiladi, agar u bog`lamli va sikl bo`lmasa.
Alfred Joyce Kilmer (December 6, 1886 – July 30, 1918)graflarda daraxtlarni tuzilishi haqida aytib o`tgan.
Ta’rif: Agar bir nechta daraxtlar o`rmon deyiladi. Sikl bo`lmaydi, bog`lamlilik bo`lishi shart emas.
Daraxt va unga ekvivalent tushunchalar. Siklga ega bo’lmagan orientirlanmagan bog’lamli graf daraxt deb ataladi. Ta’rifga ko’ra daraxt
sirtmoqlar va karrali qirralarga ega emas. Siklga ega bo„lmagan orientirlanmagan
graf o‘rmon (asiklik graf) deb ataladi.
T e o r e m a . Uchlari soni va qirralari soni bo‘lgan graf uchun
quyidagi tasdiqlar ekvivalentdir:

1. 
   daraxtdir.
   
2. 
   asiklikdir va
   
3. 
   bog’lamlidir va
   
4. 
   G bog‘lamlidir va undan istalgan qirrani olib tashlash amalini qo‘llash natijasida bog‘lamli bo‘lmagan graf hosil bo‘ladi, ya’ni G ning har bir qirrasi ko‘prikdir;
   
5. 
   G grafninng o‘zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutahtiriladi;
   
6. 
   G asiklik bo‘lib, uning qo‘shni bo‘lmagan ikkita uchini qirra bilan tutashtirish amalini qo‘llash natijasida faqat bitta siklga ega bo‘lgan graf hosil bo‘ladi.
   

36. Daraxtlarning xossalari.

7. 
   
   
8. 
   
   

37. Daraxtlar haqidagi teoremalar.

Alfred Joyce Kilmer (December 6, 1886 – July 30, 1918)graflarda daraxtlarni tuzilishi haqida aytib o`tgan.
Ta`rif. Yo`nalishga ega bo`lmagan graf daraxt deyiladi, agar u bog`lamli va sikl bo`lmasa.