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

Latest revision as of 15:38, 8 September 2023

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

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

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

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

नेटवर्क

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

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

प्रवाह

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

क्षमता की कमी: प्रत्येक किनारे के लिए $(u,v)\in E$ , $f_{uv}\leq c_{uv}.$
प्रवाह का संरक्षण: प्रत्येक शीर्ष के लिए $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 \in S$ और $t \in 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 से जोड़ने वाले दो तीरों में से प्रत्येक के माध्यम से प्रवाह पूरी क्षमता पर है; यह सदैव स्थिति होता है: न्यूनतम डिडक्शन सिस्टम की 'अड़चन' का प्रतिनिधित्व करती है।

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

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

	अधिकतम-प्रवाह (प्राइमल)	न्यूनतम-कट (दोहरी)
वैरीएबल	$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 देती हैं कि वैरीएबल वास्तव में नियमबद्ध डिडक्शन का प्रतिनिधित्व करते हैं:^[3]

बाधाएँ $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*, द्वारा गठित इष्टतम मान समान हैं।

आवेदन

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

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

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

अप्रत्यक्ष किनारे-विच्छेद पथ समस्या में, हमें अप्रत्यक्ष ग्राफ $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 (p i)$	मशीन $c (q j)$
1	100	200	प्रोजेक्ट1 आवश्यक मशीन 1 और 2.
2	200	100	प्रोजेक्ट2 आवश्यक मशीन 2.
3	150	50	प्रोजेक्ट3 आवश्यक मशीन 3.

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

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

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

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

छवि विभाजन समस्या में, $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 में दिया गया था:^[5] आर्क्स पर क्षमता सीमाओं के अधीन नेटवर्क में बिंदु से दूसरे बिंदु तक अधिकतम स्थिर स्थिति प्रवाह का निर्धारण ... 1955 के वसंत में टी.ई. द्वारा लेखकों के सामने रखा गया था। हैरिस, जिन्होंने जनरल एफ.एस. रॉस (सेवानिवृत्त) के साथ मिलकर रेलवे यातायात प्रवाह का सरलीकृत मॉडल तैयार किया था, और इस विशेष समस्या को मॉडल द्वारा सुझाई गई केंद्रीय समस्या के रूप में संकेत किया था। इसके पश्चात् अधिक समय नहीं बीता जब मुख्य परिणाम, प्रमेय 5.1, जिसे हम अधिकतम-प्रवाह न्यूनतम-कट प्रमेय कहते हैं, जिसका अनुमान लगाया गया और स्थापित किया गया था।^[6] तब से अनेक प्रमाण सामने आए हैं।^[7]^[8]^[9]

प्रमाण

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

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

$A$ : $G f$ में $s$ से पहुंच योग्य शीर्षों का समुच्चय
$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)$ शून्य प्रवाह होना चाहिए.

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

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

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

यह भी देखें

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

संदर्भ

↑ Dantzig, G.B.; Fulkerson, D.R. (9 September 1964). "नेटवर्क के अधिकतम-प्रवाह न्यूनतम-कट प्रमेय पर" (PDF). RAND Corporation: 13. Archived from the original (PDF) on 5 May 2018.
↑ Trevisan, Luca. "Lecture 15 from CS261: Optimization" (PDF).
↑ Keller, Orgad. "एलपी न्यूनतम-कट अधिकतम-प्रवाह प्रस्तुति".
↑ Cederbaum, I. (August 1962). "संचार नेटवर्क के इष्टतम संचालन पर". Journal of the Franklin Institute. 274: 130–141.
↑ L. R. Ford Jr. & D. R. Fulkerson (1962) Flows in Networks, page 1, Princeton University Press MR0159700
↑ L. R. Ford Jr. and D. R. Fulkerson (1956) "Maximal flow through a network", Canadian Journal of Mathematics 8: 399-404
↑ P. Elias, A. Feinstein, and C. E. Shannon (1956) "A note on the maximum flow through a network", IRE. Transactions on Information Theory, 2(4): 117–119
↑ George Dantzig and D. R. Fulkerson (1956) "On the Max-Flow MinCut Theorem of Networks", in Linear Inequalities, Ann. Math. Studies, no. 38, Princeton, New Jersey
↑ L. R. Ford & D. R. Fulkerson (1957) "A simple algorithm for finding the maximum network flows and an application to the Hitchcock problem", Canadian Journal of Mathematics 9: 210–18

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.

[1] Dantzig, G.B.; Fulkerson, D.R. (9 September 1964). "नेटवर्क के अधिकतम-प्रवाह न्यूनतम-कट प्रमेय पर" (PDF). RAND Corporation: 13. Archived from the original (PDF) on 5 May 2018.

[2] Trevisan, Luca. "Lecture 15 from CS261: Optimization" (PDF).

[3] Keller, Orgad. "एलपी न्यूनतम-कट अधिकतम-प्रवाह प्रस्तुति".

[4] Cederbaum, I. (August 1962). "संचार नेटवर्क के इष्टतम संचालन पर". Journal of the Franklin Institute. 274: 130–141.

[5] L. R. Ford Jr. & D. R. Fulkerson (1962) Flows in Networks, page 1, Princeton University Press MR0159700

[6] L. R. Ford Jr. and D. R. Fulkerson (1956) "Maximal flow through a network", Canadian Journal of Mathematics 8: 399-404

[7] P. Elias, A. Feinstein, and C. E. Shannon (1956) "A note on the maximum flow through a network", IRE. Transactions on Information Theory, 2(4): 117–119

[8] George Dantzig and D. R. Fulkerson (1956) "On the Max-Flow MinCut Theorem of Networks", in Linear Inequalities, Ann. Math. Studies, no. 38, Princeton, New Jersey

[9] L. R. Ford & D. R. Fulkerson (1957) "A simple algorithm for finding the maximum network flows and an application to the Hitchcock problem", Canadian Journal of Mathematics 9: 210–18

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 15:38, 8 September 2023

Contents

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

नेटवर्क

प्रवाह

डिडक्शन

मुख्य प्रमेय

उदाहरण

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

आवेदन

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

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

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

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

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

इतिहास

