नेटवर्क फ्लो एल्गोरिदम
नेटवर्क फ्लो एल्गोरिदम एक कैपेसिटेटेड नेटवर्क के माध्यम से एक स्रोत से एक सिंक तक भेजे जा सकने वाले प्रवाह की अधिकतम मात्रा की गणना करते हैं, एक ऐसी समस्या जिसका इष्टतम द्वैतता द्वारा नेटवर्क के न्यूनतम कट से जुड़ा होता है।
Definition
एक प्रवाह नेटवर्क किनारों की क्षमताओं, एक स्रोत और एक सिंक के साथ एक निर्देशित ग्राफ है; एक अधिकतम-प्रवाह एल्गोरिदम किनारों को प्रवाह का एक असाइनमेंट ढूंढता है, जो क्षमताओं और मध्यवर्ती शीर्षों पर संरक्षण का सम्मान करता है, जो स्रोत से सिंक तक कुल प्रवाह को अधिकतम करता है।
Scope
यह विषय अधिकतम-प्रवाह समस्या और इसके एल्गोरिदम को कवर करता है: संवर्धित पथों के साथ फोर्ड-फुलकर्सन विधि, एडमंड्स-कार्प और डिनिक के शोधन जो चलने के समय को सीमित करते हैं, और अधिकतम-प्रवाह न्यूनतम-कट प्रमेय जो इष्टतम को दर्शाता है। यह अन्य समस्याओं — द्विदलीय मिलान (bipartite matching), शीर्ष-असंयुक्त पथ (vertex-disjoint paths), परियोजना चयन (project selection) — को नेटवर्क प्रवाह में कम करने को भी कवर करता है। इसमें सामान्य रैखिक प्रोग्रामिंग (linear programming) शामिल नहीं है, जिसका प्रवाह एक विशेष मामला है।
Core questions
- प्रवाह को कैसे परिभाषित किया जाता है, और उसे किन बाधाओं को पूरा करना चाहिए?
- अवशिष्ट ग्राफ (residual graph) में संवर्धित पथ (augmenting paths) अधिकतम की ओर प्रवाह को कैसे बढ़ाते हैं?
- अधिकतम प्रवाह न्यूनतम कट क्षमता के बराबर क्यों होता है?
- एडमंड्स-कार्प और डिनिक का एल्गोरिदम बहुपद चलने के समय की गारंटी कैसे देता है?
- मिलान (matching) और अन्य समस्याओं को अधिकतम प्रवाह में कैसे कम किया जाता है?
Key concepts
- प्रवाह नेटवर्क (flow network)
- क्षमता और संरक्षण (capacity and conservation)
- संवर्धित पथ (augmenting path)
- अवशिष्ट ग्राफ (residual graph)
- अधिकतम-प्रवाह न्यूनतम-कट प्रमेय (max-flow min-cut theorem)
- एडमंड्स-कार्प एल्गोरिदम (Edmonds-Karp algorithm)
- डिनिक का एल्गोरिदम (Dinic's algorithm)
- द्विदलीय मिलान कमी (bipartite matching reduction)
Key theories
- अधिकतम-प्रवाह न्यूनतम-कट प्रमेय
- स्रोत से सिंक तक अधिकतम प्रवाह का मान उन्हें अलग करने वाले कट की न्यूनतम क्षमता के बराबर होता है; फोर्ड और फुलकर्सन के कारण यह द्वैतता, इष्टतमता को प्रमाणित करती है और प्रवाह को कनेक्टिविटी और विभाजन समस्याओं से जोड़ती है।
- संवर्धित पथ और अवशिष्ट ग्राफ
- फोर्ड-फुलकर्सन विधि अवशिष्ट ग्राफ में अतिरिक्त क्षमता वाले पथों को ढूंढकर प्रवाह को बढ़ाती है; सबसे छोटे संवर्धित पथों (एडमंड्स-कार्प) का चयन करना या स्तर ग्राफ और अवरुद्ध प्रवाह (डिनिक) का उपयोग करना बहुपद-समय की गारंटी देता है।
Clinical relevance
नेटवर्क प्रवाह एक बहुमुखी मॉडलिंग उपकरण है: यह द्विदलीय असाइनमेंट और शेड्यूलिंग को हल करता है, नेटवर्क की कनेक्टिविटी और विश्वसनीयता की गणना करता है, कंप्यूटर विजन में ग्राफ कट के माध्यम से छवि विभाजन करता है, और रसद, परिवहन योजना और परियोजना-चयन अनुकूलन को रेखांकित करता है जहां क्षमताएं और बाधाएं मायने रखती हैं।
History
फोर्ड और फुलकर्सन ने 1956 में परिवहन नेटवर्क का अध्ययन करते हुए अधिकतम-प्रवाह समस्या और अधिकतम-प्रवाह न्यूनतम-कट प्रमेय प्रस्तुत किया। एडमंड्स और कार्प (1972) और, स्वतंत्र रूप से, डिनिक (1970) ने पहले बहुपद-समय एल्गोरिदम दिए, और बाद के काम ने अधिकतम प्रवाह के स्पर्शोन्मुख चलने के समय में लगातार सुधार किया है।
Key figures
- Lester Ford
- Delbert Fulkerson
- Jack Edmonds
- Yefim Dinic
Related topics
Seminal works
- fordfulkerson1956
- cormen2009
Frequently asked questions
- अधिकतम-प्रवाह न्यूनतम-कट प्रमेय वास्तव में क्या कहता है?
- यह बताता है कि स्रोत से सिंक तक आप जितना अधिकतम प्रवाह धकेल सकते हैं, वह किनारों के किसी भी सेट की सबसे छोटी कुल क्षमता के बराबर होता है जिसे हटाने से स्रोत सिंक से डिस्कनेक्ट हो जाता है। न्यूनतम कट एक बाधा के रूप में कार्य करता है जो अधिकतम प्रवाह को सीमित करता है।
- साधारण फोर्ड-फुलकर्सन का बहुपद चलने का समय क्यों नहीं होता है?
- यदि संवर्धित पथों को खराब तरीके से चुना जाता है और क्षमताएं बड़ी (या अपरिमेय) होती हैं, तो संवर्धनों की संख्या बहुत अधिक हो सकती है या समाप्त होने में विफल भी हो सकती है। सबसे छोटे संवर्धित पथों (एडमंड्स-कार्प) का चयन करना या अवरुद्ध प्रवाह (डिनिक) का उपयोग करना संवर्धनों की संख्या को सीमित करता है और बहुपद समय देता है।