प्रवाह नेटवर्क: Difference between revisions

Revision as of 13:34, 20 February 2023

आरेख सिद्धांत में, प्रवाह तंत्र जिसे परिवहन तंत्र के रूप में भी जाना जाता है, एक निर्देशित आरेख है जहां प्रत्येक भुजा की कुछ क्षमता होती है और प्रत्येक भुजा को प्रवाह प्राप्त होता है। भुजाओं पर प्रवाह की मात्रा उसकी क्षमता से अधिक नहीं हो सकती। प्रायः संचालन अनुसंधान में, निर्देशित आरेख को तंत्र कहा जाता है, शीर्षों को नोड कहा जाता है और भुजाऑ को चाप कहा जाता है। प्रवाह को इस प्रतिबंध को स्थापित करना चाहिए कि नोड के भीतर प्रवाह की मात्रा इसके बाहर प्रवाह की मात्रा के बराबर हों, जब तक कि नोड कोई स्रोत या कुंड(सिंक) न हो। तंत्र का उपयोग कंप्यूटर तंत्र में ट्रैफ़िक, मांगों के साथ परिसंचरण, नलिकाओं में तरल पदार्थ, विद्युत परिपथ में धाराओं, या कुछ इसी तरह के नोड्स के तंत्र के माध्यम से यात्रा करने के लिए किया जा सकता है।

परिभाषा

तंत्र एक निर्देशित आरेख G = (V, E) है जिसमें प्रत्येक भुजाओं के लिए एक गैर-ऋणात्मक क्षमता फलन c है और एक ही स्रोत और लक्ष्य नोड्स वाली चाँपरहित भुजाये हैं। सामान्यीकरण के हानी के बिना, हम यह मान सकते हैं कि यदि $(u, v) \in E$ है तब $(v, u)$ भी $E$ का सदस्य है इसके अतिरिक्त, यदि $(v, u) \notin E$ तो हम $(v, u)$ को $E$ में जोड़ सकते हैं और फिर $c (v, u) = 0$ .समायोजित कर सकते हैं।

यदि $G$ में दो नोड्स विभेदित हैं - स्रोत के रूप में $s$ और सिंक के रूप में $t$ - तब $(G, c, s, t)$ को प्रवाह तंत्र कहा जाता है।^[1]

प्रवाह

प्रवाह फलन, नोड्स के युग्मों के मध्य इकाइयों के शुद्ध प्रवाह को प्रारूपित करते हैं, और प्रश्न पूछते समय उपयोगी होते हैं जैसे कि इकाइयों की अधिकतम संख्या क्या है जो स्रोत नोड एस से सिंक नोड टी में स्थानांतरित की जा सकती है? दो नोड्स के मध्य प्रवाह की मात्रा का उपयोग एक नोड से दूसरे नोड में स्थानांतरित होने वाली इकाइयों की शुद्ध मात्रा का प्रतिनिधित्व करने के लिए किया जाता है।

अधिशेष फलन $\mathbb {R}$ किसी दिए गए नोड $u$ में प्रवेश करने वाले शुद्ध प्रवाह को संदर्भित करता है और

x_{f}(u)=\sum _{w\in V}f(w,u).

द्वारा परिभाषित किया गया है किसी नोड

u

यदि

x f (u) > 0

अर्थात नोड

u

प्रवाह को ग्रहण करता है तों इसे सक्रिय कहा जाएगा, यदि

x f (u) < 0

अर्थात नोड

u

प्रवाह का उत्पादन करता है तों इसे अपूर्ण कहा जाएगा और यदि

x f (u) = 0

है तों इसे सरक्षक कहा जाएगा। प्रवाह तंत्र में, स्रोत

s

अपूर्ण है, और कुंड

t

सक्रिय है।

आभासी प्रवाह, व्यवहार्य प्रवाह और पूर्व प्रवाह सभी प्रवाह फलनों के उदाहरण हैं।

आभासी प्रवाह तंत्र में प्रत्येक भुजा का फलन f है जो सभी नोड्स यू और वी के लिए निम्नलिखित दो बाधाओं को पूरा करता है

तिर्यक् समरूपता बाधा: चाप पर u से v तक का प्रवाह चाप पर v से u तक के प्रवाह के निषेध के बराबर है, अर्थात: f (u, v) = -f (v, u). प्रवाह का संकेत प्रवाह की दिशा को इंगित करता है।
क्षमता बाधा: चाप का प्रवाह उसकी क्षमता से अधिक नहीं हो सकता है, अर्थात: $f (u, v) \leq c (u, v)$ .

पूर्व-प्रवाह एक आभासी प्रवाह है, जो सभी

v ∈ V \{s

} के लिए अतिरिक्त बाधा को पूरा करता है:

