Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 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-пунктке көш. Соңы. Енді сипатталған алгоритммен құрылған ағынның ең үлкен екендігін көрсетейік. А арқылы желінің белгіленбеген төбелер жиынын белгілейміз. Каталог: uploads uploads -> Сәлім меңдібаев армысың, алтын таң! Журналист жазбалары Қостанай – 2013 ж uploads -> Тақырыбы: Ғарышты игеру (аудандық семинар) uploads -> Реферат kz Қазақша рефераттар сайты Талғат Амангелдіұлы Мұсабаев Қазақстанның ұлттық ғарыш агенттігінің төрағасы. Ғарышкер, техника ғылымдарының докторы uploads -> Ғарыш әлеміне саяхат uploads -> Сабақ тақырыбы: Шерхан Мұртаза «Ай мен Айша» романы Сабақ мақсаты: ҚР «Білім туралы» uploads -> Қазақ тілі мен латын тілі кафедрасы Қазақ Әдебиеті пәні бойынша әдістемелік өҢдеу мамандығы: Фельдшер Мейірбике ісі Стамотология Курс: І семестрі: ІІ uploads -> Ф 7 –007-02 Қазақстан Республикасы Білім және ғылым министрлігі uploads -> 2011 жылдың 14 мамырында «Жалпы гигиена және экология», «Эпидемиология» кафедрасының ұйымдастыруымен және «Студенттік басқару ұйымының» ұйымдастыруымен Д. Е uploads -> Сабақтың тақырыбы Бала Мәншүк ( Мәриям Хакімжанова) Сілтеме uploads -> Ана тілі №2. Тақырыбы: Кел, балалар, оқылық Мақсаты жүктеу/скачать 21,8 Mb. Достарыңызбен бөлісу:
|