O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali

Graf, uch, qirra, daraxt, о'rmon, asiklik graf, marshrut, sikl,

zanjir, oddiy zanjir, ко'prik, grafning sinch daraxti, grafning

sinch o'rmoni, grafning siklomatik soni.

Daraxt va unga ekvivalent tushunchalar. Siklga ega bo'lmagan oriyentirlanmagan bog'lamli

graf daraxt, deb ataladi1. Ta'rifga ko'ra, daraxt sirtmoqlar va karrali qirralarga ega emas.

Siklga ega bo'lmagan oriyentirlanmagan graf о'rmon (asiklik graf), deb ataladi.

1-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 birbiriga 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)-gvaf uchun daraxtlar haqidagi asosiy teorema, deb

ataluvchi quyidagi teorema o'rinlidir.

1-teorema. Uchlari soni m va qirralari soni n bo 'Igan 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 vam=k bo'lganda, 2) tasdiq o'rinli