गैर-अपूर्ण प्रवाह: नोड में प्रवेश करने वाला शुद्ध प्रवाह $v$ , प्रवाह उत्पन्न करने वाले स्रोत को छोड़कर गैर-ऋणात्मक है। वह $v ∈ V \{s$ } के लिए $x f (v) \geq 0$ है .

व्यवहार्य प्रवाह, एक आभासी प्रवाह है, जो सभी

v ∈ V \{s, t

},के लिए अतिरिक्त बाधा को पूरा करता है:

* प्रवाह संरक्षण बाधा: किसी नोड

v

में प्रवेश करने वाला कुल शुद्ध प्रवाह, स्रोत

s

और सिंक

t

को छोड़कर, तंत्र में सभी नोड्स के लिए शून्य है जो सभी

v ∈ V \{s, t}

के लिए

x f (v) = 0

है . दूसरे शब्दों में, स्रोत

s

और सिंक

t

, को छोड़कर तंत्र में सभी नोड्स के लिए किसी नोड से आने वाले प्रवाह का कुल योग इसके बर्हिगामी प्रवाह के बराबर होता है

अर्थात प्रत्येक शीर्ष

v ∈ V \{s, t}

के लिए

\sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)

है।.

व्यवहार्य प्रवाह f का मान तंत्र | f | के लिए एक प्रवाह तंत्र के सिंक t में शुद्ध प्रवाह है, अर्थात: | f | = x_f (t)। ध्यान दें, तंत्र में प्रवाह मान भी स्रोत $s$ के सभी बहिर्गामी प्रवाह के बराबर होता है जो $| f | = - x f (s)$ है। इसके अतिरिक्त, यदि हम $A$ को नोड्स $G$ के एक समुच्चय के रूप में इस प्रकार परिभाषित करते हैं कि $s \in A$ और $t \notin A$ तो प्रवाह मान, A से बाहर जाने वाले कुल शुद्ध प्रवाह के बराबर है अर्थात $| f | = f out (A) - f in (A)$ ।^[2]किसी तंत्र में प्रवाह मान, s से t तक प्रवाह की कुल मात्रा है।

प्रवाह समस्याओ के लिए उपयोगी अवधारणाएँ

चाप और प्रवाह को जोड़ना

हम किसी तंत्र के भीतर कई चापों का उपयोग नहीं करते हैं क्योंकि हम उन सभी चापों को एक चाप में जोड़ सकते हैं। दो चापों को एकल चाप में संयोजित करने के लिए, हम उनकी क्षमता और उनके प्रवाह मान को जोड़ते हैं, और उन्हें नए चाप में निर्दिष्ट करते हैं:

कोई दो नोड $u$ और $v$ दिए गए हैं जहा $u$ से $v$ तक दो चाप है जिनकी क्षमताएं क्रमशः $c 1 (u,v)$ और $c 2 (u,v)$ है, यह $u$ को $v$ से जोड़ने वाले एकल चाप के बराबर होगा जिनकी क्षमता $c 1 (u,v)+c 2 (u,v)$ है।
कोई दो नोड $u$ और $v$ दिए गए हैं जहा $u$ से $v$ तक दो चाप है जिनके आभासी प्रवाह क्रमशः $f 1 (u,v)$ और $f 2 (u,v)$ है यह $u$ को $v$ से जोड़ने वाले एकल चाप के बराबर होगा जिसका आभासी प्रवाह $f 1 (u,v)+f 2 (u,v)$ .है।

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

अवशेष

आभासी-प्रवाह f के संबंध में एक चाप e की अवशिष्ट क्षमता को c_f द्वारा निरूपित किया जाता है, और यह चाप की क्षमता और इसके प्रवाह के बीच का अंतर है। अर्थात $c f (e) = c (e) - f (e)$ .इससे हम एक अवशिष्ट तंत्र $G f (V, E f)$ का निर्माण कर सकते हैं , एक क्षमता फलन $c f$ के साथ जो चाप के समुच्चय $G = (V, E)$ पर उपलब्ध क्षमता की मात्रा को प्ररूपित करता है। विशिस्ट रूप से, $(u, v)$ का प्रत्येक चाप, क्षमता फलन $c f$ के अवशिष्ट तंत्र में प्रवाह की मात्रा का प्रतिनिधित्व करता है जिसे तंत्र के भीतर प्रवाह की वर्तमान स्थिति को देखते हुए $u$ को $v$ से स्थानांतरित किया जा सकता है।

इस अवधारणा का उपयोग फोर्ड-फुलकर्सन विधिकलन में किया जाता है जो प्रवाह तंत्र में अधिकतम प्रवाह की गणना करता है।

ध्यान दें कि अवशिष्ट तंत्र में $u$ से $v$ तक एक असंतृप्त पथ हो सकता है भले ही $u$ से $v$ तक मूल तंत्र में कोई भी वास्तविक पथ न हों। चूंकि विपरीत दिशाओं में प्रवाह नष्ट हो जाता है, v से u तक प्रवाह घटाना, u से v तक प्रवाह बढ़ाने के समान है।.

