अधिकतम-प्रवाह न्यूनतम-घटाव प्रमेय

कंप्यूटर विज्ञान और ऑप्टिमाइज़ेशन (गणित) में, अधिकतम-प्रवाह न्यूनतम-कट प्रमेय बताता है कि एक प्रवाह नेटवर्क में, ग्राफ़ सिद्धांत की शब्दावली से गुजरने वाले प्रवाह की अधिकतम मात्रा #दिशा|

यह रैखिक कार्यक्रमों के लिए दोहरी समस्या का एक विशेष मामला है और इसका उपयोग मेन्जर के प्रमेय और कोनिग के प्रमेय (ग्राफ सिद्धांत) | कोनिग-एगर्वरी प्रमेय को प्राप्त करने के लिए किया जा सकता है।

परिभाषाएँ और कथन

प्रमेय दो मात्राओं को बराबर करता है: एक नेटवर्क के माध्यम से अधिकतम प्रवाह, और नेटवर्क में कटौती की न्यूनतम क्षमता। प्रमेय बताने के लिए, इनमें से प्रत्येक धारणा को पहले परिभाषित किया जाना चाहिए।

नेटवर्क

एक नेटवर्क से मिलकर बनता है

• एक परिमित निर्देशित ग्राफ N = (V, E), जहां V शीर्षों के परिमित समुच्चय को दर्शाता है और E ⊆ V×V निर्देशित किनारों का समूह है;
• एक स्रोत s ∈ V और एक सिंक t ∈ V;
• एक क्षमता फ़ंक्शन, जो एक मैपिंग है $c:E\to \mathbb {R} ^{+}$ द्वारा चिह्नित c_uv या c(u, v) के लिए (u,v) ∈ E. यह प्रवाह की अधिकतम मात्रा का प्रतिनिधित्व करता है जो एक किनारे से गुजर सकता है।

प्रवाह

किसी नेटवर्क के माध्यम से प्रवाह एक मानचित्रण है $f:E\to \mathbb {R} ^{+}$ द्वारा चिह्नित $f_{uv}$ या $f(u,v)$, निम्नलिखित दो बाधाओं के अधीन:

1. क्षमता की कमी: हर किनारे के लिए $(u,v)\in E$, $f_{uv}\leq c_{uv}.$
2. प्रवाह का संरक्षण: प्रत्येक शीर्ष के लिए $v$ के अलावा $s$ और $t$ (यानी स्रोत और सिंक, क्रमशः), निम्नलिखित समानता रखती है:
   $\sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}.$

प्रत्येक किनारे की दिशा का अनुसरण करते हुए, प्रवाह को नेटवर्क के माध्यम से तरल पदार्थ के भौतिक प्रवाह के रूप में देखा जा सकता है। क्षमता बाधा तब कहती है कि प्रति इकाई समय में प्रत्येक किनारे से बहने वाली मात्रा किनारे की अधिकतम क्षमता से कम या उसके बराबर है, और संरक्षण बाधा कहती है कि प्रत्येक शीर्ष में बहने वाली मात्रा स्रोत और सिंक शीर्ष के अलावा, प्रत्येक शीर्ष से बहने वाली मात्रा के बराबर होती है।

प्रवाह का मान परिभाषित किया गया है

$|f|=\sum \nolimits _{\{v:(s,v)\in E\}}f_{sv}=\sum \nolimits _{\{v:(v,t)\in E\}}f_{vt},$ जहां ऊपर बताया गया है $s$ स्रोत है और $t$ नेटवर्क का सिंक है. द्रव सादृश्य में, यह स्रोत पर नेटवर्क में प्रवेश करने वाले द्रव की मात्रा को दर्शाता है। प्रवाह के लिए संरक्षण सिद्धांत के कारण, यह सिंक पर नेटवर्क छोड़ने वाले प्रवाह की मात्रा के समान है।