प्रमाण

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{short description|Concept in optimization theory}}
-[[कंप्यूटर विज्ञान]] और ऑप्टिमाइज़ेशन (गणित) में, अधिकतम-प्रवाह न्यूनतम-कट प्रमेय बताता है कि एक [[प्रवाह नेटवर्क]] में, ग्राफ़ सिद्धांत की शब्दावली से गुजरने वाले प्रवाह की अधिकतम मात्रा #दिशा|
+[[कंप्यूटर विज्ञान]] और ऑप्टिमाइज़ेशन (गणित) में, '''अधिकतम-प्रवाह न्यूनतम-कट प्रमेय''' बताता है कि [[प्रवाह नेटवर्क|फ्लो नेटवर्क]] में, ग्राफ़ सिद्धांत की शब्दावली से निकलने वाले प्रवाह की अधिकतम मात्रा न्यूनतम कट में किनारों के कुल वजन के समान होती है अर्थात सबसे छोटा कुल किनारों का भार, जिसे हटाने पर स्रोत सिंक से भिन्न हो जाता है।
-यह [[रैखिक कार्यक्रम]]ों के लिए [[दोहरी समस्या]] का एक विशेष मामला है और इसका उपयोग मेन्जर के प्रमेय और कोनिग के प्रमेय (ग्राफ सिद्धांत) | कोनिग-एगर्वरी प्रमेय को प्राप्त करने के लिए किया जा सकता है।<ref>{{cite journal| last1=Dantzig |first1=G.B. |last2= Fulkerson |first2=D.R.|title=नेटवर्क के अधिकतम-प्रवाह न्यूनतम-कट प्रमेय पर|journal=RAND Corporation|date=9 September 1964| page=13 |url= http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|archive-url=https://web.archive.org/web/20180505093256/http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|archive-date=5 May 2018|url-status=dead}}</ref>
+यह [[रैखिक कार्यक्रम|रैखिक]] प्रोग्राम के लिए [[दोहरी समस्या|द्वैत प्रमेय]] का विशेष स्थिति है और इसका उपयोग मेन्जर के प्रमेय और कोनिग के प्रमेय (ग्राफ सिद्धांत) या कोनिग-एगर्वरी प्रमेय को प्राप्त करने के लिए किया जा सकता है।<ref>{{cite journal| last1=Dantzig |first1=G.B. |last2= Fulkerson |first2=D.R.|title=नेटवर्क के अधिकतम-प्रवाह न्यूनतम-कट प्रमेय पर|journal=RAND Corporation|date=9 September 1964| page=13 |url= http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|archive-url=https://web.archive.org/web/20180505093256/http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|archive-date=5 May 2018|url-status=dead}}</ref>
 ==परिभाषाएँ और कथन==
-प्रमेय दो मात्राओं को बराबर करता है: एक नेटवर्क के माध्यम से अधिकतम प्रवाह, और नेटवर्क में कटौती की न्यूनतम क्षमता। प्रमेय बताने के लिए, इनमें से प्रत्येक धारणा को पहले परिभाषित किया जाना चाहिए।
+प्रमेय दो मात्राओं को समान करता है: नेटवर्क के माध्यम से अधिकतम प्रवाह, और नेटवर्क में डिडक्शन की न्यूनतम क्षमता प्रमेय बताने के लिए, इनमें से प्रत्येक धारणा को पहले परिभाषित किया जाना चाहिए।
 ===नेटवर्क===
@@ Line 13: / Line 11: @@
 एक नेटवर्क से मिलकर बनता है
 * एक परिमित [[निर्देशित ग्राफ]] {{math|''N'' {{=}} (''V'', ''E'')}}, जहां V शीर्षों के परिमित समुच्चय को दर्शाता है और {{math|''E'' ⊆ ''V''×''V''}} निर्देशित किनारों का समूह है;
-* एक स्रोत {{math|''s'' ∈ ''V''}} और एक सिंक {{math|''t'' ∈ ''V''}};
+* एक स्रोत {{math|''s'' ∈ ''V''}} और सिंक {{math|''t'' ∈ ''V''}};
-* एक क्षमता फ़ंक्शन, जो एक मैपिंग है <math>c:E\to\R^+</math> द्वारा चिह्नित {{mvar|c<sub>uv</sub>}} या {{math|''c''(''u'', ''v'')}} के लिए {{math|(''u'',''v'') ∈ ''E''}}. यह प्रवाह की अधिकतम मात्रा का प्रतिनिधित्व करता है जो एक किनारे से गुजर सकता है।
+*एक क्षमता फ़ंक्शन जो मैपिंग {{math|(''u'',''v'') ∈ ''E''}} है, जिसे <math>c:E\to\R^+</math> के लिए {{mvar|c<sub>uv</sub>}} या {{math|''c''(''u'', ''v'')}} द्वारा निरूपित किया जाता है। यह अधिकतम मात्रा का प्रतिनिधित्व करता है। प्रवाह जो किनारे से निकल सकता है।
 === प्रवाह ===
-किसी नेटवर्क के माध्यम से प्रवाह एक मानचित्रण है <math>f:E\to\R^+</math> द्वारा चिह्नित <math>f_{uv}</math> या <math>f(u, v)</math>, निम्नलिखित दो बाधाओं के अधीन:
+किसी नेटवर्क के माध्यम से प्रवाह मैपिंग <math>f:E\to\R^+</math> है जिसे <math>f_{uv}</math> या <math>f(u, v)</math> द्वारा दर्शाया जाता है, जो निम्नलिखित दो बाधाओं के अधीन है:
-# क्षमता की कमी: हर किनारे के लिए <math>(u, v) \in E</math>, <math>f_{uv} \le c_{uv}.</math>
+# क्षमता की कमी: प्रत्येक किनारे के लिए <math>(u, v) \in E</math>, <math>f_{uv} \le c_{uv}.</math>
-# प्रवाह का संरक्षण: प्रत्येक शीर्ष के लिए <math>v</math> के अलावा <math>s</math> और <math>t</math> (यानी स्रोत और सिंक, क्रमशः), निम्नलिखित समानता रखती है:<br/><math>\sum\nolimits_{\{ u : (u,v)\in E\}} f_{uv} = \sum\nolimits_{\{w : (v,w)\in E\}} f_{vw}.</math>
+# प्रवाह का संरक्षण: प्रत्येक शीर्ष के लिए <math>v</math> के अतिरिक्त <math>s</math> और <math>t</math> (अर्थात स्रोत और सिंक, क्रमशः), निम्नलिखित समानता रखती है:<br/><math>\sum\nolimits_{\{ u : (u,v)\in E\}} f_{uv} = \sum\nolimits_{\{w : (v,w)\in E\}} f_{vw}.</math>
-प्रत्येक किनारे की दिशा का अनुसरण करते हुए, प्रवाह को नेटवर्क के माध्यम से तरल पदार्थ के भौतिक प्रवाह के रूप में देखा जा सकता है। क्षमता बाधा तब कहती है कि प्रति इकाई समय में प्रत्येक किनारे से बहने वाली मात्रा किनारे की अधिकतम क्षमता से कम या उसके बराबर है, और संरक्षण बाधा कहती है कि प्रत्येक शीर्ष में बहने वाली मात्रा स्रोत और सिंक शीर्ष के अलावा, प्रत्येक शीर्ष से बहने वाली मात्रा के बराबर होती है।
+प्रत्येक किनारे की दिशा का अनुसरण करते हुए, प्रवाह को नेटवर्क के माध्यम से तरल पदार्थ के भौतिक प्रवाह के रूप में देखा जा सकता है। क्षमता बाधा तब कहती है कि प्रति इकाई समय में प्रत्येक किनारे से बहने वाली मात्रा किनारे की अधिकतम क्षमता से कम या उसके समान है, और संरक्षण बाधा कहती है कि प्रत्येक शीर्ष में बहने वाली मात्रा स्रोत और सिंक शीर्ष के अतिरिक्त, प्रत्येक शीर्ष से बहने वाली मात्रा के समान होती है।
 प्रवाह का मान परिभाषित किया गया है
-:<math>|f| = \sum\nolimits_{\{v : (s,v)\in E\}} f_{sv}=\sum\nolimits_{\{v : (v,t)\in E\}} f_{vt},</math> जहां ऊपर बताया गया है <math>s</math> स्रोत है और <math>t</math> नेटवर्क का सिंक है. द्रव सादृश्य में, यह स्रोत पर नेटवर्क में प्रवेश करने वाले द्रव की मात्रा को दर्शाता है। प्रवाह के लिए संरक्षण सिद्धांत के कारण, यह सिंक पर नेटवर्क छोड़ने वाले प्रवाह की मात्रा के समान है।
+:<math>|f| = \sum\nolimits_{\{v : (s,v)\in E\}} f_{sv}=\sum\nolimits_{\{v : (v,t)\in E\}} f_{vt},</math>
+:जैसा कि ऊपर बताया गया है, <math>s</math> स्रोत है और <math>t</math> नेटवर्क का सिंक है। द्रव सादृश्य में, यह स्रोत पर नेटवर्क में प्रवेश करने वाले द्रव की मात्रा को दर्शाता है। प्रवाह के लिए संरक्षण सिद्धांत के कारण, यह सिंक पर नेटवर्क छोड़ने वाले प्रवाह की मात्रा के समान है।
 अधिकतम प्रवाह समस्या किसी दिए गए नेटवर्क पर सबसे बड़े प्रवाह की मांग करती है।
-<ब्लॉककोट>
-अधिकतम प्रवाह समस्या|अधिकतम प्रवाह समस्या। अधिकतम <math>|f|</math>, अर्थात्, जितना संभव हो सके उतने अधिक प्रवाह को रूट करना <math>s</math> को <math>t</math>.
-</ब्लॉककोट>
-=== कटौती ===
+अधिकतम प्रवाह समस्या अधिकतम करें <math>|f|</math> अर्थात जितना संभव हो उतना प्रवाह को <math>s</math> को <math>t</math> तक रूट करना है
-अधिकतम-प्रवाह न्यूनतम-कट प्रमेय का दूसरा भाग नेटवर्क के एक अलग पहलू को संदर्भित करता है: कटौती का संग्रह। एक एस-टी कट {{math|''C'' {{=}} (''S'', ''T'')}} का एक विभाजन है {{mvar|V}} ऐसा है कि {{math|''s'' ∈ ''S''}} और {{math|''t'' ∈ ''T''}}. अर्थात्, एस-टी कट नेटवर्क के शीर्षों को दो भागों में विभाजित करना है, जिसमें एक भाग में स्रोत और दूसरे में सिंक होता है। 'कट-सेट' <math>X_C</math> एक कट का {{mvar|C}} किनारों का समूह है जो कट के स्रोत भाग को सिंक भाग से जोड़ता है:
+=== डिडक्शन ===
+अधिकतम-प्रवाह न्यूनतम-कट प्रमेय का दूसरा भाग नेटवर्क के भिन्न पहलू को संदर्भित करता है: डिडक्शन का संग्रह सेंट कट {{math|''C'' {{=}} (''S'', ''T'')}} {{mvar|V}} का विभाजन है जैसे कि {{math|''s'' ∈ ''S''}} और {{math|''t'' ∈ ''T''}} अर्थात्, सेंट कट नेटवर्क के शीर्षों को दो भागों में विभाजित करता है, जिसमें भाग में स्रोत होता है और दूसरे में सिंक. कट सी का कट-सेट <math>X_C</math> किनारों का सेट है जो कट के स्रोत भाग को सिंक भाग से जोड़ता है:
 :<math>X_C := \{ (u, v) \in E \ : \ u \in S, v \in T \} = (S\times T) \cap E.</math>
-इस प्रकार, यदि सभी किनारे कट-सेट में हैं {{mvar|C}} हटा दिए जाते हैं, तो कोई सकारात्मक प्रवाह संभव नहीं है, क्योंकि परिणामी ग्राफ़ में स्रोत से सिंक तक कोई पथ नहीं है।
+इस प्रकार यदि {{mvar|C}} के कट-सेट में सभी किनारों को हटा दिया जाता है, तो कोई धनात्मक प्रवाह संभव नहीं है, क्योंकि परिणामी ग्राफ़ में स्रोत से सिंक तक कोई पथ नहीं है।
-''एसटी कट'' की क्षमता इसके कट-सेट में किनारों की क्षमता का योग है,
+''ST कट'' की क्षमता इसके कट-सेट में किनारों की क्षमता का योग है,
 :<math>c(S,T) = \sum\nolimits_{(u,v) \in X_C} c_{uv} = \sum\nolimits_{(i,j) \in E } c_{ij}d_{ij},</math>
-कहाँ <math>d_{ij} = 1</math> अगर <math>i \in S</math> और <math>j \in T</math>, <math>0</math> अन्यथा।
+जहाँ <math>d_{ij} = 1</math> यदि <math>i \in S</math> और <math>j \in T</math>, <math>0</math> अर्थात
-एक ग्राफ़ में आम तौर पर कई कट होते हैं, लेकिन छोटे वजन वाले कट अक्सर ढूंढना अधिक कठिन होते हैं।
+एक ग्राफ़ में सामान्यतः अनेक कट होते हैं, किन्तु छोटे वजन वाले कट अधिकांशतः खोजना अधिक कठिन होते हैं।
-:न्यूनतम एस-टी कट समस्या। छोटा करना {{math|''c''(''S'', ''T'')}}, अर्थात निर्धारित करें {{mvar|S}} और {{mvar|T}} जैसे कि एस-टी कट की क्षमता न्यूनतम हो।
+:न्यूनतम S-T कट समस्या {{math|''c''(''S'', ''T'')}} को न्यूनतम करें, अर्थात {{mvar|S}} और {{mvar|T}} को ऐसे निर्धारित करें कि सेंट कट की क्षमता न्यूनतम होते है।
 === मुख्य प्रमेय ===
-उपरोक्त स्थिति में, कोई यह साबित कर सकता है कि नेटवर्क के माध्यम से किसी भी प्रवाह का मूल्य किसी भी सेंट कट की क्षमता से कम या उसके बराबर है, और इसके अलावा अधिकतम मूल्य वाला प्रवाह और न्यूनतम क्षमता वाला कट मौजूद है। मुख्य प्रमेय अधिकतम प्रवाह मान को नेटवर्क की न्यूनतम कट क्षमता से जोड़ता है।
+उपरोक्त स्थिति में, कोई यह सिद्ध कर सकता है कि नेटवर्क के माध्यम से किसी भी प्रवाह का मूल्य किसी भी सेंट कट की क्षमता से कम या उसके समान है, और इसके अतिरिक्त अधिकतम मूल्य वाला प्रवाह और न्यूनतम क्षमता वाला कट उपस्थित है। मुख्य प्रमेय अधिकतम प्रवाह मान को नेटवर्क की न्यूनतम कट क्षमता से जोड़ता है।
-: 'अधिकतम-प्रवाह न्यूनतम-कट प्रमेय।' एक एस-टी प्रवाह का अधिकतम मूल्य सभी एस-टी कटों पर न्यूनतम क्षमता के बराबर है।
+: 'अधिकतम-प्रवाह न्यूनतम-कट प्रमेय' S-T प्रवाह का अधिकतम मूल्य सभी S-T कटों पर न्यूनतम क्षमता के समान है।
 ==उदाहरण==
-[[File:Max_flow.svg|thumb|right|किसी नेटवर्क में अधिकतम प्रवाह. प्रत्येक किनारे को f/c से लेबल किया गया है, जहां f किनारे पर प्रवाह है और c किनारे की क्षमता है। प्रवाह मान 5 है। क्षमता 5 के साथ कई न्यूनतम एस-टी कट हैं; एक है S={s,p} और T={o, q, r, t}।]]दाईं ओर का चित्र नेटवर्क में प्रवाह दिखाता है। प्रत्येक तीर पर एफ/सी के रूप में संख्यात्मक एनोटेशन, तीर के प्रवाह (एफ) और क्षमता (सी) को इंगित करता है। स्रोत से निकलने वाले प्रवाहों की कुल संख्या पाँच (2+3=5) है, जैसा कि सिंक में प्रवाह (2+3=5) से होता है, जिससे यह स्थापित होता है कि प्रवाह का मान 5 है।
+[[File:Max_flow.svg|thumb|right|किसी नेटवर्क में अधिकतम प्रवाह. प्रत्येक किनारे को 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 की कट क्षमता देती है। (ओ से पी तक तीर पर विचार नहीं किया जाता है, क्योंकि यह टी से वापस एस की ओर इशारा करता है।)
+मान 5 के साथ s-t कट S={s,p} और T={o, q, r, t} द्वारा दिया जाता है। इस कट को पार करने वाले किनारों की क्षमता 3 और 2 है, जो 3+2=5 की कट क्षमता देती है। (O से P तक तीर पर विचार नहीं किया जाता है, क्योंकि यह t से वापस S की ओर संकेत करता है।)
-प्रवाह का मान कट की क्षमता के बराबर है, यह दर्शाता है कि प्रवाह अधिकतम प्रवाह है और कट न्यूनतम कट है।
+प्रवाह का मान कट की क्षमता के समान है, यह दर्शाता है कि प्रवाह अधिकतम प्रवाह है और कट न्यूनतम कट है।
-ध्यान दें कि S को T से जोड़ने वाले दो तीरों में से प्रत्येक के माध्यम से प्रवाह पूरी क्षमता पर है; यह हमेशा मामला होता है: न्यूनतम कटौती सिस्टम की 'अड़चन' का प्रतिनिधित्व करती है।
+ध्यान दें कि S को T से जोड़ने वाले दो तीरों में से प्रत्येक के माध्यम से प्रवाह पूरी क्षमता पर है; यह सदैव स्थिति होता है: न्यूनतम डिडक्शन सिस्टम की 'अड़चन' का प्रतिनिधित्व करती है।
-==रैखिक कार्यक्रम सूत्रीकरण==
+==रैखिक प्रोग्राम सूत्रीकरण==
-अधिकतम-प्रवाह समस्या और न्यूनतम-कट समस्या को दो दोहरे रैखिक कार्यक्रम | प्राइमल-दोहरी [[रैखिक प्रोग्रामिंग]] के रूप में तैयार किया जा सकता है।<ref>{{Cite web| url= http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf|title=Lecture 15 from CS261: Optimization|last=Trevisan|first=Luca}}</ref>
+अधिकतम-प्रवाह समस्या और न्यूनतम-कट समस्या को दो दोहरे रैखिक प्रोग्राम या प्राइमल-दोहरी [[रैखिक प्रोग्रामिंग]] के रूप में तैयार किया जा सकता है।<ref>{{Cite web| url= http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf|title=Lecture 15 from CS261: Optimization|last=Trevisan|first=Luca}}</ref>
 {| class="wikitable" rules="" cellspacing="0" cellpadding="0" border="0"
 !
 ! style="border: 1px solid darkgrey;"|
-Max-flow (Primal)
+अधिकतम-प्रवाह (प्राइमल)
 ! style="border-top: 1px solid darkgrey; border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey;"|
-Min-cut (Dual)
+न्यूनतम-कट (दोहरी)
 |-
-|'''variables'''
+|'''''वैरीएबल'''''
 | style="border-right: 1px solid darkgrey; border-left: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
-<math>f_{uv}</math> <math>\forall (u,v)\in E</math> ''[a variable per edge]''
+<math>f_{uv}</math> <math>\forall (u,v)\in E</math> ''[प्रति किनारे वैरीएबल]''
 | style="border-right: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
-<math>d_{uv}</math> <math>\forall (u,v)\in E</math> ''[a variable per edge]''
+<math>d_{uv}</math> <math>\forall (u,v)\in E</math> ''[प्रति किनारे वैरीएबल]''
-<math>z_{v}</math> <math>\forall v\in V\setminus \{s,t\}</math> ''[a variable per non-terminal node]''
+<math>z_{v}</math> <math>\forall v\in V\setminus \{s,t\}</math> ''[प्रति गैर-टर्मिनल नोड वैरीएबल]''
 |-
-|'''objective'''
+|'''उद्देश्य'''
 | style="border-right: 1px solid darkgrey; border-left: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
-maximize <math>\sum\nolimits_{v: (s,v)\in E} f_{sv}</math>
+अधिकतम <math>\sum\nolimits_{v: (s,v)\in E} f_{sv}</math>
-''[max total flow from source]''
+''[स्रोत से अधिकतम कुल प्रवाह]''
 | style="border-right: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
-minimize <math>\sum\nolimits_{(u,v) \in E } c_{uv}d_{uv}</math>
+न्यूनतम <math>\sum\nolimits_{(u,v) \in E } c_{uv}d_{uv}</math>
-''[min total capacity of edges in cut]''
+''[कट में किनारों की न्यूनतम कुल क्षमता]''
 |-
-|'''constraints'''
+|'''प्रतिबंध'''
 | style="border-left: 1px solid darkgrey; border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey; padding: 1em;" valign="top" |
-subject to
+विषय है
 :<math>\begin{align}
@@ Line 97: / Line 95: @@
 \end{align}</math>
-''[a constraint per edge and a constraint per non-terminal node]''
+''[प्रति किनारे बाधा और प्रति गैर-टर्मिनल नोड बाधा]''
 | style="border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey; padding: 1em" valign="top" |
-subject to
+विषय है
 :<math>\begin{align}
@@ Line 108: / Line 106: @@
 \end{align}</math>
-''[a constraint per edge]''
+''[प्रति किनारे बाधा]''
 |-
-|'''sign constraints'''
+|'''sign प्रतिबंध'''
 |<math>\begin{align}
 f_{uv} & \geq 0 && \forall (u, v) \in E\\
@@ Line 119: / Line 117: @@
 \end{align}</math>
 |}
-अधिकतम-प्रवाह एलपी सीधा है। दोहरे एलपी को दोहरे रैखिक कार्यक्रम में वर्णित एल्गोरिदम का उपयोग करके प्राप्त किया जाता है: दोहरे के चर और संकेत बाधाएं प्रारंभिक की बाधाओं के अनुरूप होती हैं, और दोहरे की बाधाएं प्रारंभिक के चर और संकेत बाधाओं के अनुरूप होती हैं। परिणामी एलपी को कुछ स्पष्टीकरण की आवश्यकता है। न्यूनतम-कट एलपी में चर की व्याख्या इस प्रकार है:
+अधिकतम-प्रवाह एलपी सीधा है। दोहरे एलपी को दोहरे रैखिक प्रोग्राम में वर्णित एल्गोरिदम का उपयोग करके प्राप्त किया जाता है: दोहरे के वैरीएबल और संकेत बाधाएं प्रारंभिक की बाधाओं के अनुरूप होती हैं, और दोहरे की बाधाएं प्रारंभिक के वैरीएबल और संकेत बाधाओं के अनुरूप होती हैं। परिणामी एलपी को कुछ स्पष्टीकरण की आवश्यकता है। न्यूनतम-कट एलपी में वैरीएबल की व्याख्या इस प्रकार है:
 :<math>d_{uv} = \begin{cases} 1, & \text{if }u \in S \text{ and } v \in T \text{ (the edge } uv \text{ is in the cut) }
@@ Line 125: / Line 123: @@
 न्यूनतमकरण उद्देश्य कट में निहित सभी किनारों की क्षमता का योग करता है।
-बाधाएँ गारंटी देती हैं कि चर वास्तव में कानूनी कटौती का प्रतिनिधित्व करते हैं:<ref>{{Cite web|url=http://u.cs.biu.ac.il/~rosenfa5/Alg2/LP.ppt|title=एलपी न्यूनतम-कट अधिकतम-प्रवाह प्रस्तुति|last=Keller|first=Orgad}}</ref>
+बाधाएँ गारंT देती हैं कि वैरीएबल वास्तव में नियमबद्ध डिडक्शन का प्रतिनिधित्व करते हैं:<ref>{{Cite web|url=http://u.cs.biu.ac.il/~rosenfa5/Alg2/LP.ppt|title=एलपी न्यूनतम-कट अधिकतम-प्रवाह प्रस्तुति|last=Keller|first=Orgad}}</ref>
-*बाधाएँ <math>d_{uv} - z_u + z_v \geq 0</math> (के बराबर <math>d_{uv} \geq z_u - z_v </math>) गारंटी दें कि, गैर-टर्मिनल नोड्स यू, वी के लिए, यदि यू एस में है और वी टी में है, तो किनारे (यू, वी) को कट में गिना जाता है (<math>d_{uv} \geq 1 </math>).
+*बाधाएँ <math>d_{uv} - z_u + z_v \geq 0</math> (के समान <math>d_{uv} \geq z_u - z_v </math>) गारंT दें कि, गैर-टर्मिनल नोड्स U, v के लिए, यदि U S में है और v T में है, तो किनारे (U, v) को कट (<math>d_{uv} \geq 1 </math>) में गिना जाता है.
-*बाधाएँ <math>d_{sv} + z_v \geq 1</math> (के बराबर <math>d_{sv} \geq 1 - z_v </math>) गारंटी दें कि, यदि v T में है, तो किनारे (s,v) को कट में गिना जाता है (क्योंकि s, S में परिभाषा के अनुसार है)।
+*बाधाएँ <math>d_{sv} + z_v \geq 1</math> (के समान <math>d_{sv} \geq 1 - z_v </math>) गारंT दें कि, यदि v T में है, तो किनारे (s,v) को कट में गिना जाता है (क्योंकि s, S में परिभाषा के अनुसार है)।
-*बाधाएँ <math>d_{ut} - z_u \geq 0</math> (के बराबर <math>d_{ut} \geq z_u </math>) गारंटी दें कि, यदि यू एस में है, तो किनारे (यू, टी) को कट में गिना जाता है (क्योंकि टी टी में परिभाषा के अनुसार है)।
+*बाधाएँ <math>d_{ut} - z_u \geq 0</math> (के समान <math>d_{ut} \geq z_u </math>) गारंT दें कि, यदि U S में है, तो किनारे (U, T) को कट में गिना जाता है (क्योंकि T T में परिभाषा के अनुसार है)।
-ध्यान दें कि, चूंकि यह एक न्यूनतमकरण समस्या है, इसलिए हमें यह गारंटी नहीं देनी है कि कोई किनारा कट में नहीं है - हमें केवल यह गारंटी देनी है कि प्रत्येक किनारा जो कट में होना चाहिए, उद्देश्य फ़ंक्शन में संक्षेपित है।
+ध्यान दें कि, चूंकि यह न्यूनतमकरण समस्या है, इसलिए हमें यह गारंT नहीं देनी है कि कोई किनारा कट में नहीं है - हमें केवल यह गारंT देनी है कि प्रत्येक किनारा जो कट में होना चाहिए, उद्देश्य फ़ंक्शन में संक्षेपित है।
-'अधिकतम-प्रवाह न्यूनतम-कट प्रमेय' में समानता दोहरे रैखिक कार्यक्रम से आती है, जो बताता है कि यदि प्रारंभिक कार्यक्रम में इष्टतम समाधान है, x*, तो दोहरे कार्यक्रम में भी इष्टतम समाधान है, y*, जैसे कि दो समाधानों द्वारा गठित इष्टतम मान बराबर हैं।
+'अधिकतम-प्रवाह न्यूनतम-कट प्रमेय' में समानता दोहरे रैखिक प्रोग्राम से आती है, जो बताता है कि यदि प्रारंभिक प्रोग्राम में इष्टतम समाधान x* है, इस प्रकारतो दोहरे प्रोग्राम में भी इष्टतम समाधान है, जैसे कि दो समाधानों y*, द्वारा गठित इष्टतम मान समान हैं।
 ==आवेदन==
 ===सीडरबाम का अधिकतम प्रवाह प्रमेय===
-{{See also| Cederbaum's maximum flow theorem}}
+{{See also|सीडरबाम का अधिकतम प्रवाह प्रमेय}}
-अधिकतम प्रवाह समस्या को गैर-रेखीय प्रतिरोधी तत्वों से बने नेटवर्क के माध्यम से विद्युत प्रवाह के अधिकतमकरण के रूप में तैयार किया जा सकता है।<ref>{{cite journal|last1=Cederbaum|first1=I.|title=संचार नेटवर्क के इष्टतम संचालन पर|journal=Journal of the Franklin Institute|date=August 1962|volume=274|pages=130-141}}</ref> इस सूत्रीकरण में, धारा की सीमा {{math|&thinsp;''I''<sub>in</sub> }} विद्युत नेटवर्क के इनपुट टर्मिनलों के बीच इनपुट वोल्टेज के रूप में {{math|''V''<sub>in</sub>}} दृष्टिकोण <math>\infty</math>, न्यूनतम-वजन कट सेट के वजन के बराबर है।
+अधिकतम प्रवाह समस्या को गैर-रेखीय प्रतिरोधी अवयवो से बने नेटवर्क के माध्यम से विद्युत प्रवाह के अधिकतमकरण के रूप में तैयार किया जा सकता है।<ref>{{cite journal|last1=Cederbaum|first1=I.|title=संचार नेटवर्क के इष्टतम संचालन पर|journal=Journal of the Franklin Institute|date=August 1962|volume=274|pages=130-141}}</ref> इस सूत्रीकरण में, धारा की सीमा {{math|&thinsp;''I''<sub>in</sub> }} विद्युत नेटवर्क के इनपुट टर्मिनलों के बीच इनपुट वोल्टेज के रूप में {{math|''V''<sub>in</sub>}} दृष्टिकोण <math>\infty</math>, न्यूनतम-वजन कट सेट के वजन के समान है।
 :<math>\lim_{V_{\text{in}} \to \infty} (I_{in})= \min_{X_C}\sum_{(u,v) \in X_C}c_{uv} </math>
@@ Line 144: / Line 143: @@
 ===सामान्यीकृत अधिकतम-प्रवाह न्यूनतम-कट प्रमेय===
-किनारे की क्षमता के अलावा, विचार करें कि प्रत्येक शीर्ष पर क्षमता है, यानी एक मानचित्रण <math>c:V\to\R^+</math> द्वारा चिह्नित {{math|''c''(''v'')}}, ऐसे कि प्रवाह {{math|&thinsp;''f''&thinsp;}} को न केवल क्षमता बाधा और प्रवाह के संरक्षण को संतुष्ट करना होगा, बल्कि शीर्ष क्षमता बाधा को भी पूरा करना होगा
+किनारे की क्षमता के अतिरिक्त, विचार करें कि प्रत्येक शीर्ष पर क्षमता है, अर्थात मानचित्रण <math>c:V\to\R^+</math> द्वारा चिह्नित {{math|''c''(''v'')}}, ऐसे कि प्रवाह {{math|&thinsp;''f''&thinsp;}} को न केवल क्षमता बाधा और प्रवाह के संरक्षण को संतुष्ट करना होता है, किन्तु शीर्ष क्षमता बाधा को भी पूरा करना होता है
 :<math>\forall v \in V \setminus \{s,t\} : \qquad \sum\nolimits_{\{u\in V\mid (u,v)\in E\}} f_{uv} \le c(v).</math>
-दूसरे शब्दों में, किसी शीर्ष से गुजरने वाले प्रवाह की मात्रा उसकी क्षमता से अधिक नहीं हो सकती। एक एस-टी कट को शीर्षों और किनारों के सेट के रूप में परिभाषित करें, जैसे कि एस से टी तक किसी भी पथ के लिए, पथ में कट का एक सदस्य शामिल हो। इस मामले में, कट की क्षमता इसमें प्रत्येक किनारे और शीर्ष की क्षमता का योग है।
+दूसरे शब्दों में, किसी शीर्ष से निकलने वाले प्रवाह की मात्रा उसकी क्षमता से अधिक नहीं हो सकती है। S-T कट को शीर्षों और किनारों के सेट के रूप में परिभाषित करें, जैसे कि S से T तक किसी भी पथ के लिए, पथ में कट का सदस्य सम्मिलित होता है। इस स्थिति में, कट की क्षमता इसमें प्रत्येक किनारे और शीर्ष की क्षमता का योग है।
-इस नई परिभाषा में, 'सामान्यीकृत अधिकतम-प्रवाह न्यूनतम-कट प्रमेय' बताता है कि एक एस-टी प्रवाह का अधिकतम मूल्य नए अर्थ में एक एस-टी कट की न्यूनतम क्षमता के बराबर है।
+इस नई परिभाषा में, 'सामान्यीकृत अधिकतम-प्रवाह न्यूनतम-कट प्रमेय' बताता है कि S-T प्रवाह का अधिकतम मूल्य नए अर्थ में S-T कट की न्यूनतम क्षमता के समान है।
 ===मेंजर का प्रमेय===
-{{See also| Menger's Theorem}}
+{{See also|मेन्जर का प्रमेय}}
-अप्रत्यक्ष किनारे-असंयुक्त पथ समस्या में, हमें एक अप्रत्यक्ष ग्राफ़ दिया गया है {{math|''G'' {{=}} (''V'', ''E'')}} और दो शीर्ष {{mvar|s}} और {{mvar|t}}, और हमें किनारे-विसंयुक्त एस-टी पथों की अधिकतम संख्या ढूंढनी होगी {{mvar|G}}.
+अप्रत्यक्ष किनारे-विच्छेद पथ समस्या में, हमें अप्रत्यक्ष ग्राफ {{math|''G'' {{=}} (''V'', ''E'')}} और दो शीर्ष {{mvar|s}} और {{mvar|t}} दिए गए हैं, और हमें {{mvar|G}} में किनारे-विच्छेदित s-t पथों की अधिकतम संख्या ज्ञात करनी है।
-मेन्जर के प्रमेय में कहा गया है कि एक अप्रत्यक्ष ग्राफ में किनारे-असंयुक्त सेंट पथों की अधिकतम संख्या एक सेंट कट-सेट में किनारों की न्यूनतम संख्या के बराबर है।
+मेन्जर के प्रमेय में कहा गया है कि अप्रत्यक्ष ग्राफ में किनारे-असंयुक्त सेंट पथों की अधिकतम संख्या सेंट कट-सेट में किनारों की न्यूनतम संख्या के समान है।
 ===प्रोजेक्ट चयन समस्या===
-[[File:Max-flow min-cut project-selection.svg|thumb|right|इष्टतम समाधान के साथ परियोजना चयन समस्या का एक नेटवर्क सूत्रीकरण]]परियोजना चयन समस्या में, हैं {{mvar|n}} परियोजनाएं और {{mvar|m}} मशीनें. प्रत्येक परियोजना {{mvar|p<sub>i</sub>}} राजस्व प्राप्त होता है {{math|''r''(''p<sub>i</sub>'')}} और प्रत्येक मशीन {{mvar|q<sub>j</sub>}} लागत {{math|''c''(''q<sub>j</sub>'')}} खरीदने के लिए। प्रत्येक परियोजना के लिए कई मशीनों की आवश्यकता होती है और प्रत्येक मशीन को कई परियोजनाओं द्वारा साझा किया जा सकता है। समस्या यह निर्धारित करने की है कि किन परियोजनाओं और मशीनों को क्रमशः चुना और खरीदा जाना चाहिए, ताकि लाभ अधिकतम हो।
+[[File:Max-flow min-cut project-selection.svg|thumb|right|इष्टतम समाधान के साथ परियोजना चयन समस्या का नेटवर्क सूत्रीकरण]]
-होने देना {{mvar|P}} चयनित न की गई परियोजनाओं का सेट हो और {{mvar|Q}} खरीदी गई मशीनों का सेट हो, तो समस्या को इस प्रकार तैयार किया जा सकता है,
+प्रोजेक्ट चयन समस्या में, {{mvar|n}} प्रोजेक्ट और {{mvar|m}} मशीनें हैं। प्रत्येक प्रोजेक्ट {{mvar|p<sub>i</sub>}} आय {{math|''r''(''p<sub>i</sub>'')}} उत्पन्न करता है और प्रत्येक मशीन {{mvar|q<sub>j</sub>}} को खरीदने में {{math|''c''(''q<sub>j</sub>'')}} व्यय होता है। प्रत्येक परियोजना के लिए अनेक मशीनों की आवश्यकता होती है और प्रत्येक मशीन को अनेक परियोजनाओं द्वारा साझा किया जा सकता है। समस्या यह निर्धारित करने की है कि किन परियोजनाओं और मशीनों को क्रमशः चुना और खरीदा जाना चाहिए जिससे लाभ अधिकतम होता है।
+मान लीजिए कि {{mvar|P}} उन परियोजनाओं का सेट है जिनका चयन नहीं किया गया है और {{mvar|Q}} खरीदी गई मशीनों का सेट है, तो समस्या को इस प्रकार तैयार किया जा सकता है,
 :<math>\max \{g\} = \sum_{i} r(p_i) - \sum_{p_i \in P} r(p_i) - \sum_{q_j \in Q} c(q_j).</math>
-चूँकि पहला पद की पसंद पर निर्भर नहीं करता है {{mvar|P}} और {{mvar|Q}}, इस अधिकतमीकरण समस्या को इसके बजाय न्यूनतमकरण समस्या के रूप में तैयार किया जा सकता है, अर्थात,
+चूँकि पहला पद {{mvar|P}} और {{mvar|Q}} की पसंद पर निर्भर नहीं करता है, इसलिए इस अधिकतमीकरण समस्या को इसके अतिरिक्त न्यूनतमकरण समस्या के रूप में तैयार किया जा सकता है। अर्थात,
 :<math>\min \{g'\} = \sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j).</math>
-उपरोक्त न्यूनतमकरण समस्या को एक नेटवर्क का निर्माण करके न्यूनतम-कट समस्या के रूप में तैयार किया जा सकता है, जहां स्रोत क्षमता वाली परियोजनाओं से जुड़ा होता है {{math|''r''(''p<sub>i</sub>'')}}, और सिंक को क्षमता वाली मशीनों द्वारा जोड़ा जाता है {{math|''c''(''q<sub>j</sub>'')}}. एक किनारा {{math|(''p<sub>i</sub>'', ''q<sub>j</sub>'')}} यदि प्रोजेक्ट में अनंत क्षमता जोड़ी जाती है {{mvar|p<sub>i</sub>}}मशीन की आवश्यकता है {{mvar|q<sub>j</sub>}}. एस-टी कट-सेट परियोजनाओं और मशीनों का प्रतिनिधित्व करता है {{mvar|P}} और {{mvar|Q}} क्रमश। अधिकतम-प्रवाह न्यूनतम-कट प्रमेय द्वारा, कोई समस्या को [[अधिकतम प्रवाह समस्या]] के रूप में हल कर सकता है।
+उपरोक्त न्यूनतमकरण समस्या को नेटवर्क का निर्माण करके न्यूनतम-कट समस्या के रूप में तैयार किया जा सकता है, जहां स्रोत क्षमता {{math|''r''(''p<sub>i</sub>'')}} वाली परियोजनाओं से जुड़ा है, और सिंक क्षमता {{math|''c''(''q<sub>j</sub>'')}} वाली मशीनों से जुड़ा है। यदि प्रोजेक्ट {{mvar|p<sub>i</sub>}} को मशीन {{mvar|q<sub>j</sub>}} की आवश्यकता होती है तो अनंत क्षमता वाला किनारा {{math|(''p<sub>i</sub>'', ''q<sub>j</sub>'')}} जोड़ा जाता है। S-T कट-सेट क्रमशः {{mvar|P}} और {{mvar|Q}} में परियोजनाओं और मशीनों का प्रतिनिधित्व करता है। अधिकतम-प्रवाह न्यूनतम-कट प्रमेय द्वारा, कोई समस्या को अधिकतम प्रवाह समस्या के रूप में हल कर सकता है।
 दाईं ओर का चित्र निम्नलिखित परियोजना चयन समस्या का नेटवर्क सूत्रीकरण देता है:
@@ Line 174: / Line 179: @@
 ! width="20px" |
 ! width="100px" |
-Project {{math|''r''(''p<sub>i</sub>'')}}
+प्रोजेक्ट{{math|''r''(''p<sub>i</sub>'')}}
 ! width="100px" |
-Machine {{math|''c''(''q<sub>j</sub>'')}}
+मशीन {{math|''c''(''q<sub>j</sub>'')}}
 !
 |-
@@ Line 182: / Line 187: @@
 | 100 || 200
 | align="left" style="padding-left: 1em;" |
-Project 1 requires machines 1 and 2.
+प्रोजेक्ट1 आवश्यक मशीन 1 और 2.
 |-
 ! 2
 | 200 || 100
 | align="left" style="padding-left: 1em;" |
-Project 2 requires machine 2.
+प्रोजेक्ट2 आवश्यक मशीन 2.
 |-
 ! 3
 | 150 || 50
 | align="left" style="padding-left: 1em;" |
-Project 3 requires machine 3.
+प्रोजेक्ट3 आवश्यक मशीन 3.
 |}
-एस-टी कट की न्यूनतम क्षमता 250 है और प्रत्येक परियोजना के राजस्व का योग 450 है; इसलिए परियोजनाओं का चयन करके अधिकतम लाभ g 450 - 250 = 200 है {{math|''p''<sub>2</sub>}} और {{math|''p''<sub>3</sub>}}.
-यहां विचार प्रत्येक परियोजना के मुनाफे को उसकी मशीनों के 'पाइप' के माध्यम से 'प्रवाह' करने का है। यदि हम किसी मशीन से पाइप नहीं भर सकते हैं, तो मशीन का रिटर्न उसकी लागत से कम है, और न्यूनतम कटौती एल्गोरिदम को मशीन की लागत बढ़त के बजाय परियोजना की लाभ बढ़त में कटौती करना सस्ता लगेगा।
+S-T कट की न्यूनतम क्षमता 250 है और प्रत्येक परियोजना के राजस्व का योग 450 है; इसलिए प्रोजेक्ट {{math|''p''<sub>2</sub>}} और {{math|''p''<sub>3</sub>}}. का चयन करके अधिकतम लाभ g 450 - 250 = 200 है।
+यहां विचार प्रत्येक परियोजना के लाभ को उसकी मशीनों के 'पाइप' के माध्यम से 'प्रवाह' करने का है। यदि हम किसी मशीन से पाइप नहीं भर सकते हैं, जिससे मशीन का रिटर्न उसकी निवेश से कम है, और न्यूनतम डिडक्शन एल्गोरिदम को मशीन की निवेश बढ़त के अतिरिक्त परियोजना की लाभ बढ़त में डिडक्शन करना होता है ।
 ===छवि विभाजन समस्या===
-{{See also|Maximum flow problem}}
+{{See also|अधिकतम प्रवाह समस्या}}
-[[File:Image segmentation.jpg|thumb|प्रत्येक काला नोड एक पिक्सेल को दर्शाता है।]]छवि विभाजन समस्या में, हैं {{mvar|n}} पिक्सल। प्रत्येक पिक्सेल {{mvar|i}} को अग्रभूमि मान निर्दिष्ट किया जा सकता है {{mvar|&thinsp;f<sub>i</sub>}} या पृष्ठभूमि मान {{mvar|b<sub>i</sub>}}. का जुर्माना है {{mvar|p<sub>ij</sub>}} यदि पिक्सेल {{mvar|i, j}} आसन्न हैं और उनके अलग-अलग कार्य हैं। समस्या यह है कि पिक्सेल को अग्रभूमि या पृष्ठभूमि में इस प्रकार निर्दिष्ट किया जाए कि उनके मानों का योग शून्य से दंड अधिकतम हो।
+[[File:Image segmentation.jpg|thumb|प्रत्येक काला नोड पिक्सेल को दर्शाता है।]]
+छवि विभाजन समस्या में, {{mvar|n}} पिक्सेल हैं। प्रत्येक पिक्सेल {{mvar|i}} को अग्रभूमि मान {{mvar|&thinsp;f<sub>i</sub>}} या पृष्ठभूमि मान {{mvar|b<sub>i</sub>}} निर्दिष्ट किया जा सकता है। यदि पिक्सेल {{mvar|p<sub>ij</sub>}} आसन्न हैं और उनके भिन्न-भिन्न कार्य हैं तो {{mvar|i, j}} का दंड है। समस्या यह है कि पिक्सेल को अग्रभूमि या पृष्ठभूमि में इस प्रकार निर्दिष्ट किया जाए कि उनके मानों का योग शून्य से दंड अधिकतम हो।
-होने देना {{mvar|P}} अग्रभूमि को निर्दिष्ट पिक्सेल का सेट बनें और {{mvar|Q}} पृष्ठभूमि को निर्दिष्ट बिंदुओं का सेट हो, तो समस्या को इस प्रकार तैयार किया जा सकता है,
+मन लीजिए {{mvar|P}} अग्रभूमि को निर्दिष्ट पिक्सेल का सेट बनें और {{mvar|Q}} पृष्ठभूमि को निर्दिष्ट बिंदुओं का सेट हो, तो समस्या को इस प्रकार तैयार किया जा सकता है,
 : <math>\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}.</math>
-इस अधिकतमीकरण समस्या को इसके बजाय न्यूनतमकरण समस्या के रूप में तैयार किया जा सकता है, अर्थात,
+इस अधिकतमीकरण समस्या को इसके अतिरिक्त न्यूनतमकरण समस्या के रूप में तैयार किया जा सकता है, अर्थात,
 : <math>\min \{g'\} = \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}.</math>
-उपरोक्त न्यूनतमकरण समस्या को एक नेटवर्क का निर्माण करके न्यूनतम-कट समस्या के रूप में तैयार किया जा सकता है जहां स्रोत (नारंगी नोड) क्षमता वाले सभी पिक्सेल से जुड़ा हुआ है {{mvar|&thinsp;f<sub>i</sub>}}, और सिंक (बैंगनी नोड) क्षमता वाले सभी पिक्सेल से जुड़ा हुआ है {{mvar|b<sub>i</sub>}}. दो किनारे ({{mvar|i, j}}) और ({{mvar|j, i}}) साथ {{mvar|p<sub>ij</sub>}} क्षमता दो आसन्न पिक्सेल के बीच जोड़ी जाती है। एस-टी कट-सेट तब अग्रभूमि में निर्दिष्ट पिक्सेल का प्रतिनिधित्व करता है {{mvar|P}} और पिक्सल को पृष्ठभूमि में असाइन किया गया है {{mvar|Q}}.
+उपरोक्त न्यूनतमकरण समस्या को नेटवर्क का निर्माण करके न्यूनतम-कट समस्या के रूप में तैयार किया जा सकता है जहां स्रोत (नारंगी नोड) क्षमता {{mvar|&thinsp;f<sub>i</sub>}} वाले सभी पिक्सल से जुड़ा हुआ है, और सिंक (बैंगनी नोड) क्षमता द्वि के साथ सभी पिक्सल से जुड़ा हुआ है पीज क्षमता वाले दो किनारे ({{mvar|i, j}}) और ({{mvar|j, i}}) दो आसन्न पिक्सेल के बीच जोड़े जाते हैं। एस-टी कट-सेट तब {{mvar|p<sub>ij</sub>}} में अग्रभूमि को निर्दिष्ट पिक्सेल और {{mvar|Q}} में पृष्ठभूमि को निर्दिष्ट पिक्सेल का प्रतिनिधित्व करता है।
 ==इतिहास==
-प्रमेय की खोज का विवरण एल. आर. फोर्ड जूनियर और डी. आर. फुलकर्सन द्वारा 1962 में दिया गया था:<ref>[[L. R. Ford Jr.]] & [[D. R. Fulkerson]] (1962) ''Flows in Networks'', page 1, [[Princeton University Press]] {{mr|id=0159700}}</ref>
+प्रमेय की खोज का विवरण एल. आर. फोर्ड जूनियर और डी. आर. फुलकर्सन द्वारा 1962 में दिया गया था:<ref>[[L. R. Ford Jr.]] & [[D. R. Fulkerson]] (1962) ''Flows in Networks'', page 1, [[Princeton University Press]] {{mr|id=0159700}}</ref> आर्क्स पर क्षमता सीमाओं के अधीन नेटवर्क में बिंदु से दूसरे बिंदु तक अधिकतम स्थिर स्थिति प्रवाह का निर्धारण ... 1955 के वसंत में टी.ई. द्वारा लेखकों के सामने रखा गया था। हैरिस, जिन्होंने जनरल एफ.एस. रॉस (सेवानिवृत्त) के साथ मिलकर रेलवे यातायात प्रवाह का सरलीकृत मॉडल तैयार किया था, और इस विशेष समस्या को मॉडल द्वारा सुझाई गई केंद्रीय समस्या के रूप में संकेत किया था। इसके पश्चात् अधिक समय नहीं बीता जब मुख्य परिणाम, प्रमेय 5.1, जिसे हम अधिकतम-प्रवाह न्यूनतम-कट प्रमेय कहते हैं, जिसका अनुमान लगाया गया और स्थापित किया गया था।<ref>L. R. Ford Jr. and D. R. Fulkerson (1956) "Maximal flow through a network", [[Canadian Journal of Mathematics]] 8: 399-404</ref> तब से अनेक प्रमाण सामने आए हैं।<ref>P. Elias, A. Feinstein, and C. E. Shannon (1956) "A note on the maximum flow through a network", IRE. Transactions on Information Theory, 2(4): 117–119</ref><ref>[[George Dantzig]] and D. R. Fulkerson (1956) "On the Max-Flow MinCut Theorem of Networks", in ''Linear Inequalities'', Ann. Math. Studies, no. 38, Princeton, New Jersey</ref><ref>L. R. Ford & D. R. Fulkerson (1957) "A simple algorithm for finding the maximum network flows and an application to the Hitchcock problem", ''Canadian Journal of Mathematics'' 9: 210–18</ref>
-आर्क्स पर क्षमता सीमाओं के अधीन नेटवर्क में एक बिंदु से दूसरे बिंदु तक अधिकतम स्थिर स्थिति प्रवाह का निर्धारण ... 1955 के वसंत में टी.ई. द्वारा लेखकों के सामने रखा गया था। हैरिस, जिन्होंने जनरल एफ.एस. रॉस (सेवानिवृत्त) के साथ मिलकर रेलवे यातायात प्रवाह का एक सरलीकृत मॉडल तैयार किया था, और इस विशेष समस्या को मॉडल द्वारा सुझाई गई केंद्रीय समस्या के रूप में इंगित किया था। इसके बाद ज्यादा समय नहीं बीता जब मुख्य परिणाम, प्रमेय 5.1, जिसे हम अधिकतम-प्रवाह न्यूनतम-कट प्रमेय कहते हैं, का अनुमान लगाया गया और स्थापित किया गया।<ref>L. R. Ford Jr. and D. R. Fulkerson (1956) "Maximal flow through a network", [[Canadian Journal of Mathematics]] 8: 399-404</ref> तब से कई सबूत सामने आए हैं।<ref>P. Elias, A. Feinstein, and C. E. Shannon (1956) "A note on the maximum flow through a network", IRE. Transactions on Information Theory, 2(4): 117–119</ref><ref>[[George Dantzig]] and D. R. Fulkerson (1956) "On the Max-Flow MinCut Theorem of Networks", in ''Linear Inequalities'', Ann. Math. Studies, no. 38, Princeton, New Jersey</ref><ref>L. R. Ford & D. R. Fulkerson (1957) "A simple algorithm for finding the maximum network flows and an application to the Hitchcock problem", ''Canadian Journal of Mathematics'' 9: 210–18</ref>
 ==प्रमाण==
-होने देना {{math|''G'' {{=}} (''V'', ''E'')}} के साथ एक नेटवर्क (निर्देशित ग्राफ़) बनें {{mvar|s}} और {{mvar|t}} का स्रोत और सिंक होना {{mvar|G}} क्रमश।
+मान लीजिए {{math|''G'' {{=}} (''V'', ''E'')}} नेटवर्क (निर्देशित ग्राफ) है जिसमें {{mvar|s}} और {{mvar|t}} क्रमशः {{mvar|G}} का स्रोत और सिंक हैं।
-प्रवाह पर विचार करें {{math|&thinsp;''f''&thinsp;}} के लिए गणना की गई {{mvar|G}} फोर्ड-फ़ल्कर्सन एल्गोरिथम द्वारा। अवशिष्ट ग्राफ में {{math|(''G<sub>f</sub>''&thinsp;)}} के लिए प्राप्त किया गया {{mvar|G}} (फोर्ड-फुलकर्सन एल्गोरिदम द्वारा अंतिम प्रवाह असाइनमेंट के बाद), शीर्षों के दो उपसमूहों को निम्नानुसार परिभाषित करें:
+फोर्ड-फ़ल्कर्सन एल्गोरिथम द्वारा {{mvar|G}} के लिए परिकलित प्रवाह {{math|&thinsp;''f''&thinsp;}} पर विचार करें। {{mvar|G}} के लिए प्राप्त अवशिष्ट ग्राफ {{math|(''G<sub>f</sub>''&thinsp;)}} में (फोर्ड-फुलकर्सन एल्गोरिदम द्वारा अंतिम प्रवाह असाइनमेंट के पश्चात्), शीर्षों के दो उपसमूहों को निम्नानुसार परिभाषित करें:
-# {{mvar|A}}: से पहुंच योग्य शीर्षों का सेट {{mvar|s}} में {{mvar|G<sub>f</sub>}}
+#{{mvar|A}}: {{mvar|G<sub>f</sub>}} में {{mvar|s}} से पहुंच योग्य शीर्षों का समुच्चय
 # {{mvar|A<sup>c</sup>}}: शेष शीर्षों का समुच्चय अर्थात {{mvar|V − A}}
-दावा करना। {{math|value(&thinsp;''f''&thinsp;) {{=}} ''c''(''A'', ''A<sup>c</sup>'')}}, जहां ''एस-टी कट'' की क्षमता को परिभाषित किया गया है
+प्रमाण मूल्य {{math|value(&thinsp;''f''&thinsp;) {{=}} ''c''(''A'', ''A<sup>c</sup>'')}} जहां ''S-T'' कट की क्षमता को परिभाषित किया गया है
 :<math>c(S,T) = \sum\nolimits_{(u,v) \in S \times T} c_{uv}</math>.
-अब, हम जानते हैं, <math>value(f) = f_{out}(A) - f_{in}(A)</math> शीर्षों के किसी उपसमुच्चय के लिए, {{mvar|A}}. इसलिए, के लिए {{math|value(&thinsp;''f''&thinsp;) {{=}} ''c''(''A'', ''A<sup>c</sup>'')}} ज़रुरत है:
+अब, हम शीर्षों के किसी उपसमुच्चय, {{mvar|A}} के लिए <math>value(f) = f_{out}(A) - f_{in}(A)</math> जानते हैं। इसलिए, {{math|value(&thinsp;''f''&thinsp;) {{=}} ''c''(''A'', ''A<sup>c</sup>'')}} के लिए हमें चाहिए:
 * कट से निकलने वाले सभी किनारे 'पूरी तरह से संतृप्त' होने चाहिए।
 * कट के सभी आने वाले किनारों में 'शून्य प्रवाह' होना चाहिए।
-उपरोक्त दावे को साबित करने के लिए हम दो मामलों पर विचार करते हैं:
+उपरोक्त प्रमाण को सिद्ध करने के लिए हम दो स्थितियों पर विचार करते हैं:
-*में {{mvar|G}}, एक आउटगोइंग एज मौजूद है <math>(x,y), x \in A, y \in A^c</math> ऐसा कि यह संतृप्त नहीं है, यानी, {{math|&thinsp;''f''&thinsp;(''x'', ''y'') < ''c<sub>xy</sub>''}}. इसका तात्पर्य यह है कि आगे की ओर एक किनारा मौजूद है {{mvar|x}} को {{mvar|y}} में {{mvar|G<sub>f</sub>}}, इसलिए वहां से एक रास्ता मौजूद है {{mvar|s}} को {{mvar|y}} में {{mvar|G<sub>f</sub>}}, जो एक विरोधाभास है। इसलिए, कोई भी आउटगोइंग एज {{math|(''x'', ''y'')}} पूर्णतः संतृप्त है।
+*{{mvar|G}} में, आउटगोइंग एज उपस्थित है <math>(x,y), x \in A, y \in A^c</math> ऐसा कि यह संतृप्त नहीं है, अर्थात, {{math|&thinsp;''f''&thinsp;(''x'', ''y'') < ''c<sub>xy</sub>''}}. इसका तात्पर्य यह है कि {{mvar|G<sub>f</sub>}} में {{mvar|x}} को {{mvar|y}} तक आगे का किनारा उपस्थित है, इसलिए {{mvar|G<sub>f</sub>}} में {{mvar|s}} को {{mvar|y}} तक पथ उपस्थित है, जो विरोधाभास है। इसलिए, कोई भी आउटगोइंग किनारा {{math|(''x'', ''y'')}} पूरी तरह से संतृप्त है।
-*में {{mvar|G}}, एक आने वाली बढ़त मौजूद है <math>(y,x), x \in A, y \in A^c</math> ऐसा कि इसमें कुछ गैर-शून्य प्रवाह होता है, यानी, {{math|&thinsp;''f''&thinsp;(''y'', ''x'') > 0}}. इसका तात्पर्य यह है कि वहाँ से एक पिछड़ा किनारा मौजूद है {{mvar|x}} को {{mvar|y}} में {{mvar|G<sub>f</sub>}}, इसलिए वहां से एक रास्ता मौजूद है {{mvar|s}} को {{mvar|y}} में {{mvar|G<sub>f</sub>}}, जो फिर से एक विरोधाभास है। इसलिए, कोई भी आने वाली बढ़त {{math|(''y'', ''x'')}} शून्य प्रवाह होना चाहिए.
+*में {{mvar|G}}, आने वाली बढ़त उपस्थित है <math>(y,x), x \in A, y \in A^c</math> ऐसा कि इसमें कुछ गैर-शून्य प्रवाह होता है, अर्थात, {{math|&thinsp;''f''&thinsp;(''y'', ''x'') > 0}}. इसका तात्पर्य यह है कि वहाँ से पिछड़ा किनारा उपस्थित है {{mvar|x}} को {{mvar|y}} में {{mvar|G<sub>f</sub>}}, इसलिए वहां से रास्ता उपस्थित है {{mvar|s}} को {{mvar|y}} में {{mvar|G<sub>f</sub>}}, जो फिर से विरोधाभास है। इसलिए, कोई भी आने वाली बढ़त {{math|(''y'', ''x'')}} शून्य प्रवाह होना चाहिए.
-उपरोक्त दोनों कथन यह साबित करते हैं कि ऊपर वर्णित तरीके से प्राप्त कट की क्षमता नेटवर्क में प्राप्त प्रवाह के बराबर है। साथ ही, प्रवाह [[फोर्ड-फ़ल्कर्सन एल्गोरिथम]] द्वारा प्राप्त किया गया था, इसलिए यह नेटवर्क का अधिकतम-प्रवाह भी है।
+उपरोक्त दोनों कथन यह सिद्ध करते हैं कि ऊपर वर्णित विधि से प्राप्त कट की क्षमता नेटवर्क में प्राप्त प्रवाह के समान है। साथ ही, प्रवाह [[फोर्ड-फ़ल्कर्सन एल्गोरिथम]] द्वारा प्राप्त किया गया था, इसलिए यह नेटवर्क का अधिकतम-प्रवाह भी है।
-इसके अलावा, चूंकि नेटवर्क में कोई भी प्रवाह हमेशा नेटवर्क में संभव प्रत्येक कट की क्षमता से कम या उसके बराबर होता है, ऊपर वर्णित कट भी न्यूनतम-कट है जो अधिकतम-प्रवाह प्राप्त करता है।
+इसके अतिरिक्त, चूंकि नेटवर्क में कोई भी प्रवाह सदैव नेटवर्क में संभव प्रत्येक कट की क्षमता से कम या उसके समान होता है, ऊपर वर्णित कट भी न्यूनतम-कट है जो अधिकतम-प्रवाह प्राप्त करता है।
-इस प्रमाण से एक परिणाम यह है कि ग्राफ़ के कट में किनारों के किसी भी सेट के माध्यम से [[अधिकतम प्रवाह]] पिछले सभी कटों की न्यूनतम क्षमता के बराबर है।
+इस प्रमाण से परिणाम यह है कि ग्राफ़ के कट में किनारों के किसी भी सेट के माध्यम से [[अधिकतम प्रवाह]] पिछले सभी कटों की न्यूनतम क्षमता के समान है।
-==यह भी देखें==
+==यह भी देखें                                                             ==
 * [[जीएनआरएस अनुमान]]
 * रैखिक प्रोग्रामिंग
 * [[अधिकतम प्रवाह]]
-*न्यूनतम कटौती
+*न्यूनतम डिडक्शन
-* प्रवाह नेटवर्क
+* फ्लो नेटवर्क
 * एडमंड्स-कार्प एल्गोरिथम
 * फोर्ड-फ़ल्कर्सन एल्गोरिथम
@@ Line 252: / Line 257: @@
 * मेन्जर का प्रमेय
-==संदर्भ==
+==संदर्भ                                                                                                                                                                                                                  ==
 {{reflist}}
 * {{cite book|author=Eugene Lawler | author-link = Eugene Lawler|title = Combinatorial Optimization: Networks and Matroids | chapter = 4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem | year = 2001 | publisher = Dover | isbn = 0-486-41453-1 | pages = 117–120}}
 * {{cite book|author=[[Christos H. Papadimitriou]], [[Kenneth Steiglitz]]|title=Combinatorial Optimization: Algorithms and Complexity | chapter=6.1 The Max-Flow, Min-Cut Theorem | year = 1998| publisher = Dover | isbn = 0-486-40258-4 |pages= 120–128}}
 * {{cite book|author=[[Vijay Vazirani|Vijay V. Vazirani]]|title=Approximation Algorithms|chapter=12. Introduction to LP-Duality | year = 2004 | publisher = Springer | isbn = 3-540-65367-8 | pages = 93–100}}
-[[Category: संयुक्त अनुकूलन]] [[Category: ग्राफ सिद्धांत में प्रमेय]] [[Category: नेटवर्क प्रवाह समस्या]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
 [[Category:Created On 26/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:ग्राफ सिद्धांत में प्रमेय]]
+[[Category:नेटवर्क प्रवाह समस्या]]
+[[Category:संयुक्त अनुकूलन]]

Anonymous

Search

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

Latest revision as of 15:38, 8 September 2023

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

नेटवर्क

प्रवाह

डिडक्शन

मुख्य प्रमेय

उदाहरण

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

आवेदन

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

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

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

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

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

इतिहास

प्रमाण

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories