क्रैब ग्राफ, एल्गोरिदम, ग्राफ थ्योरी, यह नेटवर्क कैसे प्रवाह होता है?

Question

क्या कोई इस समस्या से मेरी मदद कर सकता है? समाधान स्पष्ट रूप से नेटवर्क प्रवाह का उपयोग कर रहा है लेकिन मैं नेटवर्क प्रवाह से बहुत परिचित नहीं हूं। नेटवर्क प्रवाह कैसे आपको हल करने में मदद करता है?

एक केकड़ा एक अप्रत्यक्ष ग्राफ है जिसमें दो प्रकार के शिखर होते हैं: 1 सिर, और के पैर, और बिल्कुल के किनारों जो प्रत्येक पैर में सिर में शामिल होते हैं। (1 < = के < = टी, जहां टी है दिया गया)

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

नोट: दो ग्राफ़ वर्टेक्स-डिसजॉइंट हैं यदि उनके पास कोई कशेरुका सामान्य नहीं है।

पूर्व। इनपुट

8 2 7 
1 4 
2 4 
3 4 
5 4 
5 8 
5 7 
5 6 

Answer 1

द्वारा घातीय टिम एल्गोरिथ्म में शीर्ष कवर दृष्टिकोण परिणामों के ऊपर समस्या का समाधान करना है, लेकिन यह फोर्ड Fulkerson एल्गोरिथ्म फोर्ड Fulkerson का उपयोग कर से ऊपर समस्या हल किया जा सकता का उपयोग कर अधिकतम प्रवाह द्वारा हल किया जा सकता है।

1. क्षमता = टी के साथ ग्राफ के सभी नोड्स में स्रोत (0) से पथ बनाएं।
2. सभी नोड्स से लक्ष्य (1) से क्षमता = 1
3. फोर्ड फुलकर्सन का उपयोग करके उपरोक्त संशोधित ग्राफ का अधिकतम प्रवाह खोजें।

फोर्ड Fulkerson एल्गोरिथ्म दिया ग्राफ़

1. में अधिकतम प्रवाह को खोजने के लिए ग्राफ में लक्षित करने के लिए स्रोत से एक पथ का पता लगाएं।
2. पथ के साथ न्यूनतम प्रवाह खोजें।
4. से ऊपर की न्यूनतम प्रवाह द्वारा पथ के साथ सभी किनारों के प्रवाह को बढ़ाएं पथ के न्यूनतम प्रवाह को स्टोर करें।

उपरोक्त 4 चरणों को दोहराएं जब तक कि कोई भी संभावित मार्ग संभव न हो। फोर्ड Fulkerson Alogrithm के लिए

स्पष्टीकरण

एक संभावित रास्ता चुना और सबसे छोटी क्षमता के साथ बढ़त की पहचान। इस नंबर को रिकॉर्ड करें इस पथ पर प्रत्येक संख्या से इस नंबर को सार करें। प्रत्येक चाप के रास्ते के लिए यह नई क्षमता है। एक और मार्ग चुनें और चरण 1 दोहराएं एक बार फिर सबसे छोटी क्षमता रिकॉर्ड करें। सभी संभावित पथ समाप्त होने तक दोहराएं। सभी मार्गों की सबसे छोटी क्षमताओं को जोड़ें। इस नेटवर्क

संदर्भ

http://anandtechblog.blogspot.in/search/label/Ford%20Fulkerson%20algorithm

Answer 2

यह vertex cover समस्या है। एक ग्राफ के कशेरुक कवर के साथ, केकड़े के सिर एक कशेरुक कवर के शिखर होते हैं, और पैर इन सिर से जुड़े शिखर होते हैं। डुप्लिकेट पैर, हटा दिया जाना चाहिए एक देखभाल :-) एक केकड़ा के सभी पैर दूर करने के लिए नहीं है, जबकि

अद्यतन:

मिनिमल शीर्ष कवर एक एन पी-सम्पूर्ण, क्या अच्छा :-) नहीं है मुझे लगता है कि केकड़ा कवर बराबर है। कम से कम न्यूनतम केकड़ा कवर होने पर हम न्यूनतम वर्टेक्स कवर प्राप्त कर सकते हैं। इसलिए, यदि न्यूनतम क्रैब एनपी-पूर्ण में नहीं है, तो न्यूनतम वर्टेक्स कवर से भी एनपी-पूर्ण नहीं होना चाहिए।

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

Answer 3

सोचो कैसे नेटवर्क प्रवाह इस समस्या को लागू किया जा सकता कर सकते हैं की न्यूनतम ले जाने की क्षमता है। ऐसा कुछ ऐसा होना चाहिए जैसे प्रवाह केकड़ा के सिर से उसके पैरों तक गुजरता है। और सिर पर आने वाले प्रवाह में पैरों की संख्या के बराबर मूल्य होना चाहिए और सिर के पैर से केब के प्रत्येक किनारे में क्षमता एक होनी चाहिए।

हम इसे कैसे प्राप्त कर सकते हैं? अपने आप से इस पर आना निश्चित रूप से कठिन है, लेकिन मुझे आशा है कि उदाहरण को कई बार देखने के बाद आप इसे लटका सकते हैं।

हमें एक नया ग्राफ बनाना है जहां मूल शिखर डुप्लीकेट हैं। एक सेट प्रत्येक कशेरुक को सिर होने का मौका देने के लिए दे सकता है और दूसरा सेट पैर के रूप में कार्य कर सकता है। इसे ध्यान में रखते हुए, सटीक algo निम्नलिखित के रूप में लिखा जा सकता है: -

1. We create a new graph where original vertices are duplicated (vertex i becomes 2*i (head set) and 2*i+1 (feet set) ). 

2.For i and j vertices connected in original graph make sure that 2*i and 2*j+1 plus 2*j and 2*i+1 gets connected in new graph with capacity 1. 

3.source vertex (S) is connected to each 2*i vertex(head set) with capacity min(T, degree). 
4. Each 2*i+1(feet set) vertex is connected to target vertex (T) with capacity 1 
5. Maxflow is the answer. 

नीचे दी गई छवि कैसे ग्राफ रूपों में से एक सभ्य विचार दे सकते हैं। New Graph formation

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

बिंदु 4 का स्पष्टीकरण: - यह सुनिश्चित करने के लिए कि जोड़े अलग हैं ताकि प्रत्येक चरम केवल एक केकड़ा में आ जाए, प्रत्येक चरण क्षमता 1 में लक्ष्य 10 से जुड़ा हुआ है।

यदि आवश्यक हो तो मैं कोड पोस्ट कर सकता हूं।