अधिकतम प्रवाह समस्या किसी दिए गए नेटवर्क पर सबसे बड़े प्रवाह की मांग करती है। <ब्लॉककोट> अधिकतम प्रवाह समस्या|अधिकतम प्रवाह समस्या। अधिकतम $|f|$, अर्थात्, जितना संभव हो सके उतने अधिक प्रवाह को रूट करना $s$ को $t$. </ब्लॉककोट>

कटौती

अधिकतम-प्रवाह न्यूनतम-कट प्रमेय का दूसरा भाग नेटवर्क के एक अलग पहलू को संदर्भित करता है: कटौती का संग्रह। एक एस-टी कट C = (S, T) का एक विभाजन है V ऐसा है कि s ∈ S और t ∈ T. अर्थात्, एस-टी कट नेटवर्क के शीर्षों को दो भागों में विभाजित करना है, जिसमें एक भाग में स्रोत और दूसरे में सिंक होता है। 'कट-सेट' $X_{C}$ एक कट का C किनारों का समूह है जो कट के स्रोत भाग को सिंक भाग से जोड़ता है:

$X_{C}:=\{(u,v)\in E\ :\ u\in S,v\in T\}=(S\times T)\cap E.$

इस प्रकार, यदि सभी किनारे कट-सेट में हैं C हटा दिए जाते हैं, तो कोई सकारात्मक प्रवाह संभव नहीं है, क्योंकि परिणामी ग्राफ़ में स्रोत से सिंक तक कोई पथ नहीं है।

एसटी कट की क्षमता इसके कट-सेट में किनारों की क्षमता का योग है,

$c(S,T)=\sum \nolimits _{(u,v)\in X_{C}}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},$

कहाँ $d_{ij}=1$ अगर $i\in S$ और $j\in T$, $0$ अन्यथा।

एक ग्राफ़ में आम तौर पर कई कट होते हैं, लेकिन छोटे वजन वाले कट अक्सर ढूंढना अधिक कठिन होते हैं।

न्यूनतम एस-टी कट समस्या। छोटा करना c(S, T), अर्थात निर्धारित करें S और T जैसे कि एस-टी कट की क्षमता न्यूनतम हो।

मुख्य प्रमेय

उपरोक्त स्थिति में, कोई यह साबित कर सकता है कि नेटवर्क के माध्यम से किसी भी प्रवाह का मूल्य किसी भी सेंट कट की क्षमता से कम या उसके बराबर है, और इसके अलावा अधिकतम मूल्य वाला प्रवाह और न्यूनतम क्षमता वाला कट मौजूद है। मुख्य प्रमेय अधिकतम प्रवाह मान को नेटवर्क की न्यूनतम कट क्षमता से जोड़ता है।

'अधिकतम-प्रवाह न्यूनतम-कट प्रमेय।' एक एस-टी प्रवाह का अधिकतम मूल्य सभी एस-टी कटों पर न्यूनतम क्षमता के बराबर है।

उदाहरण

किसी नेटवर्क में अधिकतम प्रवाह. प्रत्येक किनारे को f/c से लेबल किया गया है, जहां f किनारे पर प्रवाह है और c किनारे की क्षमता है। प्रवाह मान 5 है। क्षमता 5 के साथ कई न्यूनतम एस-टी कट हैं; एक है S={s,p} और T={o, q, r, t}।

दाईं ओर का चित्र नेटवर्क में प्रवाह दिखाता है। प्रत्येक तीर पर एफ/सी के रूप में संख्यात्मक एनोटेशन, तीर के प्रवाह (एफ) और क्षमता (सी) को इंगित करता है। स्रोत से निकलने वाले प्रवाहों की कुल संख्या पाँच (2+3=5) है, जैसा कि सिंक में प्रवाह (2+3=5) से होता है, जिससे यह स्थापित होता है कि प्रवाह का मान 5 है।

मान 5 के साथ एक s-t कट S={s,p} और T={o, q, r, t} द्वारा दिया जाता है। इस कट को पार करने वाले किनारों की क्षमता 3 और 2 है, जो 3+2=5 की कट क्षमता देती है। (ओ से पी तक तीर पर विचार नहीं किया जाता है, क्योंकि यह टी से वापस एस की ओर इशारा करता है।)

