Дәріс тақырыбы: Графтар теориясы (5 сағат) Негізгі сұрақтар

жүктеу 0,75 Mb.

бет	20/23
Дата	03.02.2022
өлшемі	0,75 Mb.
	#35463

1 ... 15 16 17 18 19 20 21 22 23

лекция

Транспорттық желілер.

Анықтама. Айталық G(V,E) байланысты бағытталмаған граф. G графының барлық төбелері арқылы өтетін, басталуы мен аяқталуы әр түрлі төбелерде болатын қарапайым цикл Гамильтон циклы деп аталады.Графтарда Гамильтон циклдары мен шынжырлары бар болудың жеткілікті шартын келтірейік. Айталық дәр. v–v V төбесінің дәрежесі болсын.

Теорема. Егер G (V, E), мұндағы |V|=n графында кез келген төбелер v_i және v_j жұбтары үшіндәр.v_i+дәр.v_j≥n-1, орындалса, графта гамильтон шынжыры бар, ал егер дәр.v_i+дәр.v_j≥n немесе дәр.v_i≥n/2 графта Гамильтон циклы бар.

Транспорттық желілер.

Анықтама. Төменде аталған шарттар: а) ілгек жоқ; b) шығу төбесі (бірде бір доға кірмейтін, тек шығатын ғана төбелері бар) бар болса; с) кіру төбесі (бірде бір доға шықпайтын, тек кіру төбелері ғана бар) бар болса; d) доғалардың Е жиынындағы әр доғада мәні өткізу қабілеті деп аталатын теріс емес бүтін мәнді с(е) функциясы анықталған болса; бағытталған, байланысты G(E, V) графы транспорт желісі деп аталады.

Транспорт желісінің шығу,кіру деп аталатын төбелерден басқа төбелері аралық төбелер деп аталады. 1-суретте v₀-басталу төбесі, z-аяқталу төбесі, v₁, v₂, v₃, v₄-аралық төбелер, ал әр доғада өткізу қабілеті көрсетілген.

Анықтама. Айталық, желінің v V төбесінен қосылатын, а -төбесінен шығатын доғалар жиыны болсын. G(V,E) желісінің Е доғалар жиынында берілген бүтін мәнді теріс емес φ(е) функциясы а), b), c) шарттарын қанағаттандырса ағын деп аталады. φ(е) функциясының мәнін х төбесінен у төбесіне баратын v(x,y) доғасымен уақыт бірлігінде өтетеін заттың саны деп қарауға болады. Бұл сан доғаның өткізу қабілетінен аспайды. Желінің басталатын және аяқталатын төбелерінен басқа төбелерде келетін заттардың саны одан шығатын заттарға тең болатындықтан еш жерде олар жиналып қалмайды

a) ,

vv₀, vz;

b) (e)c(e);

5-сурет

жүктеу 0,75 Mb.

Достарыңызбен бөлісу:

1 ... 15 16 17 18 19 20 21 22 23