संवर्धित पथ

संवर्धित पथ अवशिष्ट तंत्र में एक पथ $(u 1, u 2, ..., u k)$ है, जहां $u 1 = s$ , $u k = t$ , और $सभी u i, u i + 1 (c f (u i, u i + 1) > 0) (1 \leq i < k)$ के लिए सत्य है अधिक सरलता से कहे तों, संवर्धित पथ स्रोत से सिंक तक उपलब्ध प्रवाह पथ है। एक तंत्र अधिकतम प्रवाह पर है यदि और केवल यदि अवशिष्ट तंत्र $G f$ में कोई संवर्द्धन पथ नहीं है .

अवरोध एक दिए गए संवर्द्धन पथ में सभी भुजाओं की न्यूनतम अवशिष्ट क्षमता है।^[2] इस आलेख के उदाहरण अनुभाग में समझाया गया उदाहरण देखें। प्रवाह तंत्र अधिकतम प्रवाह पर है यदि और केवल यदि इसमें शून्य से अधिक मान का अवरोध है।

संवर्द्धन पथ के लिए "प्रवाह में वृद्धि" शब्द का अर्थ है इस संवर्द्धन पथ में प्रत्येक चाप के प्रवाह f को अवरोध क्षमता c के समान अद्यतन करना। प्रवाह को बढ़ाना संवर्द्धन पथ के साथ अतिरिक्त प्रवाह को तब तक धकेलता है जब तक कि अवरोध में उपलब्ध अवशिष्ट क्षमता शेष न हो।

एकाधिक स्रोत और/या सिंक

कभी-कभी, एक से अधिक स्रोत वाले तंत्र को प्ररूपित करते समय, आरेख़ में स्रोत प्रस्तुत किया जाता है।^[3] इसमें अनंत क्षमता के भुजाऑ के साथ प्रत्येक स्रोत से जुड़ा एक शीर्ष होता है, ताकि इसे वैश्विक स्रोत के रूप में फलन किया जा सके। ऐसे ही सिंक के समान निर्माण को सुपरसिंक कहा जाता है।^[4]

उदाहरण

(चित्र 1) प्रवाह और क्षमता दिखाने वाला प्रवाह तंत्र

(चित्र 2) प्रवाह और क्षमता दिखाने वाले प्रवाह तंत्र के लिए एक वैकल्पिक संकेतन।

चित्र 1 में आप सिंक t और चार अतिरिक्त नोड्स s वाले स्रोत के साथ एक प्रवाह तंत्र देखते हैं। प्रवाह और क्षमता को $f/c$ से निरूपित किया जाता है . ध्यान दें कि तंत्र मे तिर्यक समरूपता बाधा, क्षमता बाधा और प्रवाह संरक्षण बाधा को कैसे स्थित रखता है। इससे $s$ से $t$ तक प्रवाह की कुल मात्रा 5 है, जिसे इस तथ्य से सरलता से देखा जा सकता है कि कुल बहिर्गामी प्रवाह $s$ से है, और निविष्ट प्रवाह $t$ है ध्यान दें, चित्र 1 को प्रायः चित्र 2 की अंकन शैली में लिखा जाता है।

(चित्र तीन)। उपरोक्त प्रवाह तंत्र के लिए अवशिष्ट तंत्र, अवशिष्ट क्षमता दिखा रहा है।

चित्र 3 में आप दिए गए प्रवाह के लिए अवशिष्ट तंत्र देखते हैं। ध्यान दें कि जहां चित्र 1 में मूल क्षमता शून्य है चित्र 3 मे कैसे कुछ भुजाऑ पर सकारात्मक अवशिष्ट क्षमता होती है , उदाहरण हेतु $(d,c)$ भुजा के लिए यह तंत्र अधिकतम प्रवाह पर नहीं है। $(s,a,c,t)$ , $(s,a,b,d,t)$ और $(s,a,b,d,c,t)$ पथों के लिए उपलब्ध क्षमताए है जो संवर्धित पथ हैं।

$(s,a,c,t)$ पथ का अवरोध $\min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))$ $=\min(c_{f}(s,a),c_{f}(a,c),c_{f}(c,t))$ $=\min(5-3,3-2,2-1)$ $=\min(2,1,1)=1$ .के बराबर है।

अनुप्रयोग

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

प्रवाह परिवहन तंत्र लोगों या सामग्री से संबंधित हो सकता है, या विद्युत वितरण प्रणाली पर विद्युत से संबंधित हो सकता है। ऐसे किसी भी भौतिक तंत्र के लिए, किसी मध्यवर्ती नोड में आने वाले प्रवाह को उस नोड से बाहर जाने वाले प्रवाह के समान होना चाहिए। यह संरक्षण बाधा किरचॉफ के धारा नियम के समान है।

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

