समस्या:अधिकतम प्रवाह - वर्टेक्स के माध्यम से - कैसे?
चलो जी = (वी, ई) एम किनारों के साथ n> = 3 शीर्षकों पर एक निर्देशित ग्राफ हो। वर्टेक्स सेट वी में तीन विशेष वर्टिस ए, वी, और बी शामिल हैं। यदि यह मौजूद है तो v से v के माध्यम से एक सरल पथ पाएं। (एक साधारण पथ दोहराए गए शिखर के बिना एक पथ है।)
मुझे विश्वास है कि इस समस्या को मैक्स फ्लो एल्गोरिदम के साथ हल किया जाना चाहिए/लेकिन मुझे यकीन नहीं है कि कैसे। यह मुझे कई स्रोतों के साथ मैक्स फ्लो एल्गोरिदम की याद दिलाता है जहां किनारों की क्षमता 1 है। किसी को भी पता है कि समस्या को अधिकतम प्रवाह एल्गोरिदम में कैसे कम किया जा सकता है?
यदि मैं वर्टेक्स बी को सिंक के रूप में सेट करता हूं तो मुझे यकीन नहीं है कि इसमें वी शामिल होगा। अगर मैं सिंक के रूप में सेट करता हूं तो वी जारी होने पर मैं कैसे जारी रखूं?
क्या बी बी के दूसरे पथ का स्रोत नहीं होगा? – Mikeb
आप Google पर "अधिकतम प्रवाह निचला बाउंड" आज़मा सकते हैं। यदि आप वर्टेक्स वी के माध्यम से 1 का न्यूनतम प्रवाह लागू करते हैं, तो आपके पास अनिवार्य रूप से v। – phimuemue
@Mikeb के माध्यम से पथ है I ऐसा नहीं लगता है। ए-> वी से प्रवाह एक ऐसा मार्ग हो सकता है जो मुझे लगता है कि वी-बी से प्रवाह करना असंभव हो जाता है। –