15-mavzu. O’rmon. Daraxtlarning xossalari. Ostov daraxti

Download 160,96 Kb.
bet	1/3
Sana	16.05.2024
Hajmi	160,96 Kb.
	#238872

1 2 3

Bog'liq
15-ma\'ruza(yangi)

^15-MAVZU. O’rmon. Daraxtlar. Daraxtlarning xossalari. Ostov daraxti.

Ta`rif. Yo`nalishga ega bo`lmagan graf daraxt deyiladi, agar u bog`lamli va sikl bo`lmasa.
Quyidagi shakllardan o`ng tomondagi graf daraxtni tashkil qiladi. Chunki ixtiyoriy nuqtasidan ikkinchisiga o`tsa bo`ladi, chap tomondagi shaklda sikl bo`lgani uchun daraxt emas.

Agar bir nechta daraxtlar o`rmon deyiladi. Sikl bo`lmaydi, bog`lamlilik bo`lishi shart emas.

How many edges does a tree with ⁿvertices has?

Recall, a connected graph with ⁿvertices has at least ⁿ^¹edges.

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.

Download 160,96 Kb.

1 2 3

Download 160,96 Kb.