प्रवाह की समस्याओं का वर्गीकरण

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

अधिकतम प्रवाह समस्या के लिए प्रसिद्ध विधिकलन
आविष्कारक	वर्ष	समय जटिलता (n नोड और m चाप के संदर्भ मे )
डिनिक का विधिकलन	1969	$O (mn 2)$
एडमंड्स-कार्प विधिकलन	1972	$O (m 2 n)$
एमपीएम (मल्होत्रा, प्रमोद-कुमार और माहेश्वरी)कलन विधि^[5]	1978	$O (n 3)$
जेम्स बी. ओर्लिन^[6]	2013	$O (mn)$

बहु-वस्तु प्रवाह समस्या में, आपके पास कई स्रोत और सिंक हैं, और विभिन्न वस्तुए हैं जो किसी दिए गए स्रोत से दिए गए सिंक में प्रवाहित होती हैं। उदाहरण के लिए विभिन्न सामान हो सकते हैं जो विभिन्न कारखानों में उत्पादित होते हैं, और एक ही परिवहन तंत्र के माध्यम से विभिन्न ग्राहकों को वितरित किए जाते हैं।

न्यूनतम लागत प्रवाह समस्या में, प्रत्येक भुजा $u,v$ के लिए लागत $k(u,v)$ है, और प्रवाह $f(u,v)$ भेजने की लागत $f(u,v)\cdot k(u,v)$ है. इसका उद्देश्य न्यूनतम संभव मूल्य पर स्रोत से सिंक तक प्रवाह की एक निश्चित मात्रा भेजना है।

संचलन की समस्या में, ऊपरी सीमा $c(u,v)$ के साथ भुजाऑ पर निचली सीमा $\ell (u,v)$ भी होती है। प्रत्येक भुजा की भी एक लागत होती है। प्रायः, संचलन समस्या में सभी नोड्स के लिए प्रवाह संरक्षण होता है, और सिंक से वापस स्रोत तक संपर्क होता है। इस तरह, आप कुल प्रवाह $\ell (t,s)$ और $c(t,s)$ को निर्देशित कर सकते हैं। प्रवाह, तंत्र के माध्यम से प्रसारित होता है, इसलिए समस्या का नाम संचलन की समस्या रखा गया है।

एक 'तंत्र विद गेन' या 'सामान्यीकृत तंत्र' में प्रत्येक भुजा का 'लाभ आरेख' वास्तविक संख्या होती है। यदि संख्या का बढ़त लाभ g है, और राशि x उसके छोर पर भुजाऑ में प्रवाहित होती है, तो राशि gx शीर्ष पर प्रवाहित होगी।

एक 'स्रोत स्थानीयकरण समस्या' में, विधिकलन आंशिक रूप से संदर्भित तंत्र के माध्यम से सूचना प्रसार के सबसे संभावित स्रोत नोड की पहचान करने का प्रयास करता है। यह पेड़ों के लिए रैखिक समय और स्वैच्छिक तंत्र के लिए घन समय में किया जा सकता है और इसमें मोबाइल फोन उपयोगकर्ताओं का पीछा करने से लेकर बीमारी के प्रकोप के मूल स्रोत की पहचान करने तक के अनुप्रयोग हैं।^[7]

यह भी देखें

ब्रेस का विरोधाभास
केंद्रीयता
फोर्ड-फुलकर्सन विधिकलन
डिनिक का विधिकलन
प्रवाह (कंप्यूटर तंत्रिंग)
प्रवाह आरेख (बहुविकल्पी)
मैक्स-प्रवाह मिन-कट प्रमेय
ओरिएंटेड मैट्रोइड
सबसे छोटा रास्ता समस्या
कहीं नहीं-शून्य प्रवाह

संदर्भ

↑ A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989
↑ ^2.0 ^2.1 Kleinberg, Jon (2011). Algorithm design. Éva Tardos (2nd ed.). Boston, Mass.: Addison-Wesley. pp. 342, 346. ISBN 0-13-213108-0. OCLC 796210667.
↑ This article incorporates public domain material from Black, Paul E. "Supersource". Dictionary of Algorithms and Data Structures.
↑ This article incorporates public domain material from Black, Paul E. "Supersink". Dictionary of Algorithms and Data Structures.
↑ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). "An $O(|V|^{3})$ algorithm for finding maximum flows in networks" (PDF). Information Processing Letters. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9. Archived (PDF) from the original on 2021-04-18. Retrieved 2019-07-11.
↑ Orlin, James B. (2013-06-01). "Max flows in O(nm) time, or better". Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing. STOC '13. Palo Alto, California, USA: Association for Computing Machinery: 765–774. doi:10.1145/2488608.2488705. hdl:1721.1/88020. ISBN 978-1-4503-2029-0. S2CID 207205207 – via MIT Open Access https://dspace.mit.edu/handle/1721.1/88020. {{cite journal}}: External link in |via= (help)
↑ Pinto, P.C.; Thiran, P.; Vetterli, M. (2012). "Locating the source of diffusion in large-scale networks" (PDF). Physical Review Letters. 109 (6): 068702. arXiv:1208.2534. Bibcode:2012PhRvL.109f8702P. doi:10.1103/PhysRevLett.109.068702. PMID 23006310. S2CID 14526887. Archived (PDF) from the original on 2012-10-22. Retrieved 2012-08-14.

