एडमंड्स-कार्प एल्गोरिदम एक ग्राफ के लिए जिसमें प्रवाह क्षमताओं के साथ नोड्स हैं

Question

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

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

किसी भी विचार की बहुत सराहना की जाएगी।

अग्रिम धन्यवाद।

अपने ग्राफ़ के हर शिखर v के लिए, दो कोने v_in और v_out के साथ बदलें:

Answer 1

एक सरल एक नियमित रूप से अधिकतम प्रवाह समस्या के लिए नोड क्षमता के साथ अधिकतम प्रवाह समस्या से कमी नहीं है। प्रत्येक आने वाले किनारे v को v_in पर इंगित करना चाहिए और v से प्रत्येक आउटगोइंग किनारे v_out से इंगित करना चाहिए। फिर v_in से v_out से क्षमता c_v के साथ एक अतिरिक्त किनारा बनाएं, vertex v की क्षमता।

तो आप बस परिवर्तित ग्राफ पर एडमंड्स-कार्प चलाएं।

s --> v_in --> v_out --> t 
    1  2   1 

:

s --> v --> t 
    1 2 1 

यह अधिकतम प्रवाह समस्या में इस ग्राफ के अनुरूप होगा:

तो मान लीजिए कि आप अपनी समस्या में निम्नलिखित ग्राफ डालते हैं (शिखर v क्षमता 2 है) यह स्पष्ट होना चाहिए कि प्राप्त अधिकतम प्रवाह समाधान है (और यह साबित करना विशेष रूप से मुश्किल नहीं है)।