 теңдігі орындалады, сондықтан
өрнегі орындалады. Ендеше теореманың салдары бойынша φz ең үлкен ағын болып табылады. Мысал. 2-суретте өрнектелген транспорт желісінің ең үлкен ағыны анықтау керек.Әр доғада жазылған сандар осы доғаның өткізу қабілетін білдіреді. Жолдың басы v0 төбесін соңы 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 болатын ағынға әкеледі. Бұл ең үлкен ағын болады.
Негізгі әдебиет: 1[249-257]; 3[172-193]
Қосымша әдебиет : 7[50-80].
Бақылау сұрақтары:
1. Транспорт желісі дегеніміз не?
2. Транспорт желісінде қандай доға қаныққан доға деп аталады?
3. Транспорт желісінде қима деп нені айтады?
4. Қандай ағын толық деп аталады?
5. Ең үлкен ағын табудың Форд – Фалькерсон алгоритміне сипаттама беріңіз.
Практикалық сабақтардың жоспары
Достарыңызбен бөлісу: |