अग्रिम पठन

George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Chapter 8:Network Flow Algorithms". Algorithms in a Nutshell. Oreilly Media. pp. 226–250. ISBN 978-0-596-51624-6.
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X.{{cite book}}: CS1 maint: multiple names: authors list (link)
Bollobás, Béla (1979). Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag. ISBN 3-540-90399-2.
Chartrand, Gary & Oellermann, Ortrud R. (1993). Applied and Algorithmic Graph Theory. New York: McGraw-Hill. ISBN 0-07-557101-3.{{cite book}}: CS1 maint: multiple names: authors list (link)
Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. ISBN 0-914894-21-8.
Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge: Cambridge University Press. ISBN 0-521-28881-9.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "26". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 696–697. ISBN 0-262-03293-7.{{cite book}}: CS1 maint: multiple names: authors list (link)

बाहरी संबंध

Maximum Flow Problem
Real graph instances
Lemon C++ library with several maximum flow and minimum cost circulation algorithms
QuickGraph Archived 2018-01-21 at the Wayback Machine, graph data structures and algorithms for .Net

[1] A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989

[:0-2] 2.0 ^2.1 Kleinberg, Jon (2011). Algorithm design. Éva Tardos (2nd ed.). Boston, Mass.: Addison-Wesley. pp. 342, 346. ISBN 0-13-213108-0. OCLC 796210667.

[3] This article incorporates public domain material from Black, Paul E. "Supersource". Dictionary of Algorithms and Data Structures.

[4] This article incorporates public domain material from Black, Paul E. "Supersink". Dictionary of Algorithms and Data Structures.

[5] Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978). "An $O(|V|^{3})$ algorithm for finding maximum flows in networks" (PDF). Information Processing Letters. 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9. Archived (PDF) from the original on 2021-04-18. Retrieved 2019-07-11.

[6] Orlin, James B. (2013-06-01). "Max flows in O(nm) time, or better". Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing. STOC '13. Palo Alto, California, USA: Association for Computing Machinery: 765–774. doi:10.1145/2488608.2488705. hdl:1721.1/88020. ISBN 978-1-4503-2029-0. S2CID 207205207 – via MIT Open Access https://dspace.mit.edu/handle/1721.1/88020. {{cite journal}}: External link in |via= (help)

[7] Pinto, P.C.; Thiran, P.; Vetterli, M. (2012). "Locating the source of diffusion in large-scale networks" (PDF). Physical Review Letters. 109 (6): 068702. arXiv:1208.2534. Bibcode:2012PhRvL.109f8702P. doi:10.1103/PhysRevLett.109.068702. PMID 23006310. S2CID 14526887. Archived (PDF) from the original on 2012-10-22. Retrieved 2012-08-14.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{Short description|Directed graph where edges have a capacity}}
-[[ग्राफ सिद्धांत|आरेख सिद्धांत]] में, प्रवाह तंत्र जिसे परिवहन तंत्र के रूप में भी जाना जाता है, एक [[निर्देशित ग्राफ|निर्देशित आरेख]] है जहां प्रत्येक भुजा की कुछ क्षमता होती है और प्रत्येक भुजा को प्रवाह प्राप्त होता है। भुजाओं पर प्रवाह की मात्रा उसकी क्षमता से अधिक नहीं हो सकती। प्रायः संचालन अनुसंधान में, निर्देशित आरेख को तंत्र कहा जाता है, शीर्षों को नोड कहा जाता है और भुजाऑ को चाप कहा जाता है। प्रवाह को इस प्रतिबंध को स्थापित करना चाहिए कि नोड के भीतर प्रवाह की मात्रा इसके बाहर प्रवाह की मात्रा के बराबर हों, जब तक कि नोड कोई स्रोत या कुंड(सिंक) न हो। तंत्र का उपयोग कंप्यूटर तंत्र में ट्रैफ़िक, मांगों के साथ परिसंचरण, नलिकाों में तरल पदार्थ, विद्युत परिपथ में धाराओं, या कुछ इसी तरह के नोड्स के तंत्र के माध्यम से यात्रा करने के लिए किया जा सकता है।
+[[ग्राफ सिद्धांत|आरेख सिद्धांत]] में, प्रवाह तंत्र जिसे परिवहन तंत्र के रूप में भी जाना जाता है, एक [[निर्देशित ग्राफ|निर्देशित आरेख]] है जहां प्रत्येक भुजा की कुछ क्षमता होती है और प्रत्येक भुजा को प्रवाह प्राप्त होता है। भुजाओं पर प्रवाह की मात्रा उसकी क्षमता से अधिक नहीं हो सकती। प्रायः संचालन अनुसंधान में, निर्देशित आरेख को तंत्र कहा जाता है, शीर्षों को नोड कहा जाता है और भुजाऑ को चाप कहा जाता है। प्रवाह को इस प्रतिबंध को स्थापित करना चाहिए कि नोड के भीतर प्रवाह की मात्रा इसके बाहर प्रवाह की मात्रा के बराबर हों, जब तक कि नोड कोई स्रोत या कुंड(सिंक) न हो। तंत्र का उपयोग कंप्यूटर तंत्र में ट्रैफ़िक, मांगों के साथ परिसंचरण, नलिकाओं में तरल पदार्थ, विद्युत परिपथ में धाराओं, या कुछ इसी तरह के नोड्स के तंत्र के माध्यम से यात्रा करने के लिए किया जा सकता है।
 == परिभाषा ==
