हमने K शीर्षों वाला एक नेटवर्क दिया और a और b दिए। सभी किनारों की क्षमता infinite है। a से b तक प्रवाह के लिए, जो किनारा max flow से होकर गुजरता है, उसे टोंटीदार किनारा कहा जाता है और उस किनारे से स्थानांतरित प्रवाह की क्षमता को प्रवाह की अड़चन कहा जाता है। एक पूर्णांक M दिया गया है। हम आकार M के साथ स्थानांतरण प्रवाह चाहते हैं, जिसमें सबसे कम अड़चन a से b हो। इस प्रवाह की गणना के लिए हमें कितनी बार फोर्ड-फुलकर्सन का उपयोग करना चाहिए?

ओ (1) रन उत्तर है, लेकिन कैसे?

1
user9851867 28 नवम्बर 2020, 06:02

1 उत्तर

सबसे बढ़िया उत्तर

मान लें कि आप प्रत्येक किनारे को क्षमता 1 असाइन करते हैं, एक बार एफएफ चलाएं, और परिणामी ग्राफ प्राप्त करें। इसके अलावा, अधिकतम प्रवाह M' होने दें। सहज रूप से, हम पाते हैं कि न्यूनतम कट $M'$ है, जिसका अर्थ है कि इस मामले में M' एज-डिसजॉइंट पथ हैं जो a से b तक हैं। यह हमें बताता है कि प्रवाह को उचित रूप से स्केल करके ⌈ M / M' ⌉ का समाधान कैसे प्राप्त किया जाए। उदाहरण के लिए, मान लीजिए कि $M=5$, और क्षमता को 1 पर सेट करने पर हमें $M' = 2$ मिलता है। तब हम जानते हैं कि न्यूनतम कटौती 2 है। यदि हम क्षमता को 5/2 = 2.5 तक बढ़ा देते हैं, तो हमें शुरुआत में 5 का प्रवाह मिलेगा। चूंकि यह एक गैर-पूर्णांक है, इसलिए हम कुछ किनारों (ए से बी तक पथ बनाने) की क्षमता को बढ़ाकर 3 कर देंगे, और कुछ को 2 तक बढ़ा देंगे।

जो अभी मिला है उससे कम कुछ नहीं मिल सकता। यदि आप कुछ कम प्राप्त कर सकते हैं, तो M'' < M / M' ⌉ कहें, तो यदि आप सभी किनारों की क्षमता M'' पर सेट करेंगे, तो प्रवाह नहीं बदलेगा। मैक्स-फ्लो / मिन-कट प्रमेय से, इसका मतलब है कि M / M''> M' किनारों का एक मिन-कट है। यह केवल M' के न्यूनतम कट के विपरीत है।

0
Ami Tavory 28 नवम्बर 2020, 11:27