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

Revision as of 05:22, 19 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)$ .

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

अवशेष

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

इस अवधारणा का उपयोग Ford-Fulkerson एल्गोरिथम में किया जाता है जो प्रवाह नेटवर्क में अधिकतम प्रवाह की गणना करता है।

ध्यान दें कि से एक असंतृप्त पथ (उपलब्ध क्षमता वाला पथ) हो सकता है $u$ को $v$ अवशिष्ट नेटवर्क में, भले ही ऐसा कोई रास्ता न हो $u$ को $v$ मूल नेटवर्क में।^{[citation needed]} चूंकि विपरीत दिशाओं में प्रवाह रद्द हो जाता है, जिससे प्रवाह कम हो जाता है $v$ को $u$ से प्रवाह बढ़ाने के समान है $u$ को $v$ .

संवर्धित पथ

एक संवर्धित पथ एक पथ है $(u 1, u 2, ..., u k)$ अवशिष्ट नेटवर्क में, जहां $u 1 = s$ , $u k = t$ , और $for all 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 में आप लेबल वाले स्रोत के साथ प्रवाह नेटवर्क देखते हैं $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$ .

अनुप्रयोग

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

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

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

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

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

Well-known algorithms for the Maximum Flow Problem
Inventor(s)	Year	Time complexity (with $n$ nodes and $m$ arcs)
Dinic's algorithm	1969	$O (mn 2)$
Edmonds–Karp algorithm	1972	$O (m 2 n)$
MPM (Malhotra, Pramodh-Kumar, and Maheshwari) algorithm^[5]	1978	$O (n 3)$
James B. Orlin^[6]	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 शीर्ष पर प्रवाहित होती है।

