Кіріспе
Оптималдастыру теориясындағы түсінік. Компьютерлік ғылым және оптимизация теориясында максималды ағын-минималды кесім теоремасы бойынша, ағын желісінде бастапқы нүктеден түнгі нүктеге өтетін ағынның ең көп мөлшері, минималды кесімдегі қабырғалардың жалпы салмағына тең, яғни, егер алынып тасталса, бастапқы нүктені түнгі нүктеден бөліп тастайтын қабырғалардың ең кіші жалпы салмағы. Бұл сызықтық бағдарламалардың дуалдық теоремасының ерекше жағдайы және Менгер теоремасы мен Кёниг-Эгервари теоремасын шығару үшін қолданылуы мүмкін.
In computer science and optimization theory, the max flow min cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i. e., the smallest total weight of the edges which if removed would disconnect the source from the sink. This is a special case of the duality theorem for linear programs and can be used to derive Menger's theorem and the Kőnig–Egerváry theorem.
Анықтамалар мен мәлімдеме
Теорема екі шаманы теңестіреді: желі арқылы максималды ағын және желідегі кесіндінің минималды сыйымдылығы. Теореманы тұжырымдау үшін, ең алдымен осы екі ұғым анықталуы тиіс.
Негізгі теорема
Жоғарыда көрсетілген жағдайда, желі арқылы кез келген ағынның мәні кез келген s-t кесудің сыйымдылығынан кем немесе тең екенін, сондай-ақ максималды мәнді ағын мен минималды сыйымдылықты кесудің бар екенін дәлелдеуге болады. Басты теорема желідегі максималды ағынның мәнін ең төменгі кесу сыйымдылығымен байланыстырады. Максималды ағын – минималды кесу теоремасы. s-t ағынының максималды мәні барлық s-t кесулердегі минималды сыйымдылыққа тең.
Мысал
Оң жақтағы суретте желідегі ағын көрсетілген. Әрбір жебедегі f/c түріндегі сандық белгілер ағынның (f) және жебенің сыйымдылығын (c) көрсетеді. Көзден шығатын ағындардың қосындысы бес (2+3=5) тең, ал қабылдағышқа келіп түсетін ағындардың қосындысы да бес (2+3=5) тең, бұл ағынның мәні 5 екенін көрсетеді. 5 мәнді s-t кесуі S={s,p} және T={o, q, r, t} жиындары арқылы берілген. Бұл кесуден өтетін қабырғалардың сыйымдылығы 3 және 2-ге тең, осылайша кесудің сыйымдылығы 3+2=5 болады. (o-дан p-ге бағытталған жебе қарастырылмайды, себебі ол T жиынынан S жиынына қарай бағытталған.) Ағынның мәні кесудің сыйымдылығына тең, яғни ағын максималды ағын және кесу минималды кесу екенін көрсетеді. S жиынынан T жиынына жалғасқан екі жебе арқылы ағын толық сыйымдылықпен жүзеге асырылады; бұл әрқашан осылай болады: минималды кесу жүйенің "тар шеңберінің" орнын көрсетеді.
The value of the flow is equal to the capacity of the cut, showing that the flow is a maximal flow and the cut is a minimal cut. Note that the flow through each of the two arrows that connect S to T is at full capacity; this is always the case: a minimal cut represents a 'bottleneck' of the system.
Седербаумның максималды ағындылық теоремасы
Максималды ағындылық мәселесін сызықтық емес кедергі элементтерінен құралған желі арқылы электр тогының максимизациялануы ретінде қоюға болады. Бұл тұжырымдамада, кіріс кернеуі Vin нөлге жақындағанда электр желісінің кіріс терминалдары арасындағы Iin тогының лимиті, ең төмен салмақты кесу жиынтығының салмағына тең болады.
Менгер теоремасы
Бағытталмаған жиектік аралық жолдар мәселесінде бізге бағытталмаған граф және s және t екі төбе беріледі, сондай-ақ G графындағы s мен t арасындағы жиектік аралық жолдардың максималды санын табу қажет.
Менгер теоремасы бойынша, бағытталмаған графтағы s мен t арасындағы жиектік аралық жолдардың максималды саны, s-t кесінді жиынындағы ең аз жиектер санына тең болады.