-तंत्र एक निर्देशित आरेख G = (V, E) है जिसमें प्रत्येक भुजाओं के लिए एक गैर-नकारात्मक क्षमता फलन c है और एक ही स्रोत और लक्ष्य नोड्स वाली चाँपरहित भुजाये हैं। [[व्यापकता के नुकसान के बिना|सामान्यीकरण के  हानी के बिना]], हम यह मान सकते हैं कि यदि {{math|(''u'', ''v'') ∈ ''E''}} है तब {{math|(''v'', ''u'')}} भी {{mvar|E}} का सदस्य है इसके अतिरिक्त, यदि {{math|(''v'', ''u'') ∉ ''E''}} तो हम {{math|(''v'', ''u'')}} को {{mvar|E}} में जोड़ सकते हैं और फिर  {{math|''c''(''v'', ''u'') {{=}} 0}}.समायोजित कर सकते हैं।
+तंत्र एक निर्देशित आरेख G = (V, E) है जिसमें प्रत्येक भुजाओं के लिए एक गैर-ऋणात्मक क्षमता फलन c है और एक ही स्रोत और लक्ष्य नोड्स वाली चाँपरहित भुजाये हैं। [[व्यापकता के नुकसान के बिना|सामान्यीकरण के  हानी के बिना]], हम यह मान सकते हैं कि यदि {{math|(''u'', ''v'') ∈ ''E''}} है तब {{math|(''v'', ''u'')}} भी {{mvar|E}} का सदस्य है इसके अतिरिक्त, यदि {{math|(''v'', ''u'') ∉ ''E''}} तो हम {{math|(''v'', ''u'')}} को {{mvar|E}} में जोड़ सकते हैं और फिर  {{math|''c''(''v'', ''u'') {{=}} 0}}.समायोजित कर सकते हैं।
 यदि {{mvar|G}} में दो नोड्स विभेदित हैं - स्रोत के रूप में '''{{mvar|s}}''' और सिंक के रूप में '''{{mvar|t}}''' - तब {{math|(''G'', ''c'', ''s'', ''t'')}} को प्रवाह तंत्र कहा जाता है।<ref>A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989</ref>
@@ Line 13: / Line 13: @@
 प्रवाह फलन, नोड्स के युग्मों के मध्य इकाइयों के शुद्ध प्रवाह को प्रारूपित करते हैं, और प्रश्न पूछते समय उपयोगी होते हैं जैसे कि इकाइयों की अधिकतम संख्या क्या है जो स्रोत नोड एस से सिंक नोड टी में स्थानांतरित की जा सकती है? दो नोड्स के मध्य प्रवाह की मात्रा का उपयोग एक नोड से दूसरे नोड में स्थानांतरित होने वाली इकाइयों की शुद्ध मात्रा का प्रतिनिधित्व करने के लिए किया जाता है।