प्रवाह का मान कट की क्षमता के बराबर है, यह दर्शाता है कि प्रवाह अधिकतम प्रवाह है और कट न्यूनतम कट है।

ध्यान दें कि S को T से जोड़ने वाले दो तीरों में से प्रत्येक के माध्यम से प्रवाह पूरी क्षमता पर है; यह हमेशा मामला होता है: न्यूनतम कटौती सिस्टम की 'अड़चन' का प्रतिनिधित्व करती है।

रैखिक कार्यक्रम सूत्रीकरण

अधिकतम-प्रवाह समस्या और न्यूनतम-कट समस्या को दो दोहरे रैखिक कार्यक्रम | प्राइमल-दोहरी रैखिक प्रोग्रामिंग के रूप में तैयार किया जा सकता है।

	Max-flow (Primal)	Min-cut (Dual)
variables	$f_{uv}$ $\forall (u,v)\in E$ [a variable per edge]	$d_{uv}$ $\forall (u,v)\in E$ [a variable per edge] $z_{v}$ $\forall v\in V\setminus \{s,t\}$ [a variable per non-terminal node]
objective	maximize $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ [max total flow from source]	minimize $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ [min total capacity of edges in cut]
constraints	subject to ${\begin{aligned}f_{uv}&\leq c_{uv}&&\forall (u,v)\in E\\\sum _{u}f_{uv}-\sum _{w}f_{vw}&=0&&v\in V\setminus \{s,t\}\end{aligned}}$ [a constraint per edge and a constraint per non-terminal node]	subject to ${\begin{aligned}d_{uv}-z_{u}+z_{v}&\geq 0&&\forall (u,v)\in E,u\neq s,v\neq t\\d_{sv}+z_{v}&\geq 1&&\forall (s,v)\in E,v\neq t\\d_{ut}-z_{u}&\geq 0&&\forall (u,t)\in E,u\neq s\\d_{st}&\geq 1&&{\text{if }}(s,t)\in E\end{aligned}}$ [a constraint per edge]
sign constraints	${\begin{aligned}f_{uv}&\geq 0&&\forall (u,v)\in E\\\end{aligned}}$	${\begin{aligned}d_{uv}&\geq 0&&\forall (u,v)\in E\\z_{v}&\in \mathbb {R} &&\forall v\in V\setminus \{s,t\}\end{aligned}}$

अधिकतम-प्रवाह एलपी सीधा है। दोहरे एलपी को दोहरे रैखिक कार्यक्रम में वर्णित एल्गोरिदम का उपयोग करके प्राप्त किया जाता है: दोहरे के चर और संकेत बाधाएं प्रारंभिक की बाधाओं के अनुरूप होती हैं, और दोहरे की बाधाएं प्रारंभिक के चर और संकेत बाधाओं के अनुरूप होती हैं। परिणामी एलपी को कुछ स्पष्टीकरण की आवश्यकता है। न्यूनतम-कट एलपी में चर की व्याख्या इस प्रकार है:

$d_{uv}={\begin{cases}1,&{\text{if }}u\in S{\text{ and }}v\in T{\text{ (the edge }}uv{\text{ is in the cut) }}\\0,&{\text{otherwise}}\end{cases}}$ :$z_{v}={\begin{cases}1,&{\text{if }}v\in S\\0,&{\text{otherwise}}\end{cases}}$

न्यूनतमकरण उद्देश्य कट में निहित सभी किनारों की क्षमता का योग करता है।

बाधाएँ गारंटी देती हैं कि चर वास्तव में कानूनी कटौती का प्रतिनिधित्व करते हैं:

