1. Kirish Daraxt va unga ekvivalent tushunchalar

Mavzu:Eng katta daraxt haqida,eng qisqa va eng uzun yo’l
Haqida tarmoqli rejalashtirish, kommunikatsiyalar turlari
Oqimi


Reja:
1.Kirish
2.Daraxt va unga ekvivalent tushunchalar
3.Eng qisqa va eng uzoq yo’l
4. Daraxtlarni Prufer usulida kodlash
5.Xulosa
6.Foydalanilgan adabiyotlar


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 oriyentirlanmagan graf o’rmon (asiklik graf) 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 bin daraxtdir.

4

5

6

3

2

1

2-misol. 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.

Daraxt tushunchasiga boshqacha ham ta’rif berish mumkin. Umuman olganda, G(m,n)- graf uchun daraxtlar haqidagi asosiy teorema, deb ataluvchi quyidagi teorema o’rinlidir

1-Teorema.Uchlari soni m va qirralar soni n bo’lgan G graf uchun quyidagi tasdiqlar ekvivalentdir:

• 
  G daraxtdir;
  

• 
  G asiklikdir va n=m-l;
  

• 
  G bog’lamlidir va n=m-l;
  

Induksion o’tish: G daraxt uchun k>2 va m=k bo’lganda, 2) tasdiq o’rinli bo’lsin deb faraz qilamiz.Endi uchlari soni m=k+L va qirralari soni n bo’lgan daraxtni qaraymiz.