Mavzu: daraxtlarda yurish, tayanch daraxtlar. Reja: Daraxt va unga ekvivalent tushunchalar. Grafning siklomatik soni tushunchasi

boruvchi ixtiyoriy /1 yo‘l shu vs va vt uchlami ajratuvchi har qanday
(R,R) kesimning hech boMmaganda bitta yoyini o‘zida saqlaydi. Shuning
uchun, agar ixtiyoriy (R,R ) kesimning barcha yoylarini tarmoqdan olib
tashlasak, u holda G orgrafda vs uchdan vf uchga boradigan birorta ham
yo‘l (va, demak, oqim ham) mavjud bo‘lmaydi.
Demak, yuqorida aytilganlami hisobga olib tarmoqdagi oqim miqdori
p(X) bilan ixtiyoriy (R,R) kesimning o‘tkazish qobiliyati b(R,R)
uzviy bog‘langan degan xulosaga kelish mumkin. Bu bog‘lanish quyidagi
teoremada o‘zining aniq ifodasini topgan.
1- teorema. T = (G,b) tarmoqdagi ixtiyoriy X oqim miqdori
p(X) shu tarmoqdagi vs manba va v( o‘pqonni ajratuvchi har qanday
(R,R) kesimning o ‘tkazish qobiliyatidan oshmaydi, ya’ni
P(X)
Isboti. T = (G,b) tarmoqdagi X oqim ta’rifidan bevosita quyidagi
tengliklar kelib chiqadi:
P(X) = Y,xsj> 0 = 5X “ IX' ’ vk 6 R •
(v„Vj)eU (v „v * )et/ (v4.v ,)e 6 '
Bu tengliklaming mos tomonlaridagi ifodalarni qo‘shib va o‘xshash
hadlarini ixchamlab,
P(X)= X х-/ “ S x>
tenglikni olamiz. 2) shartni va ^-X/,-0 ekanligini hisobga olsak,
v j £ R ,v,-€ R
oxirgi tenglikdan p(X)< У Д =b(R,R) munosabat kelib chiqadi.

FOYDALANILGAN ADABIYOTLAR RO’YXATI:

1. T o ‘rayev H.T., Azizov I., O taq u lo v S. Kom binatorika va graflar nazariyasi:
Uslubiy q o ‘llanm a. - Samarqand: Sam D U nashri. 2006. - 2 6 3 bet.
2. Алексеев В.Б., Кудрявцев В.Б., Сапоженко A.A., Яблонский С.В. и др.
М етодическая разработка по курсу “М атематическая логика и дискретная
математика” . 1980.
3. Soleev A. Ordering in Com plicated Problems. In 14-th British Combinatorical
Conference. Keele, GB, July, 1993. Abstracts, p. 96-98.
4. Гетманова А.Д. Логика: Словарь и задачник. М., «Гуманитарный
издательский центр ВЛАДО С», 1998.