ग्राफ़ में अधिकतम प्रवाह खोजने के लिए, बैक किनारों पर विचार किए बिना उस पथ में न्यूनतम किनारे की क्षमता वाले सभी संवर्द्धन पथों को केवल संतृप्त करने के लिए पर्याप्त क्यों नहीं है? मेरा मतलब है, अगर हम इससे प्रवाह मानते हैं तो यह बिंदु क्या है?फोर्ड-फुलकर्सन एल्गोरिदम में बैक किनारों की आवश्यकता क्यों है?
फोर्ड-फुलकर्सन एल्गोरिदम करते समय पीछे किनारों की आवश्यकता होती है यदि आपके द्वारा चुने गए पथ को समग्र प्रवाह का हिस्सा नहीं बनता है।
एक उदाहरण है जहां वापस किनारों के लिए आवश्यक हैं के रूप में, इस प्रवाह नेटवर्क पर विचार करें:
s
/\
a b
\/\
c d
\/
t
मान लें कि सभी किनारों नीचे इंगित करें और सभी किनारों क्षमता 1 है और आप टी के एस से एक प्रवाह पता लगाना चाहते हैं कि । मान लें कि फोर्ड-फुलकर्सन के पहले पुनरावृत्ति पर आप पथ लेते हैं -> बी -> सी -> टी। इस बिंदु पर, आपने प्रवाह की एक इकाई को टी से टी तक धक्का दिया है। आप किसी भी पृष्ठ किनारों में शामिल नहीं करते हैं, तो आप इस के साथ छोड़ दिया जाता है:
s
/
a b
\ \
c d
/
t
कोई और अधिक एस टी पथ होते हैं, लेकिन इसका मतलब यह नहीं है कि आप एक अधिकतम प्रवाह की है। आप मार्गों के साथ एक को भेजकर एस से टी तक प्रवाह की दो इकाइयों को धक्का दे सकते हैं -> ए -> सी -> टी और दूसरे पथ के साथ -> बी -> डी -> टी। अवशिष्ट प्रवाह नेटवर्क में किसी भी पीछे किनारों के बिना, आप इस अन्य पथ को कभी नहीं खोज पाएंगे।
आशा है कि इससे मदद मिलती है!
क्या आप कृपया अपने विवरण में बैकजेज बनाने के बारे में अधिक जानकारी दे सकते हैं? धन्यवाद! – bluejamesbond
@bluejamesbond यहां, पीछे किनारों से बी से एस, सी से बी तक, और टी से सी तक इंगित किया जाएगा (यह किनारों के विपरीत किनारों के विपरीत है)। तब किनारों से एस से टी तक एक बढ़ता पथ मिलता है जो दर्शाता है कि प्रवाह अधिकतम नहीं है। – templatetypedef
हालांकि ये पथ कब लेंगे? – bluejamesbond