• बाधाएँ $d_{uv}-z_{u}+z_{v}\geq 0$ (के बराबर $d_{uv}\geq z_{u}-z_{v}$) गारंटी दें कि, गैर-टर्मिनल नोड्स यू, वी के लिए, यदि यू एस में है और वी टी में है, तो किनारे (यू, वी) को कट में गिना जाता है ($d_{uv}\geq 1$).
• बाधाएँ $d_{sv}+z_{v}\geq 1$ (के बराबर $d_{sv}\geq 1-z_{v}$) गारंटी दें कि, यदि v T में है, तो किनारे (s,v) को कट में गिना जाता है (क्योंकि s, S में परिभाषा के अनुसार है)।
• बाधाएँ $d_{ut}-z_{u}\geq 0$ (के बराबर $d_{ut}\geq z_{u}$) गारंटी दें कि, यदि यू एस में है, तो किनारे (यू, टी) को कट में गिना जाता है (क्योंकि टी टी में परिभाषा के अनुसार है)।

ध्यान दें कि, चूंकि यह एक न्यूनतमकरण समस्या है, इसलिए हमें यह गारंटी नहीं देनी है कि कोई किनारा कट में नहीं है - हमें केवल यह गारंटी देनी है कि प्रत्येक किनारा जो कट में होना चाहिए, उद्देश्य फ़ंक्शन में संक्षेपित है।

'अधिकतम-प्रवाह न्यूनतम-कट प्रमेय' में समानता दोहरे रैखिक कार्यक्रम से आती है, जो बताता है कि यदि प्रारंभिक कार्यक्रम में इष्टतम समाधान है, x*, तो दोहरे कार्यक्रम में भी इष्टतम समाधान है, y*, जैसे कि दो समाधानों द्वारा गठित इष्टतम मान बराबर हैं।

आवेदन

सीडरबाम का अधिकतम प्रवाह प्रमेय

See also: Cederbaum's maximum flow theorem

अधिकतम प्रवाह समस्या को गैर-रेखीय प्रतिरोधी तत्वों से बने नेटवर्क के माध्यम से विद्युत प्रवाह के अधिकतमकरण के रूप में तैयार किया जा सकता है। इस सूत्रीकरण में, धारा की सीमा  I_in विद्युत नेटवर्क के इनपुट टर्मिनलों के बीच इनपुट वोल्टेज के रूप में V_in दृष्टिकोण $\infty$, न्यूनतम-वजन कट सेट के वजन के बराबर है।

$\lim _{V_{\text{in}}\to \infty }(I_{in})=\min _{X_{C}}\sum _{(u,v)\in X_{C}}c_{uv}$

सामान्यीकृत अधिकतम-प्रवाह न्यूनतम-कट प्रमेय

किनारे की क्षमता के अलावा, विचार करें कि प्रत्येक शीर्ष पर क्षमता है, यानी एक मानचित्रण $c:V\to \mathbb {R} ^{+}$ द्वारा चिह्नित c(v), ऐसे कि प्रवाह  f  को न केवल क्षमता बाधा और प्रवाह के संरक्षण को संतुष्ट करना होगा, बल्कि शीर्ष क्षमता बाधा को भी पूरा करना होगा

$\forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u\in V\mid (u,v)\in E\}}f_{uv}\leq c(v).$

दूसरे शब्दों में, किसी शीर्ष से गुजरने वाले प्रवाह की मात्रा उसकी क्षमता से अधिक नहीं हो सकती। एक एस-टी कट को शीर्षों और किनारों के सेट के रूप में परिभाषित करें, जैसे कि एस से टी तक किसी भी पथ के लिए, पथ में कट का एक सदस्य शामिल हो। इस मामले में, कट की क्षमता इसमें प्रत्येक किनारे और शीर्ष की क्षमता का योग है।

इस नई परिभाषा में, 'सामान्यीकृत अधिकतम-प्रवाह न्यूनतम-कट प्रमेय' बताता है कि एक एस-टी प्रवाह का अधिकतम मूल्य नए अर्थ में एक एस-टी कट की न्यूनतम क्षमता के बराबर है।

मेंजर का प्रमेय

See also: Menger's Theorem

