Дәріс конспектісі

Анықтама. Төменде аталған шарттар: а) ілгек жоқ; 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) j(e)£c(e);

c)

5-сурет

Анықтама. ағын шамасы деп аталады және φz болып белгіленеді.

Анықтама. е доғасы үшін φ(е)=с(е) болса,ол толыққан доға деп, ал әрбір жолдың басынан бастап ағына дейін ең болмаса бір қаныққан доғасы болса jz ағыны толық деп аталады.

Анықтама. Айталық, v₀ÏA, ал zÎA шарты орындалатындай транспорт желісі төбелерінің ішкі жиыны AÌV болсын. А-ға енбейтін төбелерді А-ның төбелерімен қосатын доғалар жиыны G(V, E) желісінің Т қимасы деп аталады. Мысалы, 1-суретте көрсетілген желідегі төбелердің A={v1,v2,v4, z } ішкі жиыннан бөлек, = {(v₀, v₁), (v₀, v₂),(v₃, z)} доғалар жиыны қима болады.

Анықтама. қимасының өткізу қабілеті c( ) деп қимаға кіретін доғалардың өткізу қабілеттерінің қосындыларын айтады, деп белгілейді.

Теорема. G(V, E) транспорт желісіндегі v₀ÏA, zÎAорындалатындай төбелердің ішкі жиыны AÌV арқылы анықталатын G(V, E) транспорт желісінен алынған φ ағыны мен кез келген Т қимасы үшін jz £ c( ), орындалса, яғни желідегі кез келген ағынның шамасы (оның ішінде ең үлкені де) кез келген қиманың өткізу қабілетінен артық емес (оның ішінде ең кішісі де).

Салдар. Егер кез-келген φ ағыны мен қимасы үшін jz= с( ), орындалса, онда φ ағыны–ең үлкен, ал қимасының өткізу қабілеті ең аз болады.

Транспорт желісінің ең үлкен ағынын анықтайтын Форд-Фалкерсон алгоритмін қарастырайық. Ол алгоритм бойынша ағын біртіндеп ең үлкен мән қабылдағанша үлкейтіле береді.

AL алгоритмі. (транспорт желісіндегі ең үлкен ағынды табу ға арналған).

Басы. Транспорт желісі V төбелер жиыны, доғалар жиыны E және желінің басыv₀ÎV,соңы zÎV арқылы беріледі. Доғалардың өткізу қабілеті c(е), еÎЕ беріледі.

1. G(V,E) желісінің v₀ мен zтөбелерінен басқаларын еркін түрде нөмірлейміз.

2. Барлық eÎE үшін φ(e)=0 деп алып кез-келген ағын тұрғызамыз.

3. Транспорт желісінің басталу төбесі v₀ мен соңғы z төбелерін қосатын барлық жолдарды қарап шығу. Егер φ ағыны толық болса 4 пунктке көш. Болмаса v₀ төбесін z қосатын барлық доғалары қаныққан емес μ жолын қарастыру керек те мына формула бойынша

φ' ағынын құрыңыз. Мұндағы .

3–пунктті қайталаңыз.

4. Желінің төбелеріне бүтін мәнді таңбалар және желі доғаларын "+" және "-" таңбаларымен мына ережелер бойынша белгілейміз:

а) v₀ басталу төбесін е0;

в) Егер vi төбесі таңбаланса, ал v әлі таңбаланбаса,онда егер v -ға vi төбесінен(j(vi,v)< c((vi,v)), қанықпаған доға келсе, v төбесіне i таңбасы ,ал (vi,v) доғасына "+" таңбасы беріледі; немесе v төбесінен нөлдік емес ағынмен vi төбесіне (j((v, vi))>0) баратын доға бар болса, (v, vi) доғасы "-" белгісімен таңбаланады. Қалған белгіленбеген доғалар мен төбелерге таңба берілмейді;

с) 4в пунктегі сипатталған процесс жаңа таңбаланған доға мен төбенің пайда болуы тоқталғанға дейін қайталанады. Осы процестің нәтижесінде z таңбаланбаса, онда құрылған ағын ең үлкен болғаны одан соңына көшу керек, керісінше болса 5 пунктке көшіңіз.

5. Әрқайсысы келесі төбенің нөмірімен таңбаланған төбелердің және жиынынан алынған төбелерді қосатын μ (не обязательно маршрут болуы міндетті емес) доғалар тізбегін қарастырамыз.Төменде көрсетілгендей жаңа ағын құрасыз.

4-пунктке көш. Соңы.

Енді сипатталған алгоритммен құрылған ағынның ең үлкен екендігін көрсетейік. А арқылы желінің белгіленбеген төбелер жиынын белгілейміз. болғандықтан А жиыны желісінің қимасын анықтайды. Әрбір доғасы таңбаланған төбені таңбаланбаған төбесімен қосады. V төбесі шартында таңбаланбай қалуы мүмкін. Екінші жағынанА( ) шығатын әрбір доғада теңдігі орындалады, сондықтан

өрнегі орындалады. Ендеше теореманың салдары бойынша φ_z ең үлкен ағын болып табылады. Мысал. 2-суретте өрнектелген транспорт желісінің ең үлкен ағыны анықтау керек.Әр доғада жазылған сандар осы доғаның өткізу қабілетін білдіреді. Жолдың басы v₀ төбесін соңы z-пен қосатын барлық жолды тізіп шығайық: m1=(v0, v1, v4, z); m2=(v0, v1, v2, v4, z); m3=(v0, v2, v3, z); m4=(v0, v1, v3, z); m5=(v0, v1, v2, v3, z); m6=(v0, v2, v4, z). Желідегі алғашқы ағынды 0 деп алып, оны әр жолдың ең болмаса қаныққан бір доғасы болғанға дейін біртіндеп көбейтеміз. Ол үшін әр жолдан доғалардың өткізу қабілеті мен осы доғалардағы ағынның ең кіші айырымын анықтаймыз және бүкіл жолдағы ағынды осы шамаға арттырамыз. Бұл процесс 6а, 6b, 6с, 6d суреттерде көрсетілген,доғаларда әрқайсысының өткізу қабілетімен бірге жақша ішінде осы доғаның ағыны көрсетілген. 6d суреттегі құрылған ағын толық және ол j_z = 9 (6а –6d) суреттерде қаныққан доғалар жуан сызықтармен бейнеленіп тұр).

Құрылған ағынның ең үлкен болу шартын тексереміз.Ол үшін доғалар мен төбелерді таңбалаймыз, нәтижесінде z төбесі таңбаланған болып шығады( 6d-сурет). Бұл 6d-суреттегі ағынның ең үлкен емес екендігін көрсетеді."+" -белгісімен таңбаланған ағын шамасын көбейту, "-"- белгісімен таңбаланған ағын шамасын азайту 6e- суретте көрсетілгендей шамасы j_z = 11 болатын ағынға әкеледі. Бұл ең үлкен ағын болады.

Негізгі әдебиет: 1[249-257]; 3[172-193]

Қосымша әдебиет : 7[50-80].

Бақылау сұрақтары:

1. Транспорт желісі дегеніміз не?

2. Транспорт желісінде қандай доға қаныққан доға деп аталады?

3. Транспорт желісінде қима деп нені айтады?

4. Қандай ағын толық деп аталады?

5. Ең үлкен ағын табудың Форд – Фалькерсон алгоритміне сипаттама беріңіз.