मान लीजिए कि ग्राफ़ में 3 लक्ष्य नोड्स हैं।ग्राफ में सभी vertex-disjoint पथ कैसे खोजें?
एक कशेरुक-विवाद पथ का अर्थ है पथ के दौरान अंत नोड को छोड़कर कोई भी नोड नहीं है।
किसी एक एकल नोड के लिए, नोड i कहें, नोड i से तीन लक्ष्य नोड्स तक सभी vertex-disjoint पथ कैसे खोजें?
आप उचित रूप से निर्मित ग्राफ में अधिकतम प्रवाह समस्या को कम करके इस समस्या को हल कर सकते हैं। विचार इस प्रकार है:
इस निर्माण के पीछे विचार इस प्रकार है। प्रारंभ नोड से गंतव्य नोड टी तक के किसी भी प्रवाह पथ में क्षमता एक होना चाहिए, क्योंकि सभी किनारों में क्षमता एक होती है। चूंकि सभी क्षमताओं अभिन्न हैं, एक अभिन्न अधिकतम प्रवाह मौजूद है। कोई भी दो प्रवाह पथ एक ही मध्यवर्ती नोड से गुजर सकता है, क्योंकि ग्राफ में नोड से गुजरने के कारण प्रवाह पथ कोसे में से किनारे को पार करना होगा, और यहां क्षमता एक तक सीमित कर दी गई है। इसके अतिरिक्त, यह प्रवाह पथ आपके द्वारा पहचाने गए तीन विशेष नोड्स में से एक पर समाप्त होने पर टी पर पहुंचना चाहिए, फिर उस नोड से किनारे के किनारे पर। इस प्रकार प्रत्येक प्रवाह पथ स्रोत नोड से तीन नोड्स में से एक में नोड-डिजॉइंट पथ का प्रतिनिधित्व करता है। तदनुसार, यहां एक अधिकतम प्रवाह की गणना करने से आप नोड-डिज्जॉइंट पथों की अधिकतम संख्या को खोज सकते हैं जिन्हें आप तीनों गंतव्यों में से किसी एक से ले जा सकते हैं।
आशा है कि इससे मदद मिलती है!
शायद मेरी अभिव्यक्ति abte vertex-disjoint पर्याप्त स्पष्ट नहीं है। नोड एस और नोड टी के लिए, एक पथ एस-> ए-> बी-> सी-> डी-> टी है, एस से भी एक और रास्ता शुरू होता है-> e-> f-> g-> h -> टी। इस मामले में, यह एक कशेरुक-विवाद पथ है। लेकिन अगर एस-> ई-> एफ-> जी-> डी-> टी के रूप में कोई रास्ता है, तो यह एक कट्टरपंथी विवाद नहीं है। – datcn
@templatetypedef यह एक बहुत अच्छी व्याख्या है। धन्यवाद ! – ggauravr
इस समाधान का चलने वाला समय क्या होगा? ओ (एनएम)? – razshan
स्पष्ट होने के लिए, आपका मतलब है कि 'i' से शुरू होने वाला पथ, तीन लक्ष्य नोड्स में से प्रत्येक के माध्यम से जाता है, और फिर दोहराए बिना दोहराए बिना दोहराए जाते हैं सिवाय इसके कि दो सिरों समान हैं? साथ ही, क्या आप ऐसे सभी पथ ढूंढना चाहते हैं (जैसे आप कहते हैं) या सबसे छोटा रास्ता (जैसे इसे टैग किया गया है)? – Dougal
मेरे उद्देश्य में, मैं नोड i से शुरू करने वाला पथ ढूंढना चाहता हूं और लक्ष्य नोड पर परिष्करण करना चाहता हूं, नोड जेड कहें। यदि एक से अधिक पथ हैं, तो नोड्स i और node z को छोड़कर इन पथों में कोई भी नोड्स नहीं होना चाहिए। मैं इन सभी पथों को i से z तक ढूंढने की आशा करता हूं। – datcn
ओह, यह मैं (और templatetypedef) समझने से बहुत अलग है। तो आप 'i' से' z' तक पथों का एक सेट खोजना चाहते हैं जैसे कि पथ अलग हैं? संभावित रूप से ऐसे कई सेट हैं (आपके द्वारा चुने गए संभावित पथों के आधार पर)। तो हो सकता है कि आप जो करना चाहते हैं वह 'i' से' z' (उदाहरण के लिए चौड़ाई-पहली खोज के माध्यम से) के सभी पथ ढूंढें और फिर उन्हें एक पृथक सेट खोजने के लिए संसाधित करें। ऐसा करने का एक आसान तरीका, जो इस तरह का सबसे बड़ा सेट या कुछ भी नहीं मिलेगा: सेट से पथ चुनें, उस पथ को छेड़छाड़ करने वाले सभी अन्य पथों को हटा दें, दोहराएं। – Dougal