Nizomiy nomidagi toshkent davlat pedagogika universiteti tabiiy fanlar fakulteti

Daraxtlar.

Daraxt va unga ekvivalent tushunchalar. Siklga ega bo`lmagan oriyentirlanmagan 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.

1-misol. 1-shaklda bog`lamli komponentali soni beshga teng bo`lgan graf tasvirlangan bo`lib, u o`rmondir. Bu grafdagi bog`lamli komponentalarning har biri daraxtdir.

4.1-shakl.

2-misol. 2-shaklda to`rtta uchga ega bir-biriga izomorf bolmagan barcha (ular bor-yo`g`I ikkita) daraxtlarning geometik ifodalanishi tasvirlangan.

4.2-shakl.

Beshta uchga ega bir-biriga izomorf bo`lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko`rsatish qiyin emas.
Daraxt tushunchasiga boshqacha ham ta`rif berish mumkin.
Umuman olganda, G(m,n)-graf uchun daratlar xaqidagi asosiy teorema, deb ataluvchi quyidagi teorema o`rinlidir.
1-teorema. Uchlari soni m va qirralari soni n bo`lgan G graf uchun quyidagi tasdiqlar ekvivalentdir:

1. 
   G daraxtdir;
   
2. 
   G asiklikdir va n=m-1;
   
3. 
   G bog`lamlidir va n=m-1;
   
4. 
   G bog`lamlidir va undan istalgan qirrani olib tashlash amalini qo`llash natijasida bog`lamli bo`lmagan graf xosil bo`ldi, ya`ni G ning xar bir qirrasi ko`prikdir;
   
5. 
   G grafning o`zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta zanjir bilan tutashtirish amalini qo`llash natijasida faqat bir siklga ega bo`lgan graf xosil bo`ladi.
   
6. 
   G asiklik bo'lib, uning qo'shni bo'lmagan ikki uchini qirra bilan tutashtirish amalini qo'llash natijasida faqat bir siklga ega bo'lgan graf hosil bo'ladi.
   

Isboti. Teoremaning 1) tasdig`idan uning 2) tasdig`i kelib chiqishini isbotlaymiz. G graf daraxt bo`lsin. Daraxtning ta`rifiga ko`ra, u asiklik bo`lishini ta`kidlab, bo`yicha matematik induksiya usulini qo`llaymiz.
Matematik induksiya usulini ba`zasi: agar bo`lsa, u holda G daraxt faqat bitta uchdan tashkil topgan bo`ladi. Tabiiyki, agar bitta uchga ega bo`lgan grafda sikl bo`lmasa, u holda unda birorta xam qirra yo`q, ya`ni . Demak, bu holda tasdiq to`g`ridir.
Induksion o`tish: G daraxt uchun k 2 va bo`lganda, 2) tasdiq o`rinli bo`lsin deb faraz qilamiz. Endi uchlari soni va qirralari soni bo`lgan daraxtni qaraymiz. Bu daraxtning ixtiyoriy qirrasini ( ) bilan belgilab, undan bu qirrani olib tashlasak, uchdan uchgacha marshrut (aniqrog`i, zanjiri) mavjud bo`lmagan grafni xosil qilamiz, u holda G daraxtda sikl topilar edi. Bunday bo`lishi esa mumkin emas.
Hosil bo`lgan graf ikkita va bog`lamli komponentalardan iborat bo`lib, bu komponentalarning har biri daraxtdir. Yana shuni ham e`tiborga olish kerakki, va daraxtlarning har biridagi qirralar soni uning uchlari sonidan bitta kam bo`lishini ta`kidlaymiz, ya`ni graf ( )-graf bo`lsa, quyidagi tengliklar o`rinlidir: va Bu tengliklardan

bo`lishi kelib chiqadi. Demak, bo`lganda ham tenglik o`rinlidir. Bu esa, matematik induksiya usuliga ko`ra, kerkli tasdiqning isbotlanganligini anglatadi.

• 
  Grafga hayotiy misollar
  

Grafga misol qilib Misr piramidalarini, Fransiyadagi Luvr muzeyini olsak bo’ladi.