शिखर/नोड्स के माध्यम से न्यूनतम कट - किनारों

Question

हम सभी जानते हैं और एस-टी न्यूनतम कट एल्गोरिदम प्यार करते हैं, लेकिन वे सभी ग्राफ में किनारों से काटते हैं। क्या कोई वेरिएंट हैं जो नोड्स के माध्यम से कटौती करते हैं?

Answer 1

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

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

मुझे उम्मीद है कि यह समझ में आता है। मुझे यकीन नहीं है कि यह काम करता है (यानी मुझे उचित सबूत सोचने की तरह महसूस नहीं होता), लेकिन यह सहज ज्ञान देता है कि यह होगा। मेरे पास सहज ज्ञान युक्त विचार यह है कि यदि आप "गैर-चरम" किनारे काटते हैं, तो आप "कशेरुक" किनारे को भी काट सकते हैं क्योंकि ग्राफ़ को डिस्कनेक्ट करने के लिए इसका एक ही प्रभाव w.r.t है।