प्रवाह नेटवर्क

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

परिभाषा

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

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

प्रवाह

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

अधिशेष फलन x_f : V → $\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) ≤ c(u, v).

पूर्व-प्रवाह एक आभासी प्रवाह है, जो सभी v ∈ V \{s} के लिए अतिरिक्त बाधा को पूरा करता है:

• गैर-अपूर्ण प्रवाह: नोड में प्रवेश करने वाला शुद्ध प्रवाह v, प्रवाह उत्पन्न करने वाले स्रोत को छोड़कर गैर-ऋणात्मक है। वह v ∈ V \{s} के लिए x_f (v) ≥ 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 ∈ A और t ∉ A तो प्रवाह मान, A से बाहर जाने वाले कुल शुद्ध प्रवाह के बराबर है अर्थात | f | = f ^out(A) - f ⁱⁿ(A)।किसी नेटवर्क में प्रवाह मान, s से t तक प्रवाह की कुल मात्रा है।

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

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

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

• कोई दो नोड u और v दिए गए हैं जहा u से v तक दो चाप है जिनकी क्षमताएं क्रमशः c₁(u,v) और c₂(u,v) है, यह u को v से जोड़ने वाले एकल चाप के बराबर होगा जिनकी क्षमता c₁(u,v)+c₂(u,v) है।
• कोई दो नोड u और v दिए गए हैं जहा u से v तक दो चाप है जिनके आभासी प्रवाह क्रमशः f₁(u,v) और f₂(u,v) है यह u को v से जोड़ने वाले एकल चाप के बराबर होगा जिसका आभासी प्रवाह f₁(u,v)+f₂(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₁, u₂, ..., u_k) है, जहां u₁ = s, u_k = t, और सभी u_i, u_{i + 1} (c_f (u_i, u_{i + 1}) > 0) (1 ≤ i < k) के लिए सत्य है अधिक सरलता से कहे तों, संवर्धित पथ स्रोत से सिंक तक उपलब्ध प्रवाह पथ है। एक नेटवर्क अधिकतम प्रवाह पर है यदि और केवल यदि अवशिष्ट नेटवर्क G_f में कोई संवर्द्धन पथ नहीं है .

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

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

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

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

उदाहरण

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

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

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

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

चित्र 3 में आप दिए गए प्रवाह के लिए अवशिष्ट नेटवर्क देखते हैं। ध्यान दें कि कैसे कुछ किनारों पर सकारात्मक अवशिष्ट क्षमता होती है जहां चित्र 1 में मूल क्षमता शून्य है, उदाहरण के लिए भुजा के लिए $(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$.

अनुप्रयोग

See also: Pipe network analysis

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

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

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

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

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

Well-known algorithms for the Maximum Flow Problem

Inventor(s)	Year	Time complexity (with n nodes and m arcs)
Dinic's algorithm	1969	O(mn2)
Edmonds–Karp algorithm	1972	O(m2n)
MPM (Malhotra, Pramodh-Kumar, and Maheshwari) algorithm	1978	O(n3)
James B. Orlin	2013	O(mn)

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

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

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

एक 'नेटवर्क विद गेन' या 'सामान्यीकृत नेटवर्क' में प्रत्येक भुजा का एक 'लाभ आरेख' होता है, एक वास्तविक संख्या (शून्य नहीं) जैसे कि, यदि भुजा का लाभ g है, और एक राशि x इसके सिरे पर भुजा में प्रवाहित होती है, तब एक राशि gx शीर्ष पर प्रवाहित होती है।

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

यह भी देखें

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

अग्रिम पठन

• 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