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

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

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

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

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

नेटवर्क

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

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

प्रवाह

किसी नेटवर्क के माध्यम से प्रवाह मैपिंग $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}$ किनारों का सेट है जो कट के स्रोत भाग को सिंक भाग से जोड़ता है:

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

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

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

$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$ अर्थात

एक ग्राफ़ में सामान्यतः अनेक कट होते हैं, किन्तु छोटे वजन वाले कट अधिकांशतः खोजना अधिक कठिन होते हैं।

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

मुख्य प्रमेय

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

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

उदाहरण

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

दाईं ओर का चित्र नेटवर्क में प्रवाह दिखाता है। प्रत्येक तीर पर एफ/सी के रूप में संख्यात्मक एनोटेशन, तीर के प्रवाह (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 से जोड़ने वाले दो तीरों में से प्रत्येक के माध्यम से प्रवाह पूरी क्षमता पर है; यह सदैव स्थिति होता है: न्यूनतम डिडक्शन सिस्टम की 'अड़चन' का प्रतिनिधित्व करती है।

रैखिक प्रोग्राम सूत्रीकरण

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

	अधिकतम-प्रवाह (प्राइमल)	न्यूनतम-कट (दोहरी)
वैरीएबल	$f_{uv}$ $\forall (u,v)\in E$ [प्रति किनारे वैरीएबल]	$d_{uv}$ $\forall (u,v)\in E$ [प्रति किनारे वैरीएबल] $z_{v}$ $\forall v\in V\setminus \{s,t\}$ [प्रति गैर-टर्मिनल नोड वैरीएबल]
उद्देश्य	अधिकतम $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ [स्रोत से अधिकतम कुल प्रवाह]	न्यूनतम $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ [कट में किनारों की न्यूनतम कुल क्षमता]
प्रतिबंध	विषय है ${\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}}$ [प्रति किनारे बाधा और प्रति गैर-टर्मिनल नोड बाधा]	विषय है ${\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}}$ [प्रति किनारे बाधा]
sign प्रतिबंध	${\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}}$

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

बाधाएँ गारंT देती हैं कि वैरीएबल वास्तव में नियमबद्ध डिडक्शन का प्रतिनिधित्व करते हैं:

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

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

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

आवेदन

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

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

अधिकतम प्रवाह समस्या को गैर-रेखीय प्रतिरोधी अवयवो से बने नेटवर्क के माध्यम से विद्युत प्रवाह के अधिकतमकरण के रूप में तैयार किया जा सकता है। इस सूत्रीकरण में, धारा की सीमा  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).$

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

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

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

See also: मेन्जर का प्रमेय

अप्रत्यक्ष किनारे-विच्छेद पथ समस्या में, हमें अप्रत्यक्ष ग्राफ G = (V, E) और दो शीर्ष s और t दिए गए हैं, और हमें G में किनारे-विच्छेदित s-t पथों की अधिकतम संख्या ज्ञात करनी है।

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

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

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

प्रोजेक्ट चयन समस्या में, 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) जोड़ा जाता है। S-T कट-सेट क्रमशः P और Q में परियोजनाओं और मशीनों का प्रतिनिधित्व करता है। अधिकतम-प्रवाह न्यूनतम-कट प्रमेय द्वारा, कोई समस्या को अधिकतम प्रवाह समस्या के रूप में हल कर सकता है।

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

	प्रोजेक्टr(pi)	मशीन c(qj)
1	100	200	प्रोजेक्ट1 आवश्यक मशीन 1 और 2.
2	200	100	प्रोजेक्ट2 आवश्यक मशीन 2.
3	150	50	प्रोजेक्ट3 आवश्यक मशीन 3.

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

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

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

See also: अधिकतम प्रवाह समस्या

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

छवि विभाजन समस्या में, 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 वाले सभी पिक्सल से जुड़ा हुआ है, और सिंक (बैंगनी नोड) क्षमता द्वि के साथ सभी पिक्सल से जुड़ा हुआ है पीज क्षमता वाले दो किनारे (i, j) और (j, i) दो आसन्न पिक्सेल के बीच जोड़े जाते हैं। एस-टी कट-सेट तब p_ij में अग्रभूमि को निर्दिष्ट पिक्सेल और Q में पृष्ठभूमि को निर्दिष्ट पिक्सेल का प्रतिनिधित्व करता है।

इतिहास

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

प्रमाण

मान लीजिए G = (V, E) नेटवर्क (निर्देशित ग्राफ) है जिसमें s और t क्रमशः G का स्रोत और सिंक हैं।

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

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

प्रमाण मूल्य value( f ) = c(A, A^c) जहां S-T कट की क्षमता को परिभाषित किया गया है

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

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

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

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

• G में, आउटगोइंग एज उपस्थित है $(x,y),x\in A,y\in A^{c}$ ऐसा कि यह संतृप्त नहीं है, अर्थात,  f (x, y) < c_xy. इसका तात्पर्य यह है कि G_f में x को y तक आगे का किनारा उपस्थित है, इसलिए G_f में s को y तक पथ उपस्थित है, जो विरोधाभास है। इसलिए, कोई भी आउटगोइंग किनारा (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.