ग्राफ़ में अधिकतम वजन का चक्र

Question

भारित ग्राफ (निर्देशित या अप्रत्यक्ष) को देखते हुए मुझे अधिकतम वजन के साथ ग्राफ के चक्र को खोजने की आवश्यकता है।

ग्राफ़ के किनारों के वजन का योग होने के चक्र का वजन।

यह किसी भी चक्र, न सिर्फ आधार चक्र जिसके लिए हम

• सभी आधार चक्र प्राप्त कर सकते हैं हो सकता है (देखें Algorithms to Identify All the Cycle Bases in a UnDirected Graph)
• प्रत्येक आधार चक्र का वजन की गणना करते हैं और पाते अधिकतम

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

क्या आपके पास सभी चक्रों को बगैर अधिकतम वजन चक्र खोजने का कोई विचार है?

यदि आपको ग्राफ पर परिकल्पना की आवश्यकता है (उदाहरण के लिए सकारात्मक वजन) कृपया उन्हें इंगित करें।

Answer 1

यह एनपी-हार्ड है।

हैमिल्टनियन चक्र समस्या को कम किया जा सकता है।

एक ग्राफ को देखते हुए जिसके लिए हमें यह जांचने की आवश्यकता है कि हैमिल्टनियन चक्र मौजूद है या नहीं, प्रत्येक किनारे पर वजन 1 असाइन करें।

अब अधिकतम वजन चक्र प्राप्त करने के लिए अपना एल्गोरिदम चलाएं। यदि वजन < एन है, तो मूल ग्राफ में हैमिल्टनियन चक्र नहीं है, अन्यथा यह करता है।

Answer 2

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