-'''अधिशेष''' फलन {{math|''x''<sub>''f''</sub> : ''V'' → <math>\mathbb{R}</math>}} किसी दिए गए नोड {{mvar|u}} में प्रवेश करने वाले शुद्ध प्रवाह को संदर्भित करता है और<math display="block">x_f(u)=\sum_{w \in V} f(w,u).</math>द्वारा परिभाषित किया गया है
+अधिशेष फलन {{math|''x''<sub>''f''</sub> : ''V'' → <math>\mathbb{R}</math>}} किसी दिए गए नोड {{mvar|u}} में प्रवेश करने वाले शुद्ध प्रवाह को संदर्भित करता है और<math display="block">x_f(u)=\sum_{w \in V} f(w,u).</math>द्वारा परिभाषित किया गया है
-किसी नोड {{mvar|u}}  यदि  {{math|''x''<sub>''f''</sub> (''u'') > 0}} अर्थात नोड {{mvar|u}} प्रवाह को ग्रहण करता है तों इसे '''सक्रिय''' कहा जाएगा, यदि {{math|''x''<sub>''f''</sub> (''u'') < 0}} अर्थात नोड {{mvar|u}} प्रवाह का उत्पादन करता है तों इसे '''अपूर्ण''' कहा जाएगा और यदि  {{math|''x''<sub>''f''</sub> (''u'') {{=}} 0}} है तों इसे '''सरक्षक''' कहा जाएगा। प्रवाह तंत्र में, स्रोत {{mvar|s}} अपूर्ण है, और कुंड {{mvar|t}} सक्रिय है।
+किसी नोड {{mvar|u}}  यदि  {{math|''x''<sub>''f''</sub> (''u'') > 0}} अर्थात नोड {{mvar|u}} प्रवाह को ग्रहण करता है तों इसे सक्रिय कहा जाएगा, यदि {{math|''x''<sub>''f''</sub> (''u'') < 0}} अर्थात नोड {{mvar|u}} प्रवाह का उत्पादन करता है तों इसे अपूर्ण कहा जाएगा और यदि  {{math|''x''<sub>''f''</sub> (''u'') {{=}} 0}} है तों इसे सरक्षक कहा जाएगा। प्रवाह तंत्र में, स्रोत {{mvar|s}} अपूर्ण है, और कुंड {{mvar|t}} सक्रिय है।
 आभासी प्रवाह, व्यवहार्य प्रवाह और पूर्व प्रवाह सभी प्रवाह फलनों के उदाहरण हैं।
@@ Line 37: / Line 37: @@
 * कोई दो नोड {{mvar|u}} और {{mvar|v}} दिए गए हैं जहा {{mvar|u}} से {{mvar|v}} तक दो चाप है जिनके आभासी प्रवाह क्रमशः  {{mvar|f<sub>1</sub>(u,v)}} और {{mvar|f<sub>2</sub>(u,v)}} है यह {{mvar|u}} को {{mvar|v}} से जोड़ने वाले एकल चाप के बराबर होगा जिसका आभासी प्रवाह  {{mvar|f<sub>1</sub>(u,v)+f<sub>2</sub>(u,v)}}.है।
 अन्य बाधाओं के साथ, मूल आभासी-प्रवाह चाप की दिशा को बनाए रखने के लिए इस चरण के दौरान तिर्यक समरूपता बाधा का ध्यान रखना चाहिए। चाप में प्रवाह जोड़ना, शून्य की क्षमता वाले चाप को जोड़ने के समान है।
 === अवशेष ===
-आभासी-प्रवाह f के संबंध में एक चाप e की अवशिष्ट क्षमता को c<sub>f</sub> द्वारा निरूपित किया जाता है, और यह चाप की क्षमता और इसके प्रवाह के बीच का अंतर है। अर्थात {{math|''c''<sub>''f''</sub> (''e'') {{=}} ''c''(''e'') - ''f''(''e'')}}.इससे हम एक अवशिष्ट तंत्र {{math|''G''<sub>''f''</sub> (''V'', ''E''<sub>''f''</sub>)}} का निर्माण कर सकते हैं , एक क्षमता फलन {{math|''c''<sub>''f''</sub>}}  के साथ जो चाप के समुच्चय {{math|''G'' {{=}} (''V'', ''E'')}} पर उपलब्ध क्षमता की मात्रा को प्ररूपित करता है। विशिस्ट रूप से, {{math|(''u'', ''v'')}} का प्रत्येक चाप, क्षमता फलन {{math|''c''<sub>''f''</sub>}}  के अवशिष्ट तंत्र में प्रवाह की मात्रा का प्रतिनिधित्व करता है जिसे तंत्र के भीतर प्रवाह की वर्तमान स्थिति को देखते हुए {{math|''u''}} को {{math|''v''}} से स्थानांतरित किया जा सकता है ।
+आभासी-प्रवाह f के संबंध में एक चाप e की अवशिष्ट क्षमता को c<sub>f</sub> द्वारा निरूपित किया जाता है, और यह चाप की क्षमता और इसके प्रवाह के बीच का अंतर है। अर्थात {{math|''c''<sub>''f''</sub> (''e'') {{=}} ''c''(''e'') - ''f''(''e'')}}.इससे हम एक अवशिष्ट तंत्र {{math|''G''<sub>''f''</sub> (''V'', ''E''<sub>''f''</sub>)}} का निर्माण कर सकते हैं , एक क्षमता फलन {{math|''c''<sub>''f''</sub>}}  के साथ जो चाप के समुच्चय {{math|''G'' {{=}} (''V'', ''E'')}} पर उपलब्ध क्षमता की मात्रा को प्ररूपित करता है। विशिस्ट रूप से, {{math|(''u'', ''v'')}} का प्रत्येक चाप, क्षमता फलन {{math|''c''<sub>''f''</sub>}}  के अवशिष्ट तंत्र में प्रवाह की मात्रा का प्रतिनिधित्व करता है जिसे तंत्र के भीतर प्रवाह की वर्तमान स्थिति को देखते हुए {{math|''u''}} को {{math|''v''}} से स्थानांतरित किया जा सकता है।
 इस अवधारणा का उपयोग फोर्ड-फुलकर्सन विधिकलन में किया जाता है जो प्रवाह तंत्र में [[अधिकतम प्रवाह]] की गणना करता है।
