▶

अधिकतम प्रवाह कैलकुलेटर (Max Flow)

Edmonds-Karp · बढ़ते पथ (Augmenting Paths) · न्यूनतम कट (Min-Cut) · प्रवाह विज़ुअलाइज़ेशन

एक निर्देशित क्षमता नेटवर्क में स्रोत से गंतव्य तक अधिकतम प्रवाह ज्ञात करें। चरण-दर-चरण बढ़ते पथों और कैनवास विज़ुअलाइज़ेशन के साथ Edmonds-Karp एल्गोरिदम (BFS Ford-Fulkerson, O(VE²)) का उपयोग करता है।

त्वरित उदाहरण (Quick Examples)

समर्थित प्रारूप: S A 10   S→A:10   S-A-10

अधिकतम प्रवाह समस्या (Maximum Flow Problem) क्या है?

अधिकतम प्रवाह समस्या कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन और नेटवर्क थ्योरी में सबसे मौलिक समस्याओं में से एक है। एक निर्देशित ग्राफ दिया गया है जहाँ प्रत्येक किनारे की एक गैर-ऋणात्मक क्षमता (capacity) होती है — अधिकतम मात्रा में प्रवाह जिसे वह ले जा सकता है। इसका लक्ष्य एक निर्दिष्ट स्रोत नोड (source node) से एक निर्दिष्ट गंतव्य नोड (sink node) तक भेजे जा सकने वाले प्रवाह की अधिकतम मात्रा का निर्धारण करना है, बशर्ते प्रवाह दो शर्तों के अधीन हो: प्रत्येक किनारे पर प्रवाह उसकी क्षमता से अधिक नहीं होना चाहिए, और प्रत्येक मध्यवर्ती नोड पर प्रवाह संरक्षित रहना चाहिए (इनफ्लो = आउटफ्लो)।

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

Ford-Fulkerson विधि

1956 में एल.आर. फोर्ड जूनियर और डी.आर. फुल्करसन द्वारा पेश की गई Ford-Fulkerson विधि, अधिकतम प्रवाह समस्याओं को हल करने का आधार है। यह विधि एक अवशिष्ट ग्राफ (residual graph) को बनाए रखती है जो शेष बची हुई क्षमता को दर्शाता है। प्रत्येक चरण में यह अवशिष्ट ग्राफ में स्रोत से गंतव्य तक एक बढ़ता पथ (augmenting path) खोजती है और उस पथ की न्यूनतम क्षमता के बराबर प्रवाह को आगे बढ़ाती है। जब कोई बढ़ता पथ नहीं बचता, तो एल्गोरिदम इष्टतम समाधान के साथ समाप्त हो जाता है।

Ford-Fulkerson एक फ्रेमवर्क है, न कि एक विशिष्ट एल्गोरिदम, क्योंकि यह यह निर्दिष्ट नहीं करता है कि बढ़ते पथों को कैसे खोजा जाए। अलग-अलग खोज रणनीतियाँ अलग-अलग एल्गोरिदम और समय जटिलता देती हैं। BFS का उपयोग करके बनाया गया Edmonds-Karp एल्गोरिदम बहुपद समय (polynomial time) देता है।

Edmonds-Karp एल्गोरिदम

1972 में जैक एडमंड्स और रिचर्ड कार्प द्वारा स्वतंत्र रूप से खोजा गया Edmonds-Karp एल्गोरिदम, ब्रेडथ-फर्स्ट सर्च (BFS) का उपयोग करके Ford-Fulkerson का एक विशिष्ट कार्यान्वयन है। BFS का यह सरल उपयोग बहुपद समय जटिलता प्रदान करता है:

  • प्रत्येक BFS सबसे छोटे पथ को O(V + E) समय में खोजता है।
  • बढ़ते पथों की कुल पुनरावृत्ति O(VE) तक सीमित है।
  • कुल समय जटिलता: O(VE²) जहाँ V = नोड्स, E = किनारे हैं।

Max-Flow Min-Cut प्रमेय

