Daraxt va unga ekvivalent tushunchalar

Download 32,13 Kb.
bet	2/7
Sana	25.05.2024
Hajmi	32,13 Kb.
	#253167

1 2 3 4 5 6 7

Bog'liq
20-mavzu. O„rmon. Daraxtlarning xossalari. Daraxtlar haqidagi te-fayllar.org

2- m i s o l .

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.
¹ Orientirlangan daraxt tushunchasi ham bor.

1- m i s o l . 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.

shakl

2- m i s o l . 2- shaklda to„rtta uchga ega bir-biriga izomorf bo„lmagan barcha (ular bor-yog„i ikkita) daraxtlarning geometrik ifodalanishi
tasvirlangan.
Beshta uchga ega bir-biriga izomorf bo„lmagan barcha

daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko„rsatish qiyin emas.

shakl

Daraxt tushunchasiga boshqacha ham ta‟rif berish mumkin. Umuman

^olganda,G ⁽^m^,ⁿ^{) - graf uchun}^{daraxtlar haqidagi asosiy teorema}^{deb ataluvchi}
quyidagi teorema o„rinlidir.

Misol. Unda barcha qirralarning ildizdan yo`nalishi bor.

Misol.

1- t e o r e m a . Uchlari soni m va qirralari soni n bo‘lgan G graf uchun quyidagi tasdiqlar ekvivalentdir:

G ^daraxtdir;

G ^{asiklikdir va n}^^m^1^;

G bog‘lamlidir va n  m 1;

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;
G grafninng o‘zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutahtiriladi;
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.

Isbot . 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, m bo„yicha matematik induksiya usulini qo„llaymiz.
^{Matematik induksiya usulining bazasi: agar}m  1 ^{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 ham qirra yo„q, ya‟ni holda tasdiq to„g„ridir.

n  0 ^{. Demak, bu}

Download 32,13 Kb.

1 2 3 4 5 6 7

Download 32,13 Kb.