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

yoylar bo‘yicha oqimlar yig‘indisi o‘pqonga insident yoylar bo‘yicha
oqimlar yig‘indisiga tengdir: ^ x sj = = p ■
(v „v ; )£{y (v,,v, )b U
1- m i s o l . 1- shaklda v0 manba va v5 o‘pqoni boigan T = (G,b)
tarmoq tasvirlangan bo‘lib, uning yoylari yoniga mos o‘tkazish
qobiliyatlari yozilgan, bunda G = (V,U) ,
^ = {v0.v„v2,v3,v4,vj},
^ = {(v0,v1),(v0,v2),(v1,v2),(v1,v3),(v2,v3),
(v2, V3 ), (v2, v4 ), (v3, v4 ), (v3, Vs ), (v4, v5 )>
Bu tarmoq uchun b0l= 7, b02 = 3 , bu = 2, bu = 5 , b2} = 2 , b2l = 4 ,
*24 = 1 ’ *31 - 5 ' *32 = 3 - bM - 2 , 635 = 2 , b4}= 2 , b45 = 4 ekanligi
shakldan ko‘rinib turibdi.
1 Masalan, agar manbalar bittadan ko‘p bo'lsa, u holda yangi (qalbaki) manba tarmoqqa kiritiladi
va grafning qalbaki manbaga mos yangi uchi uning haqiqiy manbalariga mos uchlari bilan
yoylar vositasida tutashtiriladi. 0 ‘pqonlar ko‘p bo'lganda ham shunga o'xshash ish amalga
oshiriladi.
www.ziyouz.com kutubxonasi
Tarmoqning har bir uchi uchun chiqish yarim darajalari va kirish yarim
darajalarini aniqlaymiz: p (v 0) = 10, p{ vx) - l , p (v2) = 7, p (v 3) = 12,
p (v 4) = 6 , p (v 5) = 0 , p(v0) = 0 , p(v,) = 14, p(v2) = 8, p( v3) = 1 1 ,
p (v 4) = 3, p (v 5) = 6 .
Berilgan T tarmoq orqali v0 manbadan v5 o‘pqonga 4 kattalikka ega
boMgan X 1 oqimni quyidagi sonlar to‘plami bilan ifodalash mumkin:
* 0 1 ^ 5 '^02 ^ ’ "^12 ^ ? * 1 3 ^ ’ * 2 1 ^ 5 * 2 3 ^ 5 '^ 2 4 ^ ’ * 3 1 — ^ ’
x32 = 0 , x34 = 2 , x35 = 1 , x43 = 0 , x45 = 3. Qaralayotgan X ] oqimning
miqdori = x0] + x02 = x35 + x45 = 4 . ■
Tarmoq bo‘ylab o‘tkazish mumkin boigan oqimlar orasida miqdori
eng katta (maksimal) oqimni topish amaliyot nuqtai nazaridan katta
v 5 v ahamiyatga egadir. Bunday oqimlar maksimal oqimlar deb