Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 08. 329-2006, Қр мжмбс 08. 33-2006 Мемлекеттік стандартына сәйкес құрылған
жүктеу/скачать 21,8 Mb.
|
Теорема. G(V, E) транспорт желісіндегі v0A, zAорындалатындай төбелердің ішкі жиыны AV арқылы анықталатын G(V, E) транспорт желісінен алынған φ ағыны мен кез келген Т қимасы үшін z c( ), орындалса, яғни желідегі кез келген ағынның шамасы (оның ішінде ең үлкені де) кез келген қиманың өткізу қабілетінен артық емес (оның ішінде ең кішісі де).
Салдар. Егер кез-келген φ ағыны мен қимасы үшін z= с(), орындалса, онда φ ағыны–ең үлкен, ал қимасының өткізу қабілеті ең аз болады.
Транспорт желісінің ең үлкен ағынын анықтайтын Форд-Фалкерсон алгоритмін қарастырайық. Ол алгоритм бойынша ағын біртіндеп ең үлкен мән қабылдағанша үлкейтіле береді. AL алгоритмі. (транспорт желісіндегі ең үлкен ағынды табу ға арналған). Басы. Транспорт желісі V төбелер жиыны, доғалар жиыны E және желінің басы v0V, соңы zV арқылы беріледі. Доғалардың өткізу қабілеті c(е), еЕ беріледі. 1. G(V,E) желісінің v0 мен zтөбелерінен басқаларын еркін түрде нөмірлейміз. 2. Барлық eE үшін φ(e)=0 деп алып кез-келген ағын тұрғызамыз. 3. Транспорт желісінің басталу төбесі v0 мен соңғы z төбелерін қосатын барлық жолдарды қарап шығу. Егер φ ағыны толық болса 4 пунктке көш. Болмаса v0 төбесін z қосатын барлық доғалары қаныққан емес μ жолын қарастыру керек те мына формула бойынша  φ' ағынын құрыңыз. Мұндағы  .
3–пунктті қайталаңыз. 4. Желінің төбелеріне бүтін мәнді таңбалар және желі доғаларын "+" және "-" таңбаларымен мына ережелер бойынша белгілейміз: а) v0 басталу төбесін е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. Достарыңызбен бөлісу:
|