एक 'स्रोत स्थानीयकरण समस्या' में, एक एल्गोरिथ्म आंशिक रूप से देखे गए नेटवर्क के माध्यम से सूचना प्रसार के सबसे संभावित स्रोत नोड की पहचान करने का प्रयास करता है। यह पेड़ों के लिए रैखिक समय और स्वैच्छिक नेटवर्क के लिए घन समय में किया जा सकता है और इसमें मोबाइल फोन उपयोगकर्ताओं को ट्रैक करने से लेकर बीमारी के प्रकोप के मूल स्रोत की पहचान करने तक के अनुप्रयोग हैं।^[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 27: / Line 27: @@
 : व्यवहार्य प्रवाह, एक आभासी प्रवाह है, जो सभी {{math|''v'' ∈ ''V'' \{''s'', ''t''}}},के लिए अतिरिक्त बाधा को पूरा करता है:
 : * ''प्रवाह संरक्षण बाधा'': किसी नोड {{mvar|v}} में प्रवेश करने वाला कुल शुद्ध प्रवाह, स्रोत <math>s</math> और सिंक <math>t</math> को छोड़कर, नेटवर्क में सभी नोड्स के लिए शून्य है जो सभी {{math|''v'' ∈ ''V'' \{''s'', ''t''<nowiki>}</nowiki>}} के लिए  {{math|''x''<sub>''f''</sub> (''v'') {{=}} 0}} है . दूसरे शब्दों में, स्रोत <math>s</math> और सिंक <math>t</math>, को छोड़कर नेटवर्क में सभी नोड्स के लिए किसी नोड से आने वाले प्रवाह का कुल योग इसके बर्हिगामी प्रवाह के बराबर होता है
-:अर्थात प्रत्येक शीर्ष  {{math|''v'' ∈ ''V'' \{''s'', ''t''<nowiki>}</nowiki>}} के लिए <math>\sum_{(u,v) \in E} f(u,v) = \sum_{(v,z) \in E} f(v,z) </math> है .
+:अर्थात प्रत्येक शीर्ष  {{math|''v'' ∈ ''V'' \{''s'', ''t''<nowiki>}</nowiki>}} के लिए <math>\sum_{(u,v) \in E} f(u,v) = \sum_{(v,z) \in E} f(v,z) </math> है।.
-मूल्य {{math|{{!}} ''f'' {{!}}}} एक व्यवहार्य प्रवाह की {{mvar|f}} एक नेटवर्क के लिए, सिंक में शुद्ध प्रवाह है {{mvar|t}} प्रवाह नेटवर्क का, वह है: {{math|{{!}} ''f'' {{!}} {{=}} ''x''<sub>''f''</sub> (''t'')}}. ध्यान दें, नेटवर्क में प्रवाह मान भी स्रोत के कुल आउटगोइंग प्रवाह के बराबर होता है {{mvar|s}}, वह है: {{math|{{!}} ''f'' {{!}} {{=}} -''x''<sub>''f''</sub> (''s'')}}. इसके अलावा, यदि हम परिभाषित करते हैं {{math|''A''}} में नोड्स के एक सेट के रूप में {{math|''G''}} ऐसा है कि {{math|''s'' ∈ ''A''}} और {{math|''t'' ∉ ''A''}}, प्रवाह मान A से बाहर जाने वाले कुल शुद्ध प्रवाह के बराबर है (अर्थात {{math|{{!}} ''f'' {{!}} {{=}} ''f''<sup> out</sup>(''A'') - ''f''<sup> in</sup>(''A'')}}).<ref name=":0" />एक नेटवर्क में प्रवाह मूल्य से प्रवाह की कुल राशि है {{mvar|s}} को {{mvar|t}}.
+व्यवहार्य प्रवाह f का मान नेटवर्क | ''f'' | के लिए एक प्रवाह नेटवर्क के सिंक t में शुद्ध प्रवाह है, अर्थात: | ''f'' | = ''x<sub>f</sub>'' (''t'')। ध्यान दें, नेटवर्क में प्रवाह मान भी स्रोत {{mvar|s}} के सभी बहिर्गामी प्रवाह के बराबर होता है जो  {{math|{{!}} ''f'' {{!}} {{=}} -''x''<sub>''f''</sub> (''s'')}} है। इसके अतिरिक्त, यदि हम {{math|''A''}} को नोड्स {{math|''G''}} के एक समुच्चय के रूप में इस प्रकार परिभाषित करते हैं कि {{math|''s'' ∈ ''A''}} और {{math|''t'' ∉ ''A''}} तो प्रवाह मान, A से बाहर जाने वाले कुल शुद्ध प्रवाह के बराबर है अर्थात {{math|{{!}} ''f'' {{!}} {{=}} ''f''<sup> out</sup>(''A'') - ''f''<sup> in</sup>(''A'')}}।<ref name=":0" />किसी नेटवर्क में प्रवाह मान, s से t तक प्रवाह की कुल मात्रा है।
 == समस्याओं को प्रवाहित करने के लिए उपयोगी अवधारणाएँ ==
@@ Line 60: / Line 60: @@
 [[File:Network Flow SVG.svg|left|thumb|332px|(चित्र 1) प्रवाह और क्षमता दिखाने वाला प्रवाह नेटवर्क]]
-[[File:Network Flow Cropped2.png|thumb|387x387px|(चित्र 2) प्रवाह और क्षमता दिखाने वाले प्रवाह नेटवर्क के लिए एक वैकल्पिक संकेतन।]]चित्र 1 में आप लेबल वाले स्रोत के साथ प्रवाह नेटवर्क देखते हैं {{mvar|s}}, डूबना {{mvar|t}}, और चार अतिरिक्त नोड। प्रवाह और क्षमता को निरूपित किया जाता है <math>f/c</math>. ध्यान दें कि नेटवर्क तिरछा समरूपता बाधा, क्षमता बाधा और प्रवाह संरक्षण बाधा को कैसे कायम रखता है। से प्रवाह की कुल मात्रा {{mvar|s}} को {{mvar|t}} 5 है, जिसे इस तथ्य से आसानी से देखा जा सकता है कि कुल आउटगोइंग प्रवाह से {{mvar|s}} 5 है, जो आने वाला प्रवाह भी है {{mvar|t}}. ध्यान दें, चित्र 1 को प्रायः चित्र 2 की अंकन शैली में लिखा जाता है।
+[[File:Network Flow Cropped2.png|thumb|387x387px|(चित्र 2) प्रवाह और क्षमता दिखाने वाले प्रवाह नेटवर्क के लिए एक वैकल्पिक संकेतन।]]चित्र 1 में आप लेबल वाले स्रोत के साथ प्रवाह नेटवर्क देखते हैं {{mvar|s}}, डूबना {{mvar|t}}, और चार अतिरिक्त नोड। प्रवाह और क्षमता को निरूपित किया जाता है <math>f/c</math>. ध्यान दें कि नेटवर्क तिरछा समरूपता बाधा, क्षमता बाधा और प्रवाह संरक्षण बाधा को कैसे कायम रखता है। से प्रवाह की कुल मात्रा {{mvar|s}} को {{mvar|t}} 5 है, जिसे इस तथ्य से आसानी से देखा जा सकता है कि कुल बहिर्गामी प्रवाह से {{mvar|s}} 5 है, जो आने वाला प्रवाह भी है {{mvar|t}}. ध्यान दें, चित्र 1 को प्रायः चित्र 2 की अंकन शैली में लिखा जाता है।
 [[File:Network flow residual SVG.svg|left|thumb|332px|(चित्र तीन)। उपरोक्त प्रवाह नेटवर्क के लिए अवशिष्ट नेटवर्क, अवशिष्ट क्षमता दिखा रहा है।]]चित्र 3 में आप दिए गए प्रवाह के लिए अवशिष्ट नेटवर्क देखते हैं। ध्यान दें कि कैसे कुछ किनारों पर सकारात्मक अवशिष्ट क्षमता होती है जहां चित्र 1 में मूल क्षमता शून्य है, उदाहरण के लिए भुजा के लिए <math>(d,c)</math>. यह नेटवर्क [[अधिकतम प्रवाह]] पर नहीं है। रास्तों के साथ उपलब्ध क्षमता है <math>(s,a,c,t)</math>, <math>(s,a,b,d,t)</math> और <math>(s,a,b,d,c,t)</math>, जो तब संवर्धित पथ हैं।
@@ Line 96: / Line 96: @@
 [[न्यूनतम लागत प्रवाह समस्या]] में, प्रत्येक भुजा <math>u,v</math> एक दी गई लागत है <math>k(u,v)</math>, और प्रवाह भेजने की लागत <math>f(u,v)</math> भुजा के पार है <math>f(u,v) \cdot k(u,v)</math>. इसका उद्देश्य न्यूनतम संभव कीमत पर स्रोत से सिंक तक प्रवाह की एक निश्चित मात्रा भेजना है।
-[[संचलन की समस्या]] में, आपकी निचली सीमा होती है <math>\ell(u,v)</math> ऊपरी सीमा के अलावा किनारों पर <math>c(u,v)</math>. प्रत्येक भुजा की भी एक लागत होती है। प्रायः, संचलन समस्या में सभी नोड्स के लिए प्रवाह संरक्षण होता है, और सिंक से वापस स्रोत तक एक कनेक्शन होता है। इस तरह, आप कुल प्रवाह को निर्देशित कर सकते हैं <math>\ell(t,s)</math> और <math>c(t,s)</math>. प्रवाह नेटवर्क के माध्यम से प्रसारित होता है, इसलिए समस्या का नाम।
+[[संचलन की समस्या]] में, आपकी निचली सीमा होती है <math>\ell(u,v)</math> ऊपरी सीमा के अतिरिक्त किनारों पर <math>c(u,v)</math>. प्रत्येक भुजा की भी एक लागत होती है। प्रायः, संचलन समस्या में सभी नोड्स के लिए प्रवाह संरक्षण होता है, और सिंक से वापस स्रोत तक एक कनेक्शन होता है। इस तरह, आप कुल प्रवाह को निर्देशित कर सकते हैं <math>\ell(t,s)</math> और <math>c(t,s)</math>. प्रवाह नेटवर्क के माध्यम से प्रसारित होता है, इसलिए समस्या का नाम।
 एक 'नेटवर्क विद गेन' या 'सामान्यीकृत नेटवर्क' में प्रत्येक भुजा का एक '[[लाभ ग्राफ|लाभ आरेख]]' होता है, एक वास्तविक संख्या (शून्य नहीं) जैसे कि, यदि भुजा का लाभ g है, और एक राशि x इसके सिरे पर भुजा में प्रवाहित होती है, तब एक राशि gx शीर्ष पर प्रवाहित होती है।

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 05:22, 19 February 2023

Contents

परिभाषा

प्रवाह