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

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

परिभाषा

तंत्र एक निर्देशित आरेख 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 के समान अद्यतन करना। प्रवाह को बढ़ाना संवर्द्धन पथ के साथ अतिरिक्त प्रवाह को तब तक धकेलता है जब तक कि अवरोध में उपलब्ध अवशिष्ट क्षमता शेष न हो।

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

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

उदाहरण

Error creating thumbnail:

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

File:Network Flow Cropped2.png

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

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

Error creating thumbnail:

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

चित्र 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$.के बराबर है।

अनुप्रयोग

See also: