1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
Желiлердегi ағындар: Форд-Фалькерсоннын максималды ағын және минималды киык туралы теоремасы
жүктеу/скачать 336,61 Kb.
|
| 2.3Желiлердегi ағындар: Форд-Фалькерсоннын максималды ағын және минималды киык туралы теоремасы
Форд-Фулкерсон теоремасы Менгер теоремасымен тығыз байланысты графиктік максималды ағын теоремасы болып табылады. Ол былай естіледі: жол графигіндегі максималды ағынның мәні оның минималды кесіндісінің өткізу қабілетінің мәніне тең. Жеткіліктілік: t және s шыңдары арасындағы кез келген ағын кез келген қиманың мәнінен аз немесе оған тең. Біраз ағын және кейбір бөлім берілсін. Бұл ағынның мәні t шыңынан s-ке дейінгі барлық мүмкін жолдар бойынша тасымалданатын «жүк» мәндерінің қосындысы болып табылады. Әрбір осындай жолдың берілген қимамен ортақ жиегі болуы керек. Секцияның әрбір жиегі үшін «жүкті» оның жүк көтергіштігінен артық беру мүмкін болмағандықтан, барлық жүктердің қосындысы осы бөліктің шеттерінің барлық жүк көтергіштіктерінің қосындысынан аз немесе оған тең. Бекіту дәлелденді. Бұдан шығатыны, кез келген ағын минималды қиманың мәнінен кем немесе оған тең, демек максималды ағын минималды қиманың мәнінен кем немесе оған тең. Графиктегі максималды ағынды табудың Форд-Фулкерсон алгоритмі осы теоремаға негізделген, ол да осы теореманың қажеттілігінің дәлелі, яғни конструктивті. Максималды ағын — өзен тасығанда пайда болатын су көлемінің табиғи құбылысы. Кейде бұған қатысты: "Өте көп су шығыны" деген шартты аталым қолданылады. Оның су тасқыны кезіндегі көлемін есептеуде көктемгі қар, күзгі мұздың еруінен, қатты нөсер жауыннан пайда болатын суға сәйкес жүргізілетін мелиоративтік жүйенің құрылыстарын жобалағанда және оны пайдалану кезіндегі су тасқынының деңгейі мен негізгі көрсеткіштерін міндетті түрде есепке алу өте қажет. Осы көрсеткіштерді ескере отырып, гидротехникалық құрылыстардың негізгі көрсеткіштері мен өлшемдерін анықтайды. Бүтін сан туралы Теорема: Бүтін сан — натурал сандардың айырымы түрінде өрнектеуге болатын сан. Натурал сан, теріс натурал сан, немесе нөл бүтін сан болып есептеледі. Барлық бүтін сандар жиыны 2 болып белгіленген (бұл немісше "zahl — сан" деген сөзінің алғашқы әрпі). Желі ағынының есептері графиктер теориясындағы есептердің кең тараған класы болып табылады. Ағындар көптеген жүйелерге қатысады, мысалы, автомобиль жолдары жүйелеріндегі көлік ағыны, басқару жүйелеріндегі ақпарат ағыны, сумен жабдықтау жүйелеріндегі су ағыны, қаржы жүйелеріндегі ақша ағыны және т.б. бейресми сипаттама Өңдеу Біз барлық ағындарды қалпына келтіреміз. Қалдық желі бастапқыда бастапқы желімен сәйкес келеді. Қалдық желіде көзден раковинаға дейінгі кез келген жолды табамыз. Ондай жол болмаса, тоқтаймыз. Біз табылған жол арқылы (ол өсетін жол немесе өсу тізбегі деп аталады) максималды мүмкін ағынды жібереміз: Қалдық желіде табылған жолда біз ең аз өткізу қабілеті бар жиекті іздейміз в мин c_{\min}. Табылған жолдың әрбір жиегі үшін ағынды көбейтеміз в мин c_{\min}, ал қарама-қарсы бағытта біз оны азайтамыз в мин c_{\min}. Біз қалдық желіні өзгертеміз. Табылған жолдағы барлық жиектер үшін, сондай-ақ оларға қарама-қарсы (антипараллельді) жиектер үшін жаңа сыйымдылықты есептейміз. Егер ол нөл емес болса, қалдық желіге жиекті қосамыз, ал егер ол нөлге айналса, біз оны өшіреміз. Біз 2-қадамға ораламыз. Алгоритм 2-қадамда нақты қай жолды іздейтінімізді немесе оны қалай жасайтынымызды көрсетпегені маңызды. Осы себепті, алгоритм тек бүтін өткізу қабілеттілігі үшін жинақталатынына кепілдік беріледі, бірақ олар үшін де үлкен өткізу қабілеттілігі үшін ол өте ұзақ уақыт жұмыс істей алады. Егер қуаттар нақты болса, алгоритм оңтайлы шешімге жақындамай-ақ шексіз жұмыс істей алады (төмендегі мысалды қараңыз). Егер сіз қандай да бір жолды емес, ең қысқа жолды іздесеңіз, сіз Эдмондс-Карп алгоритмін немесе Dinits алгоритмін аласыз. Бұл алгоритмдер уақыт бойынша кез келген нақты салмақтар үшін жинақталады. Әрбір қадамда алгоритм бар ағынға кеңейтетін жол ағынын қосады. Егер барлық жиектердің сыйымдылығы бүтін сандар болса, барлық жиектер арқылы өтетін ағындар әрқашан бүтін сандар болатынын индукция арқылы дәлелдеу оңай. Сондықтан, әрбір қадамда алгоритм ағынды кем дегенде біреуге арттырады, сондықтан ол ең көп жиналады О ( | f | ) {\displaystyle O(|f|)} қадамдар, мұндағы f - графиктегі максималды ағын. Әр қадамды уақытында аяқтай алады О ( | Е | ) {\displaystyle O(|E|)}, мұнда | Е | {\displaystyle |E|} - графиктің жиектерінің саны, онда алгоритмнің жалпы жұмыс уақыты шектелген. О ( | Е | макс | f | ) {\ Displaystyle O(|E|\max |f|)}. Егер шеттердің ең болмағанда біреуінің сыйымдылығы иррационал сан болса, онда алгоритм тіпті дұрыс шешімге міндетті түрде жақындамай-ақ шексіз жұмыс істей алады. Төменде мысал келтірілген. Есеп: 1)s - бастапқы нүкте, t - шөгу нүктесі және әр жиектегі санның мағынасы - жиектің ағып кетуіне мүмкіндік беретін максималды ағын. Жиекті құбыр ретінде қарастыруға болады, 0/3 құбырдың секундына максималды 3 бірлік ағынды өткізе алатынын білдіреді, ал 0 ағымдағы ағынды білдіреді. Максималды ағын мәселесі мынада: s нүктесінен t нүктесіне дейін максималды рұқсат етілген ағын қандай? 2) Біз Renyou Village (Е түйіні) асинхронды ауылға кітаптар партиясын тасымалдауды қалайды деп болжаймыз (F раковина түйіні) және Renyou Village-де шексіз кітаптар бар (максималды ағын алгоритмінің сыйымдылық шартын қанағаттандыру үшін). Ренью ауылы мен Асинхронды ауыл арасында автомобиль, теміржол және әуе сияқты әртүрлі көлік түрлері бар, бірақ әр көлік түрінің қозғалыс шектеулері бар және бірнеше көлік түрлерінің тасымалдау жылдамдығы бірдей. Осы жайларға сүйене отырып, F раковина түйіні жылдамдықты есептемей-ақ қанша кітапты қабылдай алатынын анықтауымыз керек. 3) Құн мен сыйымдылықтың желілік диаграммасын (bij, cij) ескере отырып, мұнда bij құнын және cij сыйымдылықты білдіреді, желінің ең аз құны мен максималды ағынын табуға тырысыңыз. 4) Ондағы максималды ағынды табыңыз (жақшада көрсетілген). есептеу нүктесі 1. g - 7:8 = g - C (S1, V1) - 7 - 8 (g - C) ( , V1)) - 1 2 3 4 Вт 1 1 1 < 0; 2. g-13, ~=g-C(Sl, ) a 13 a Z a 11 5)Автомобиль жолдары жүйесінде көлік ағыны, басқару жүйесінде ақпарат ағыны, сумен жабдықтау жүйесінде су ағыны, қаржы жүйесінде ақша ағыны және т.б. Тасымалдау схемасын жобалаудың мысалын қарастырайық. Төмендегі сурет өнімнің шығу тегі Vs мен сату орнын Vt байланыстыратын көлік желісі.Әр доға екі нүкте арасындағы тасымалдау сызығын білдіреді, ал доғаның жанындағы сан осы тасымалдау сызығының максималды өткізу қабілетін білдіреді. Енді Vs-ден Vt-ге дейін тасымалданатын өнімдердің санын барынша арттыратын тасымалдау схемасын әзірлеу қажет. 6) (u, v) ток ағыны 3/4 деп есептесек, онда c(u, v)=4, f(u, v)=3, содан кейін r(u, v)=1.ең қысқа жол табу жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|