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

Revision as of 04:26, 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$ (यानी प्रवेश करने वाले प्रवाह का योग $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

:

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

एक पूर्व-प्रवाह एक छद्म प्रवाह है, जो सभी के लिए है

v ∈ V \{s

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

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

एक व्यवहार्य प्रवाह, या सिर्फ एक प्रवाह, एक छद्म प्रवाह है, जो सभी के लिए है

v ∈ V \{s, t

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

* प्रवाह संरक्षण बाधा: एक नोड में प्रवेश करने वाला कुल शुद्ध प्रवाह

v

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

s

और सिंक

t

, वह है:

x f (v) = 0

सभी के लिए

v ∈ V \{s, t}

. दूसरे शब्दों में, स्रोत को छोड़कर नेटवर्क में सभी नोड्स के लिए

s

और सिंक

t

, किसी नोड के आने वाले प्रवाह का कुल योग इसके आउटगोइंग प्रवाह के बराबर होता है (अर्थात

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

, प्रत्येक शीर्ष के लिए

v ∈ V \{s, t}

).

मूल्य $| 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 1: / Line 1: @@
 {{Short description|Directed graph where edges have a capacity}}
-[[ग्राफ सिद्धांत]] में, एक प्रवाह नेटवर्क (परिवहन नेटवर्क के रूप में भी जाना जाता है) एक [[निर्देशित ग्राफ]] है जहां प्रत्येक किनारे की क्षमता होती है और प्रत्येक किनारे को प्रवाह प्राप्त होता है। किनारे पर प्रवाह की मात्रा किनारे की क्षमता से अधिक नहीं हो सकती। अक्सर संचालन अनुसंधान में, एक निर्देशित ग्राफ को एक नेटवर्क कहा जाता है, कोने को नोड कहा जाता है और किनारों को चाप कहा जाता है। एक प्रवाह को प्रतिबंध को पूरा करना चाहिए कि एक नोड में प्रवाह की मात्रा इसके बाहर प्रवाह की मात्रा के बराबर होती है, जब तक कि यह एक स्रोत न हो, जिसमें केवल आउटगोइंग प्रवाह हो, या सिंक, जिसमें केवल आने वाला प्रवाह हो। एक नेटवर्क का उपयोग कंप्यूटर नेटवर्क में ट्रैफ़िक, मांगों के साथ परिसंचरण, पाइपों में तरल पदार्थ, विद्युत सर्किट में धाराओं, या कुछ इसी तरह के नोड्स के नेटवर्क के माध्यम से यात्रा करने के लिए किया जा सकता है।
+[[ग्राफ सिद्धांत|आरेख सिद्धांत]] में, प्रवाह नेटवर्क जिसे परिवहन नेटवर्क के रूप में भी जाना जाता है, एक [[निर्देशित ग्राफ|निर्देशित आरेख]] है जहां प्रत्येक भुजा की कुछ क्षमता होती है और प्रत्येक भुजा को प्रवाह प्राप्त होता है। भुजाओं पर प्रवाह की मात्रा उसकी क्षमता से अधिक नहीं हो सकती। प्रायः संचालन अनुसंधान में, निर्देशित आरेख को नेटवर्क कहा जाता है, शीर्षों को नोड कहा जाता है और भुजाऑ को चाप कहा जाता है। प्रवाह को इस प्रतिबंध को स्थापित करना चाहिए कि नोड के भीतर प्रवाह की मात्रा इसके बाहर प्रवाह की मात्रा के बराबर हों, जब तक कि नोड कोई स्रोत या कुंड(सिंक) न हो। नेटवर्क का उपयोग कंप्यूटर नेटवर्क में ट्रैफ़िक, मांगों के साथ परिसंचरण, पाइपों में तरल पदार्थ, विद्युत सर्किट में धाराओं, या कुछ इसी तरह के नोड्स के नेटवर्क के माध्यम से यात्रा करने के लिए किया जा सकता है।
 == परिभाषा ==
-एक नेटवर्क एक निर्देशित ग्राफ है {{math|''G'' {{=}} (''V'', ''E'')}} एक गैर-नकारात्मक क्षमता फ़ंक्शन (गणित) के साथ {{math|''c''}} प्रत्येक किनारे के लिए, और कई चापों के बिना (यानी एक ही स्रोत और लक्ष्य नोड्स वाले किनारे)। [[व्यापकता के नुकसान के बिना]], हम मान सकते हैं कि यदि {{math|(''u'', ''v'') ∈ ''E''}}, तब {{math|(''v'', ''u'')}} का भी सदस्य है {{mvar|E}}. इसके अतिरिक्त, अगर {{math|(''v'', ''u'') ∉ ''E''}} तो हम जोड़ सकते हैं {{math|(''v'', ''u'')}} ई के लिए और फिर सेट करें {{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>
+यदि {{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}} (यानी प्रवेश करने वाले प्रवाह का योग {{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}} सक्रिय है।
+'अतिरिक्त' समारोह {{math|''x''<sub>''f''</sub> : ''V'' → <math>\mathbb{R}</math>}} किसी दिए गए नोड में प्रवेश करने वाले शुद्ध प्रवाह का प्रतिनिधित्व करता है {{mvar|u}} (यानी प्रवेश करने वाले प्रवाह का योग {{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}} सक्रिय है।
 छद्म प्रवाह, व्यवहार्य प्रवाह और पूर्व प्रवाह सभी प्रवाह कार्यों के उदाहरण हैं।
-: एक छद्म प्रवाह एक कार्य है {{math|''f''}} नेटवर्क में प्रत्येक किनारे के लिए जो सभी नोड्स के लिए निम्नलिखित दो बाधाओं को पूरा करता है {{mvar|u}} और {{mvar|v}}:
+: एक छद्म प्रवाह एक कार्य है {{math|''f''}} नेटवर्क में प्रत्येक भुजा के लिए जो सभी नोड्स के लिए निम्नलिखित दो बाधाओं को पूरा करता है {{mvar|u}} और {{mvar|v}}:
 :*तिरछा समरूपता बाधा: से एक चाप पर प्रवाह {{mvar|u}} को {{mvar|v}} से चाप पर प्रवाह की उपेक्षा के बराबर है {{mvar|v}} को {{mvar|u}}, वह है: {{math|''f'' (''u'', ''v'') {{=}} −''f'' (''v'', ''u'')}}. प्रवाह का संकेत प्रवाह की दिशा को इंगित करता है।
 :*क्षमता बाधा: एक चाप का प्रवाह इसकी क्षमता से अधिक नहीं हो सकता है, अर्थात: {{math|''f'' (''u'', ''v'') ≤ ''c''(''u'', ''v'')}}.
@@ Line 26: / Line 26: @@
 : एक व्यवहार्य प्रवाह, या सिर्फ एक प्रवाह, एक छद्म प्रवाह है, जो सभी के लिए है {{math|''v'' ∈ ''V'' \{''s'', ''t''}}}, अतिरिक्त बाधा को पूरा करता है:
 : * प्रवाह संरक्षण बाधा: एक नोड में प्रवेश करने वाला कुल शुद्ध प्रवाह {{mvar|v}} स्रोत को छोड़कर नेटवर्क में सभी नोड्स के लिए शून्य है <math>s</math> और सिंक <math>t</math>, वह है: {{math|''x''<sub>''f''</sub> (''v'') {{=}} 0}} सभी के लिए {{math|''v'' ∈ ''V'' \{''s'', ''t''<nowiki>}</nowiki>}}. दूसरे शब्दों में, स्रोत को छोड़कर नेटवर्क में सभी नोड्स के लिए <math>s</math> और सिंक <math>t</math>, किसी नोड के आने वाले प्रवाह का कुल योग इसके आउटगोइंग प्रवाह के बराबर होता है (अर्थात <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|{{!}} ''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}}.
+मूल्य {{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}}.
 == समस्याओं को प्रवाहित करने के लिए उपयोगी अवधारणाएँ ==
@@ Line 45: / Line 45: @@
 === संवर्धित पथ ===
-एक संवर्धित पथ एक पथ है {{math|(''u''<sub>1</sub>, ''u''<sub>2</sub>, ..., ''u''<sub>''k''</sub>)}} अवशिष्ट नेटवर्क में, जहां {{math|''u''<sub>1</sub> {{=}} ''s''}}, {{math|''u''<sub>''k''</sub> {{=}} ''t''}}, और {{math|for all ''u''<sub>''i''</sub>, ''u''<sub>''i'' + 1</sub> (''c''<sub>''f''</sub> (''u''<sub>''i''</sub>, ''u''<sub>''i'' + 1</sub>) > 0) (1 ≤ i < k)}}. अधिक सरलता से, एक संवर्धित पथ स्रोत से सिंक तक उपलब्ध प्रवाह पथ है। एक नेटवर्क अधिकतम प्रवाह पर है अगर और केवल अगर अवशिष्ट नेटवर्क में कोई संवर्द्धन पथ नहीं है {{math|''G''<sub>''f''</sub>}}.
+एक संवर्धित पथ एक पथ है {{math|(''u''<sub>1</sub>, ''u''<sub>2</sub>, ..., ''u''<sub>''k''</sub>)}} अवशिष्ट नेटवर्क में, जहां {{math|''u''<sub>1</sub> {{=}} ''s''}}, {{math|''u''<sub>''k''</sub> {{=}} ''t''}}, और {{math|for all ''u''<sub>''i''</sub>, ''u''<sub>''i'' + 1</sub> (''c''<sub>''f''</sub> (''u''<sub>''i''</sub>, ''u''<sub>''i'' + 1</sub>) > 0) (1 ≤ i < k)}}. अधिक सरलता से, एक संवर्धित पथ स्रोत से सिंक तक उपलब्ध प्रवाह पथ है। एक नेटवर्क अधिकतम प्रवाह पर है यदि और केवल यदि अवशिष्ट नेटवर्क में कोई संवर्द्धन पथ नहीं है {{math|''G''<sub>''f''</sub>}}.
-टोंटी एक दिए गए संवर्द्धन पथ में सभी किनारों की न्यूनतम अवशिष्ट क्षमता है।<ref name=":0">{{Cite book |last=Kleinberg |first=Jon |url=https://www.worldcat.org/oclc/796210667 |title=Algorithm design |date=2011 |publisher=Addison-Wesley |others=Éva Tardos |isbn=0-13-213108-0 |edition=2nd |location=Boston, Mass. |pages=342, 346 |oclc=796210667}}</ref> इस आलेख के उदाहरण अनुभाग में समझाया गया उदाहरण देखें। प्रवाह नेटवर्क अधिकतम प्रवाह पर है अगर और केवल अगर इसमें शून्य से अधिक मूल्य के साथ बाधा है।
+टोंटी एक दिए गए संवर्द्धन पथ में सभी किनारों की न्यूनतम अवशिष्ट क्षमता है।<ref name=":0">{{Cite book |last=Kleinberg |first=Jon |url=https://www.worldcat.org/oclc/796210667 |title=Algorithm design |date=2011 |publisher=Addison-Wesley |others=Éva Tardos |isbn=0-13-213108-0 |edition=2nd |location=Boston, Mass. |pages=342, 346 |oclc=796210667}}</ref> इस आलेख के उदाहरण अनुभाग में समझाया गया उदाहरण देखें। प्रवाह नेटवर्क अधिकतम प्रवाह पर है यदि और केवल यदि इसमें शून्य से अधिक मूल्य के साथ बाधा है।
 संवर्द्धित पथ के लिए प्रवाह को बढ़ाने का अर्थ प्रवाह को अद्यतन करना है {{mvar|f}} क्षमता के बराबर करने के लिए इस संवर्द्धन पथ में प्रत्येक चाप की {{math|''c''}} अड़चन का। प्रवाह को बढ़ाना संवर्द्धन पथ के साथ अतिरिक्त प्रवाह को तब तक धकेलने से मेल खाता है जब तक कि टोंटी में शेष उपलब्ध अवशिष्ट क्षमता न हो।
 === एकाधिक स्रोत और/या सिंक ===
-कभी-कभी, एक से अधिक स्रोत वाले नेटवर्क को मॉडलिंग करते समय, ग्राफ़ में एक सुपरसोर्स पेश किया जाता है।<ref>{{DADS|Supersource|supersource}}</ref> इसमें अनंत क्षमता के किनारों के साथ प्रत्येक स्रोत से जुड़ा एक शीर्ष होता है, ताकि वैश्विक स्रोत के रूप में कार्य किया जा सके। सिंक के समान निर्माण को सुपरसिंक कहा जाता है।<ref>{{DADS|Supersink|supersink}}</ref>
+कभी-कभी, एक से अधिक स्रोत वाले नेटवर्क को मॉडलिंग करते समय, आरेख़ में एक सुपरसोर्स पेश किया जाता है।<ref>{{DADS|Supersource|supersource}}</ref> इसमें अनंत क्षमता के किनारों के साथ प्रत्येक स्रोत से जुड़ा एक शीर्ष होता है, ताकि वैश्विक स्रोत के रूप में कार्य किया जा सके। सिंक के समान निर्माण को सुपरसिंक कहा जाता है।<ref>{{DADS|Supersink|supersink}}</ref>
@@ Line 58: / Line 58: @@
 [[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>, जो तब संवर्धित पथ हैं।
+[[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>, जो तब संवर्धित पथ हैं।
 की अड़चन <math>(s,a,c,t)</math> पथ के बराबर है <math>\min(c(s,a)-f(s,a), c(a,c)-f(a,c), c(c,t)-f(c,t))</math> <math>=\min(c_f(s,a), c_f(a,c), c_f(c,t))</math> <math>= \min(5-3, 3-2, 2-1)</math> <math>= \min(2, 1, 1) = 1</math>.
@@ Line 74: / Line 74: @@
 == प्रवाह की समस्याओं का वर्गीकरण ==
-प्रवाह नेटवर्क का उपयोग करने वाली सबसे सरल और सबसे आम समस्या यह है कि [[अधिकतम प्रवाह समस्या]] क्या कहलाती है, जो किसी दिए गए ग्राफ में स्रोत से सिंक तक सबसे बड़ा संभव कुल प्रवाह प्रदान करती है। ऐसी कई अन्य समस्याएं हैं जिन्हें अधिकतम प्रवाह एल्गोरिदम का उपयोग करके हल किया जा सकता है, यदि उन्हें प्रवाह नेटवर्क के रूप में उचित रूप से प्रतिरूपित किया जाता है, जैसे द्विदलीय मिलान, असाइनमेंट समस्या और [[परिवहन समस्या]]। अधिकतम प्रवाह की समस्याओं को पुश-रिलेबेल एल्गोरिथम के साथ कुशलतापूर्वक हल किया जा सकता है। [[मैक्स-फ्लो मिन-कट प्रमेय]] बताता है कि एक अधिकतम नेटवर्क प्रवाह खोजना न्यूनतम क्षमता के [[कट (ग्राफ सिद्धांत)]] को खोजने के बराबर है जो स्रोत और सिंक को अलग करता है, जहां कट शीर्षों का विभाजन है जैसे कि स्रोत अंदर है एक डिवीजन और सिंक दूसरे में है।
+प्रवाह नेटवर्क का उपयोग करने वाली सबसे सरल और सबसे आम समस्या यह है कि [[अधिकतम प्रवाह समस्या]] क्या कहलाती है, जो किसी दिए गए आरेख में स्रोत से सिंक तक सबसे बड़ा संभव कुल प्रवाह प्रदान करती है। ऐसी कई अन्य समस्याएं हैं जिन्हें अधिकतम प्रवाह एल्गोरिदम का उपयोग करके हल किया जा सकता है, यदि उन्हें प्रवाह नेटवर्क के रूप में उचित रूप से प्रतिरूपित किया जाता है, जैसे द्विदलीय मिलान, असाइनमेंट समस्या और [[परिवहन समस्या]]। अधिकतम प्रवाह की समस्याओं को पुश-रिलेबेल एल्गोरिथम के साथ कुशलतापूर्वक हल किया जा सकता है। [[मैक्स-फ्लो मिन-कट प्रमेय]] बताता है कि एक अधिकतम नेटवर्क प्रवाह खोजना न्यूनतम क्षमता के [[कट (ग्राफ सिद्धांत)|कट (आरेख सिद्धांत)]] को खोजने के बराबर है जो स्रोत और सिंक को अलग करता है, जहां कट शीर्षों का विभाजन है जैसे कि स्रोत अंदर है एक डिवीजन और सिंक दूसरे में है।
 {| class="wikitable" style="height: 200px;" align="right"
@@ Line 92: / Line 92: @@
 [[बहु-वस्तु प्रवाह समस्या]] में, आपके पास कई स्रोत और सिंक हैं, और विभिन्न कमोडिटीज हैं जो किसी दिए गए स्रोत से दिए गए सिंक में प्रवाहित होती हैं। यह उदाहरण के लिए विभिन्न सामान हो सकते हैं जो विभिन्न कारखानों में उत्पादित होते हैं, और एक ही परिवहन नेटवर्क के माध्यम से विभिन्न ग्राहकों को वितरित किए जाते हैं।
-[[न्यूनतम लागत प्रवाह समस्या]] में, प्रत्येक किनारे <math>u,v</math> एक दी गई लागत है <math>k(u,v)</math>, और प्रवाह भेजने की लागत <math>f(u,v)</math> किनारे के पार है <math>f(u,v) \cdot k(u,v)</math>. इसका उद्देश्य न्यूनतम संभव कीमत पर स्रोत से सिंक तक प्रवाह की एक निश्चित मात्रा भेजना है।
+[[न्यूनतम लागत प्रवाह समस्या]] में, प्रत्येक भुजा <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 शीर्ष पर प्रवाहित होती है।
+एक 'नेटवर्क विद गेन' या 'सामान्यीकृत नेटवर्क' में प्रत्येक भुजा का एक '[[लाभ ग्राफ|लाभ आरेख]]' होता है, एक वास्तविक संख्या (शून्य नहीं) जैसे कि, यदि भुजा का लाभ g है, और एक राशि x इसके सिरे पर भुजा में प्रवाहित होती है, तब एक राशि gx शीर्ष पर प्रवाहित होती है।
 एक 'स्रोत स्थानीयकरण समस्या' में, एक एल्गोरिथ्म आंशिक रूप से देखे गए नेटवर्क के माध्यम से सूचना प्रसार के सबसे संभावित स्रोत नोड की पहचान करने का प्रयास करता है। यह पेड़ों के लिए रैखिक समय और स्वैच्छिक नेटवर्क के लिए घन समय में किया जा सकता है और इसमें मोबाइल फोन उपयोगकर्ताओं को ट्रैक करने से लेकर बीमारी के प्रकोप के मूल स्रोत की पहचान करने तक के अनुप्रयोग हैं।<ref>{{Cite journal| last1 =Pinto| first1 =P.C.| last2 =Thiran| first2 =P.| last3 =Vetterli| first3 =M.| date =2012| title =Locating the source of diffusion in large-scale networks| url =http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf| journal =Physical Review Letters| volume =109| issue =6| page =068702| doi =10.1103/PhysRevLett.109.068702| pmid =23006310| arxiv =1208.2534| bibcode =2012PhRvL.109f8702P| s2cid =14526887| access-date =2012-08-14| archive-date =2012-10-22| archive-url =https://web.archive.org/web/20121022084454/http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf| url-status =live}}</ref>
@@ Line 107: / Line 107: @@
 * डिनिक का एल्गोरिदम
 * [[प्रवाह (कंप्यूटर नेटवर्किंग)]]
-* फ्लो ग्राफ (बहुविकल्पी)
+* फ्लो आरेख (बहुविकल्पी)
 * मैक्स-फ्लो मिन-कट प्रमेय
 * [[ओरिएंटेड मैट्रोइड]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 04:26, 19 February 2023

Contents

परिभाषा

प्रवाह