ग्राफ़ में न्यूनतम कट खोजें जैसे कि दिए गए कोने डिस्कनेक्ट किए गए हैं

Question

कुछ समय पहले मैंने सामान्य मिनिनम कट एल्गोरिदम के बारे में पढ़ा था जो एक ग्राफ इनपुट के रूप में लेता है और एक मिनट हटा देता है। किनारों की संख्या जैसे कि दो डिस्कनेक्ट किए गए घटक बने रहते हैं।

अब मैं 10k + नोड्स और 500k + किनारों (दो शीर्षकों के बीच कोई एकाधिक किनारों) के साथ एक अप्रत्यक्ष ग्राफ पर काम कर रहा हूं। नोड्स के बीच इंटरैक्शन को श्रेय देने के लिए मैंने दो दिए गए शिखर (या प्रवाह से संबंधित उपायों) को डिस्कनेक्ट करने वाले न्यूनतम कट की गणना करने के बारे में सोचा।

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

धन्यवाद!

Answer 1

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

किसी भी जोड़ी के लिए, आप इस जोड़ी में स्रोत/सिंक सेट करके ग्राफ़ से नेटवर्क बनाते हैं। आपको एल्गोरिदम का उपयोग करके अधिकतम प्रवाह मिलता है, जिसका उपयोग आप कट को प्राप्त करने के लिए करते हैं:

• प्रवाह द्वारा उपयोग किए जाने वाले किसी किनारे का चयन करें। यह किनारा कटौती से संबंधित होगा। जब तक प्रवाह 0

अंत में है

दोहराएँ, लेकिन अब चयनित बढ़त (रों) के बिना एक ग्राफ पर प्रवाह खोज करते हैं, तो आप कम से कम कटौती, अधिकतम प्रवाह के आकार की है।

यदि आप वास्तव में प्रदर्शन पर दबाव डालना चाहते हैं, तो आप इस पेपर को देखना चाहेंगे: Flows in Undirected Unit Capacity Networks (1997) एंड्रयू वी। गोल्डबर्ग, सतीश राव द्वारा, लेकिन शायद मैं सरल लोगों के साथ रहूंगा।