Қазақстан республикасының білім және ғылым министірлігі

жүктеу 21,8 Mb.

бет	112/214
Дата	09.01.2018
өлшемі	21,8 Mb.
	#7265
түрі	Мазмұндама

1 ... 108 109 110 111 112 113 114 115 ... 214

Теорема. G(V, E) транспорт желісіндегі v₀A, zAорындалатындай төбелердің ішкі жиыны AV арқылы анықталатын G(V, E) транспорт желісінен алынған φ ағыны мен кез келген Т қимасы үшін z  c(

), орындалса, яғни желідегі кез келген ағынның шамасы (оның ішінде ең үлкені де) кез келген қиманың өткізу қабілетінен артық емес (оның ішінде ең кішісі де).

Салдар. Егер кез-келген φ ағыны мен

қимасы үшін z= с(

), орындалса, онда φ ағыны–ең үлкен, ал

қимасының өткізу қабілеті ең аз болады.

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

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 төбесінен((vi,v) c((vi,v)), қанықпаған доға келсе, v төбесіне i таңбасы ,ал (vi,v) доғасына "+" таңбасы беріледі; немесе v төбесінен нөлдік емес ағынмен vi төбесіне (((v, vi))>0) баратын доға бар болса, (v, vi) доғасы "-" белгісімен таңбаланады. Қалған белгіленбеген доғалар мен төбелерге таңба берілмейді;

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

5. Әрқайсысы келесі төбенің нөмірімен таңбаланған

төбелердің және

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

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

Енді сипатталған алгоритммен құрылған ағынның ең үлкен екендігін көрсетейік. А арқылы желінің белгіленбеген төбелер жиынын белгілейміз.

жүктеу 21,8 Mb.

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

1 ... 108 109 110 111 112 113 114 115 ... 214