Max-Flow Min-Cut प्रमेय एक युगांतरकारी परिणाम है जो बताता है कि किसी भी प्रवाह नेटवर्क के लिए, अधिकतम प्रवाह न्यूनतम कट की क्षमता के बराबर होता है। एक कट नोड्स को दो सेटों S (स्रोत सहित) और T (गंतव्य सहित) में विभाजित करना है; इसकी क्षमता S से T की ओर जाने वाले किनारों की क्षमता का योग है। न्यूनतम कट सबसे छोटी क्षमता वाला कट है।

यह प्रमेय नेटवर्क की सबसे संकरी जगह (bottleneck) की पहचान करता है। परिवहन नेटवर्क में, न्यूनतम कट उन रास्तों के सेट की पहचान करता है जो समग्र थ्रूपुट को सीमित करते हैं।

अनुप्रयोग

  • इंटरनेट रूटिंग: नेटवर्क नोड्स के बीच डेटा पैकेट थ्रूपुट को अधिकतम करना।
  • द्विदलीय मिलान (Bipartite Matching): नौकरी शेड्यूलिंग और असाइनमेंट समस्याओं को हल करना।
  • छवि विभाजन (Image Segmentation): कंप्यूटर विज़न में छवि से अग्रभूमि (foreground) और पृष्ठभूमि (background) को अलग करना।
  • आपूर्ति श्रृंखला ऑप्टिमाइज़ेशन: रसद नेटवर्क के माध्यम से सामान भेजने की क्षमता बढ़ाना।
  • नेटवर्क विश्वसनीयता: उन महत्वपूर्ण रास्तों की पहचान करना जिनके टूटने से नेटवर्क क्षमता सबसे अधिक प्रभावित होगी।

अक्सर पूछे जाने वाले प्रश्न (FAQ)

अधिकतम प्रवाह समस्या क्या है?
अधिकतम प्रवाह समस्या में, एक निर्देशित ग्राफ में स्रोत से गंतव्य तक भेजे जा सकने वाले प्रवाह की कुल अधिकतम मात्रा ज्ञात की जाती है, जो किनारे की क्षमताओं और मध्यवर्ती नोड्स पर प्रवाह संरक्षण के अधीन होती है।
Ford-Fulkerson और Edmonds-Karp में क्या अंतर है?
Ford-Fulkerson एक व्यापक विधि है जो बढ़ते पथों को बार-बार खोजती है। Edmonds-Karp इसका एक विशिष्ट कार्यान्वयन है जो सबसे छोटे बढ़ते पथ को खोजने के लिए BFS (ब्रेडथ-फर्स्ट सर्च) का उपयोग करता है। यह BFS का उपयोग इसकी समय जटिलता को O(VE²) पर स्थिर और कुशल बनाता है।
Max-Flow Min-Cut प्रमेय क्यों महत्वपूर्ण है?
यह प्रमेय गणितीय रूप से साबित करता है कि नेटवर्क का अधिकतम प्रवाह उसके सबसे संकरे हिस्से (minimum cut) की क्षमता के बिल्कुल बराबर होता है। यह एल्गोरिदम को एक ही गणना से नेटवर्क के प्रवाह और उसकी बाधाओं (bottlenecks) दोनों को खोजने की अनुमति देता है।
अवशिष्ट ग्राफ (Residual Graph) क्या करता है?
अवशिष्ट ग्राफ यह दर्शाता है कि प्रत्येक किनारे पर आगे और पीछे की दिशा में और कितना प्रवाह भेजा जा सकता है। पीछे की दिशा के किनारे (backward edges) एल्गोरिदम को पहले से आवंटित प्रवाह को वापस लेने (undo) और बेहतर इष्टतम रास्ते तलाशने का अवसर देते हैं।

संबंधित कैलकुलेटर

D
Dijkstra का सबसे छोटा पथ
M
न्यूनतम फैलाव वृक्ष (MST)
A
आसन्नता मैट्रिक्स कैलकुलेटर
L
रैखिक प्रोग्रामिंग सॉल्वर (LPP)

ग्राफ नियम

किनारों को Source Target Capacity प्रारूप में दर्ज करें।

जैसे:
S A 10 A T 5