के एक निर्देशित ग्राफ को दो तरफा न्यूनतम स्पैनिंग पेड़, भारित किनारों के साथ एक निर्देशित ग्राफ को देखते हुए, न्यूनतम वजन वाले उप-ग्राफ को देने के लिए किस एल्गोरिदम का उपयोग किया जा सकता है, लेकिन ग्राफ़ में किसी भी कशेरुक से किसी भी चरम पर आंदोलन की अनुमति देता है (धारणा के तहत कि किसी भी दो शीर्षकों के बीच पथ हमेशा मौजूद हैं)।एक निर्देशित ग्राफ
क्या ऐसा कोई एल्गोरिदम मौजूद है?
यह एनपी-हार्ड होना प्रतीत होता है: न्यूनतम वजन दृढ़ता से उप-समस्या समस्या फैलता है।
मेरा मानना है कि हैमिल्टनियन चक्र की समस्या को कम किया जा सकता है: ग्राफ़ जी (वी, ई) को देखते हुए, किनारों के लिए वजन 1 के साथ एक डिग्राफ डीजी का निर्माण करें और किनारों के लिए वजन 100 (| वी | +1) 'टी। डीजी का वजन कम से कम वजन के उप-अनुच्छेद को दृढ़ता से जुड़ा हुआ है। वी | अगर और केवल अगर जी में हैमिल्टनियन चक्र है। http://portal.acm.org/citation.cfm?id=844363
हालांकि वे खुद को सही नहीं थे, समय विटाली के विकिपीडिया लिंक का पालन करने के लिए जल्दी से इस एल्गोरिथ्म का पर्दाफाश लेने:
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
स्प्लिट दो नोड्स में ग्राफ में प्रत्येक नोड। एक नोड सभी आने वाले किनारों को मूल नोड में स्वीकार करेगा, और दूसरे के पास सभी आउटगोइंग किनार होंगे। फिर, सभी किनारों पर दिशा छोड़ दें, इसलिए ग्राफ अप्रत्यक्ष है। फिर आप ग्राफ़ (प्राइम, क्रस्कल) पर एक मानक एमएसटी एल्गोरिदम चला सकते हैं और आप सुनिश्चित करेंगे कि प्रत्येक मूल नोड को हर दूसरे मूल नोड द्वारा यात्रा की जा सके।
दुर्भाग्य से यह काम नहीं करेगा, क्योंकि यह अंतिम ग्राफ में अनावश्यक किनारों को जोड़ देगा। कम से कम एक नोड के साथ एक अतिरिक्त धार संलग्न होगा, भले ही उसे उस किनारे की आवश्यकता न हो। उदाहरण के लिए, ए, बी, सी और किनारों के साथ ग्राफ में एबी, बीए, बीसी, सीबी, एसी, सीए, ग्राफ की न्यूनतम अवधि केवल एबी, बीसी, सीए के किनारों पर हो सकती है। लेकिन आपकी विधि का उपयोग करके उन 3 किनारों को एक दूसरे से जोड़ा नहीं जाएगा, और अतिरिक्त किनारों को एमएसटी खत्म करने के लिए जोड़ा जाना होगा। –
किसी भी नोड उठाओ और इसे वापस:
कागज यहाँ एक सन्निकटन एल्गोरिथ्म है।
क्या आप शायद मतलब सबसे बड़ा दृढ़ता से जुड़े subgraph (कम से कम नोड्स की संख्या संभव हटाया) मिल जाए, या न्यूनतम वजन subgraph फैले (कोई नोड द्वारा निकाली अनुमति)?
शीर्षक 'स्पैनिंग पेड़' कहता है, इसलिए मैं बाद वाले को मानता हूं। –
@ मॉरॉन: आह, मुझे वह याद आया :) इस मामले में, आपका जवाब सही है। –
यह निर्देशित स्टीनर ट्री समस्या है। स्टीनर ट्री के रूप में, यह एनपी-हार्ड है।
आप कुछ aproximate एल्गोरिदम यहाँ पा सकते हैं:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps
लेकिन एक निर्देशित स्टीनर ट्री की जड़ की आवश्यकता है, है ना? – highBandWidth
इष्टतम रूट वर्टेक्स एल्गोरिदम द्वारा पाया जा सकता है लेकिन आप वर्टेक्स के सेट के साथ रूट निर्दिष्ट कर सकते हैं। – jwinandy
एडमंड एल्गोरिथ्म केवल भरोसा दिलाते हैं कि एक ग्राफ में प्रत्येक नोड जड़ से पहुंचा जा सकेगा, न कि प्रत्येक नोड हर दूसरे नोड से पहुंचा जा सकेगा। –
यह एनपी-हार्ड है। -1। –
मेरे लिंक के एनपी वर्गीकरण को मूल प्रश्न के प्रासंगिकता के साथ क्या करना है? – Mathew