@@ Line 56: / Line 53: @@
 === एकाधिक स्रोत और/या सिंक ===
 कभी-कभी, एक से अधिक स्रोत वाले तंत्र को प्ररूपित करते समय, आरेख़ में स्रोत प्रस्तुत किया जाता है।<ref>{{DADS|Supersource|supersource}}</ref> इसमें अनंत क्षमता के भुजाऑ के साथ प्रत्येक स्रोत से जुड़ा एक शीर्ष होता है, ताकि इसे वैश्विक स्रोत के रूप में फलन किया जा सके। ऐसे ही सिंक के समान निर्माण को सुपरसिंक कहा जाता है।<ref>{{DADS|Supersink|supersink}}</ref>
 == उदाहरण ==
@@ Line 78: / Line 74: @@
 == प्रवाह की समस्याओं का वर्गीकरण ==
-प्रवाह तंत्र का उपयोग करने वाली सबसे सरल और सबसे साधारण समस्या यह ज्ञात करना है कि [[अधिकतम प्रवाह समस्या]] क्या होती है, जो किसी दिए गए आरेख में स्रोत से सिंक तक सबसे बड़ा संभव पूर्ण प्रवाह प्रदान करती है। ऐसी कई अन्य समस्याएं हैं जिन्हें यदि प्रवाह तंत्र के रूप में उचित रूप से प्रतिरूपित कर दिया जाता है तों अधिकतम प्रवाह विधिकलन का उपयोग करके हल किया जा सकता है, जैसे द्विदलीय मिलान, असाइनमेंट समस्या और [[परिवहन समस्या]]। अधिकतम प्रवाह की समस्याओं को पुश-रिलेबेल विधिकलन के साथ कुशलतापूर्वक हल किया जा सकता है। [[मैक्स-फ्लो मिन-कट प्रमेय|मैक्स-प्रवाह मिन-कट प्रमेय]] बताता है कि अधिकतम तंत्र प्रवाह खोजना न्यूनतम क्षमता के [[कट (ग्राफ सिद्धांत)|कट आरेख सिद्धांत]] को खोजने के बराबर है जो स्रोत और सिंक को अलग करता है, जहां कट शीर्षों का विभाजन है जिसका एक भाग स्रोत के भीतर है और दूसरा सिंक के भीतर है।
+प्रवाह तंत्र का उपयोग करने वाली सबसे सरल और सबसे साधारण समस्या यह ज्ञात करना है कि [[अधिकतम प्रवाह समस्या]] क्या होती है, जो किसी दिए गए आरेख में स्रोत से सिंक तक सबसे बड़ा संभव पूर्ण प्रवाह प्रदान करती है। ऐसी कई अन्य समस्याएं हैं जिन्हें यदि प्रवाह तंत्र के रूप में उचित रूप से प्रतिरूपित कर दिया जाता है तों अधिकतम प्रवाह विधिकलन का उपयोग करके हल किया जा सकता है, जैसे द्विदलीय मिलान, असाइनमेंट समस्या और [[परिवहन समस्या]] है। अधिकतम प्रवाह की समस्याओं को पुश-रिलेबेल विधिकलन के साथ कुशलतापूर्वक हल किया जा सकता है। [[मैक्स-फ्लो मिन-कट प्रमेय|मैक्स-प्रवाह मिन-कट प्रमेय]] बताता है कि अधिकतम तंत्र प्रवाह खोजना न्यूनतम क्षमता के [[कट (ग्राफ सिद्धांत)|कट आरेख सिद्धांत]] को खोजने के बराबर है जो स्रोत और सिंक को अलग करता है, जहां कट शीर्षों का विभाजन है जिसका एक भाग स्रोत के भीतर है और दूसरा सिंक के भीतर है।
 {| class="wikitable" style="height: 200px;" align="right"

Anonymous

Search

प्रवाह नेटवर्क: Difference between revisions

Namespaces

More

Page actions

Revision as of 13:34, 20 February 2023

Contents

परिभाषा

प्रवाह