अप्रत्यक्ष किनारे-असंयुक्त पथ समस्या में, हमें एक अप्रत्यक्ष ग्राफ़ दिया गया है G = (V, E) और दो शीर्ष s और t, और हमें किनारे-विसंयुक्त एस-टी पथों की अधिकतम संख्या ढूंढनी होगी G.

मेन्जर के प्रमेय में कहा गया है कि एक अप्रत्यक्ष ग्राफ में किनारे-असंयुक्त सेंट पथों की अधिकतम संख्या एक सेंट कट-सेट में किनारों की न्यूनतम संख्या के बराबर है।

प्रोजेक्ट चयन समस्या

इष्टतम समाधान के साथ परियोजना चयन समस्या का एक नेटवर्क सूत्रीकरण

परियोजना चयन समस्या में, हैं n परियोजनाएं और m मशीनें. प्रत्येक परियोजना p_i राजस्व प्राप्त होता है r(p_i) और प्रत्येक मशीन q_j लागत c(q_j) खरीदने के लिए। प्रत्येक परियोजना के लिए कई मशीनों की आवश्यकता होती है और प्रत्येक मशीन को कई परियोजनाओं द्वारा साझा किया जा सकता है। समस्या यह निर्धारित करने की है कि किन परियोजनाओं और मशीनों को क्रमशः चुना और खरीदा जाना चाहिए, ताकि लाभ अधिकतम हो।

होने देना P चयनित न की गई परियोजनाओं का सेट हो और Q खरीदी गई मशीनों का सेट हो, तो समस्या को इस प्रकार तैयार किया जा सकता है,

$\max\{g\}=\sum _{i}r(p_{i})-\sum _{p_{i}\in P}r(p_{i})-\sum _{q_{j}\in Q}c(q_{j}).$

चूँकि पहला पद की पसंद पर निर्भर नहीं करता है P और Q, इस अधिकतमीकरण समस्या को इसके बजाय न्यूनतमकरण समस्या के रूप में तैयार किया जा सकता है, अर्थात,

