Анықтама. қимасының өткізу қабілеті 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-пунктке көш.Соңы.

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

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

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