$\min\{g'\}=\sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j}).$

उपरोक्त न्यूनतमकरण समस्या को एक नेटवर्क का निर्माण करके न्यूनतम-कट समस्या के रूप में तैयार किया जा सकता है, जहां स्रोत क्षमता वाली परियोजनाओं से जुड़ा होता है r(p_i), और सिंक को क्षमता वाली मशीनों द्वारा जोड़ा जाता है c(q_j). एक किनारा (p_i, q_j) यदि प्रोजेक्ट में अनंत क्षमता जोड़ी जाती है p_iमशीन की आवश्यकता है q_j. एस-टी कट-सेट परियोजनाओं और मशीनों का प्रतिनिधित्व करता है P और Q क्रमश। अधिकतम-प्रवाह न्यूनतम-कट प्रमेय द्वारा, कोई समस्या को अधिकतम प्रवाह समस्या के रूप में हल कर सकता है।

दाईं ओर का चित्र निम्नलिखित परियोजना चयन समस्या का नेटवर्क सूत्रीकरण देता है:

	Project r(pi)	Machine c(qj)
1	100	200	Project 1 requires machines 1 and 2.
2	200	100	Project 2 requires machine 2.
3	150	50	Project 3 requires machine 3.

एस-टी कट की न्यूनतम क्षमता 250 है और प्रत्येक परियोजना के राजस्व का योग 450 है; इसलिए परियोजनाओं का चयन करके अधिकतम लाभ g 450 - 250 = 200 है p₂ और p₃.

यहां विचार प्रत्येक परियोजना के मुनाफे को उसकी मशीनों के 'पाइप' के माध्यम से 'प्रवाह' करने का है। यदि हम किसी मशीन से पाइप नहीं भर सकते हैं, तो मशीन का रिटर्न उसकी लागत से कम है, और न्यूनतम कटौती एल्गोरिदम को मशीन की लागत बढ़त के बजाय परियोजना की लाभ बढ़त में कटौती करना सस्ता लगेगा।

छवि विभाजन समस्या

See also: Maximum flow problem

प्रत्येक काला नोड एक पिक्सेल को दर्शाता है।

छवि विभाजन समस्या में, हैं n पिक्सल। प्रत्येक पिक्सेल i को अग्रभूमि मान निर्दिष्ट किया जा सकता है  f_i या पृष्ठभूमि मान b_i. का जुर्माना है p_ij यदि पिक्सेल i, j आसन्न हैं और उनके अलग-अलग कार्य हैं। समस्या यह है कि पिक्सेल को अग्रभूमि या पृष्ठभूमि में इस प्रकार निर्दिष्ट किया जाए कि उनके मानों का योग शून्य से दंड अधिकतम हो।

होने देना P अग्रभूमि को निर्दिष्ट पिक्सेल का सेट बनें और Q पृष्ठभूमि को निर्दिष्ट बिंदुओं का सेट हो, तो समस्या को इस प्रकार तैयार किया जा सकता है,

$\max\{g\}=\sum _{i\in P}f_{i}+\sum _{i\in Q}b_{i}-\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.$

इस अधिकतमीकरण समस्या को इसके बजाय न्यूनतमकरण समस्या के रूप में तैयार किया जा सकता है, अर्थात,

$\min\{g'\}=\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.$

उपरोक्त न्यूनतमकरण समस्या को एक नेटवर्क का निर्माण करके न्यूनतम-कट समस्या के रूप में तैयार किया जा सकता है जहां स्रोत (नारंगी नोड) क्षमता वाले सभी पिक्सेल से जुड़ा हुआ है  f_i, और सिंक (बैंगनी नोड) क्षमता वाले सभी पिक्सेल से जुड़ा हुआ है b_i. दो किनारे (i, j) और (j, i) साथ p_ij क्षमता दो आसन्न पिक्सेल के बीच जोड़ी जाती है। एस-टी कट-सेट तब अग्रभूमि में निर्दिष्ट पिक्सेल का प्रतिनिधित्व करता है P और पिक्सल को पृष्ठभूमि में असाइन किया गया है Q.

इतिहास

प्रमेय की खोज का विवरण एल. आर. फोर्ड जूनियर और डी. आर. फुलकर्सन द्वारा 1962 में दिया गया था: आर्क्स पर क्षमता सीमाओं के अधीन नेटवर्क में एक बिंदु से दूसरे बिंदु तक अधिकतम स्थिर स्थिति प्रवाह का निर्धारण ... 1955 के वसंत में टी.ई. द्वारा लेखकों के सामने रखा गया था। हैरिस, जिन्होंने जनरल एफ.एस. रॉस (सेवानिवृत्त) के साथ मिलकर रेलवे यातायात प्रवाह का एक सरलीकृत मॉडल तैयार किया था, और इस विशेष समस्या को मॉडल द्वारा सुझाई गई केंद्रीय समस्या के रूप में इंगित किया था। इसके बाद ज्यादा समय नहीं बीता जब मुख्य परिणाम, प्रमेय 5.1, जिसे हम अधिकतम-प्रवाह न्यूनतम-कट प्रमेय कहते हैं, का अनुमान लगाया गया और स्थापित किया गया। तब से कई सबूत सामने आए हैं।

प्रमाण

होने देना G = (V, E) के साथ एक नेटवर्क (निर्देशित ग्राफ़) बनें s और t का स्रोत और सिंक होना G क्रमश।

प्रवाह पर विचार करें  f  के लिए गणना की गई G फोर्ड-फ़ल्कर्सन एल्गोरिथम द्वारा। अवशिष्ट ग्राफ में (G_f ) के लिए प्राप्त किया गया G (फोर्ड-फुलकर्सन एल्गोरिदम द्वारा अंतिम प्रवाह असाइनमेंट के बाद), शीर्षों के दो उपसमूहों को निम्नानुसार परिभाषित करें:

1. A: से पहुंच योग्य शीर्षों का सेट s में G_f
2. A^c: शेष शीर्षों का समुच्चय अर्थात V − A

दावा करना। value( f ) = c(A, A^c), जहां एस-टी कट की क्षमता को परिभाषित किया गया है

$c(S,T)=\sum \nolimits _{(u,v)\in S\times T}c_{uv}$.

अब, हम जानते हैं, $value(f)=f_{out}(A)-f_{in}(A)$ शीर्षों के किसी उपसमुच्चय के लिए, A. इसलिए, के लिए value( f ) = c(A, A^c) ज़रुरत है:

• कट से निकलने वाले सभी किनारे 'पूरी तरह से संतृप्त' होने चाहिए।
• कट के सभी आने वाले किनारों में 'शून्य प्रवाह' होना चाहिए।

उपरोक्त दावे को साबित करने के लिए हम दो मामलों पर विचार करते हैं:

• में G, एक आउटगोइंग एज मौजूद है $(x,y),x\in A,y\in A^{c}$ ऐसा कि यह संतृप्त नहीं है, यानी,  f (x, y) < c_xy. इसका तात्पर्य यह है कि आगे की ओर एक किनारा मौजूद है x को y में G_f, इसलिए वहां से एक रास्ता मौजूद है s को y में G_f, जो एक विरोधाभास है। इसलिए, कोई भी आउटगोइंग एज (x, y) पूर्णतः संतृप्त है।

• में G, एक आने वाली बढ़त मौजूद है $(y,x),x\in A,y\in A^{c}$ ऐसा कि इसमें कुछ गैर-शून्य प्रवाह होता है, यानी,  f (y, x) > 0. इसका तात्पर्य यह है कि वहाँ से एक पिछड़ा किनारा मौजूद है x को y में G_f, इसलिए वहां से एक रास्ता मौजूद है s को y में G_f, जो फिर से एक विरोधाभास है। इसलिए, कोई भी आने वाली बढ़त (y, x) शून्य प्रवाह होना चाहिए.

उपरोक्त दोनों कथन यह साबित करते हैं कि ऊपर वर्णित तरीके से प्राप्त कट की क्षमता नेटवर्क में प्राप्त प्रवाह के बराबर है। साथ ही, प्रवाह फोर्ड-फ़ल्कर्सन एल्गोरिथम द्वारा प्राप्त किया गया था, इसलिए यह नेटवर्क का अधिकतम-प्रवाह भी है।

इसके अलावा, चूंकि नेटवर्क में कोई भी प्रवाह हमेशा नेटवर्क में संभव प्रत्येक कट की क्षमता से कम या उसके बराबर होता है, ऊपर वर्णित कट भी न्यूनतम-कट है जो अधिकतम-प्रवाह प्राप्त करता है।

इस प्रमाण से एक परिणाम यह है कि ग्राफ़ के कट में किनारों के किसी भी सेट के माध्यम से अधिकतम प्रवाह पिछले सभी कटों की न्यूनतम क्षमता के बराबर है।

यह भी देखें

• जीएनआरएस अनुमान
• रैखिक प्रोग्रामिंग
• अधिकतम प्रवाह
• न्यूनतम कटौती
• प्रवाह नेटवर्क
• एडमंड्स-कार्प एल्गोरिथम
• फोर्ड-फ़ल्कर्सन एल्गोरिथम
• अनुमानित अधिकतम-प्रवाह न्यूनतम-कट प्रमेय
• मेन्जर का प्रमेय

संदर्भ

• Eugene Lawler (2001). "4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem". Combinatorial Optimization: Networks and Matroids. Dover. pp. 117–120. ISBN 0-486-41453-1.
• Christos H. Papadimitriou, Kenneth Steiglitz (1998). "6.1 The Max-Flow, Min-Cut Theorem". Combinatorial Optimization: Algorithms and Complexity. Dover. pp. 120–128. ISBN 0-486-40258-4.
• Vijay V. Vazirani (2004). "12. Introduction to LP-Duality". Approximation Algorithms. Springer. pp. 93–100. ISBN 3-540-65367-8.