प्रेरित पथ

हाइपरक्यूब ग्राफ में लंबाई चार का प्रेरित पथ। हाइपरक्यूब में सबसे लंबे समय तक प्रेरित पथ ढूँढना सांप-इन-द-बॉक्स समस्या के रूप में जाना जाता है।

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

इसी तरह, एक प्रेरित चक्र एक चक्र ग्राफ है जो एक प्रेरित सबग्राफ है G; प्रेरित चक्रों को तार रहित चक्र या (जब चक्र की लंबाई चार या अधिक हो) छिद्र भी कहा जाता है। एक प्रतिछिद्र के पूरक (ग्राफ सिद्धांत) में एक छेद है G, अर्थात, एक प्रतिछिद्र एक छिद्र का पूरक है।

किसी ग्राफ़ में सबसे लंबे प्रेरित पथ की लंबाई को कभी-कभी ग्राफ़ की चक्कर संख्या कहा जाता है; विरल रेखांकन के लिए, परिबद्ध चक्कर संख्या का होना परिबद्ध वृक्ष-गहराई के बराबर है। एक ग्राफ की प्रेरित पथ संख्या G प्रेरित पथों की सबसे छोटी संख्या है जिसमें ग्राफ़ के शीर्षों को विभाजित किया जा सकता है, और निकटता से संबंधित पथ की संख्या को कवर करता है G प्रेरित पथों की सबसे छोटी संख्या है जिसमें एक साथ सभी शीर्ष शामिल हैं G. एक ग्राफ का घेरा (ग्राफ सिद्धांत) उसके सबसे छोटे चक्र की लंबाई है, लेकिन यह चक्र एक प्रेरित चक्र होना चाहिए क्योंकि किसी भी जीवा का उपयोग एक छोटे चक्र का उत्पादन करने के लिए किया जा सकता है; इसी तरह के कारणों के लिए एक ग्राफ का विषम घेरा भी उसके सबसे छोटे विषम प्रेरित चक्र की लंबाई है।

उदाहरण

Maximum lengths of snakes (L_s) and coils (L_c) in the snakes-in-the-box problem for dimensions n from 1 to 4

चित्रण इस ग्राफ में एक घन, आठ कोने और बारह किनारों वाला एक ग्राफ, और लंबाई चार का एक प्रेरित पथ दिखाता है। एक सीधे मामले के विश्लेषण से पता चलता है कि घन में अब प्रेरित पथ नहीं हो सकता है, हालांकि इसकी लंबाई छह का एक प्रेरित चक्र है। हाइपरक्यूब में सबसे लंबे समय तक प्रेरित पथ या चक्र खोजने की समस्या, सबसे पहले किसके द्वारा प्रस्तुत की गई थी Kautz (1958), को स्नेक-इन-द-बॉक्स समस्या के रूप में जाना जाता है, और कोडिंग सिद्धांत और इंजीनियरिंग में इसके अनुप्रयोगों के कारण इसका व्यापक अध्ययन किया गया है।

कोग्राफ परिवारों की विशेषता

कई महत्वपूर्ण ग्राफ़ परिवारों को परिवार में ग्राफ़ के प्रेरित पथों या चक्रों के संदर्भ में चित्रित किया जा सकता है।

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

एल्गोरिदम और जटिलता

ग्राफ़ G और पैरामीटर k के लिए यह निर्धारित करने के लिए NP-पूर्ण है कि क्या ग्राफ़ में कम से कम k लंबाई का एक प्रेरित पथ है। Garey & Johnson (1979) इस परिणाम का श्रेय माइकलिस यानाकाकिस के अप्रकाशित संचार को दें। हालाँकि, इस समस्या को बहुपद समय में कुछ ग्राफ़ परिवारों के लिए हल किया जा सकता है, जैसे कि क्षुद्रग्रह-ट्रिपल-मुक्त ग्राफ़ या बिना लंबे छेद वाले ग्राफ़। यह निर्धारित करने के लिए भी एनपी-पूर्ण है कि ग्राफ के कोने को दो प्रेरित पथों या दो प्रेरित चक्रों में विभाजित किया जा सकता है या नहीं। नतीजतन, ग्राफ के प्रेरित पथ संख्या का निर्धारण एनपी-हार्ड है।

सबसे लंबे समय तक प्रेरित पथ या चक्र की समस्याओं का अनुमान लगाने की जटिलता निम्न कमी से ग्राफ में बड़े स्वतंत्र सेट (ग्राफ सिद्धांत) को खोजने से संबंधित हो सकती है। n शीर्षों वाले किसी भी ग्राफ़ G से, G n(n − 1)/2 शीर्षों में जोड़कर, G में दो शीर्षों के साथ एक अन्य ग्राफ़ H बनाएँ, जिसमें दो पड़ोसी हों, G में प्रत्येक शीर्ष जोड़ी के लिए एक। फिर यदि G आकार k का एक स्वतंत्र सेट है, H के पास एक प्रेरित पथ और लंबाई 2k का एक प्रेरित चक्र होना चाहिए, जो I के कोने के साथ G में स्वतंत्र सेट के वैकल्पिक वर्टिकल द्वारा बनता है। इसके विपरीत, यदि H का एक प्रेरित पथ या लंबाई k का चक्र है , इस पथ या चक्र से G में असन्निकट शीर्षों का कोई भी अधिकतम सेट कम से कम k/3 आकार के G में एक स्वतंत्र सेट बनाता है। इस प्रकार, जी में अधिकतम स्वतंत्र सेट का आकार सबसे लंबे प्रेरित पथ के आकार और एच में सबसे लंबे समय तक प्रेरित चक्र के एक स्थिर कारक के भीतर है। इसलिए, के परिणाम से Håstad (1996) स्वतंत्र सेटों की अनुपयुक्तता पर, जब तक कि एनपी = जेडपीपी, ओ (एन) के कारक के भीतर सबसे लंबे समय तक प्रेरित पथ या सबसे लंबे समय तक प्रेरित चक्र का अनुमान लगाने के लिए बहुपद समय एल्गोरिदम मौजूद नहीं है।^{इष्टतम समाधान का 1/2-ε})।

एन कोने और एम किनारों वाले ग्राफ में छेद (और लंबाई 5 के तारहीन चक्र के बिना ग्राफ में एंटीहोल्स) समय में पता लगाया जा सकता है (एन + एम)²).

परमाणु चक्र

परमाणु चक्र ताररहित चक्रों का एक सामान्यीकरण है, जिसमें कोई एन-कॉर्ड नहीं होता है। किसी चक्र को देखते हुए, एन-कॉर्ड को चक्र पर दो बिंदुओं को जोड़ने वाली लंबाई एन के पथ के रूप में परिभाषित किया जाता है, जहां एन उन बिंदुओं को जोड़ने वाले चक्र पर सबसे कम पथ की लंबाई से कम है। यदि किसी चक्र में कोई n-रज्जु नहीं है, तो इसे परमाणु चक्र कहा जाता है, क्योंकि इसे छोटे चक्रों में विघटित नहीं किया जा सकता है। सबसे खराब स्थिति में, एक ग्राफ में परमाणु चक्रों की गणना O(m.) में की जा सकती है²) समय, जहां m ग्राफ़ में किनारों की संख्या है।

संदर्भ

• Barioli, Francesco; Fallat, Shaun; Hogben, Leslie (2004). "Computation of minimal rank and path cover number for certain graphs" (PDF). Linear Algebra and Its Applications. 392: 289–303. doi:10.1016/j.laa.2004.06.019.
• Berman, Piotr; Schnitger, Georg (1992). "On the complexity of approximating the independent set problem". Information and Computation. 96 (1): 77–94. doi:10.1016/0890-5401(92)90056-L.
• Buckley, Fred; Harary, Frank (1988). "On longest induced paths in graphs". Chinese Quarterly Journal of Mathematics. 3 (3): 61–65.
• Chartrand, Gary; McCanna, Joseph; Sherwani, Naveed; Hossain, Moazzem; Hashmi, Jahangir (1994). "The induced path number of bipartite graphs". Ars Combinatoria. 37: 191–208.
• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. p. 196.
• Gashler, Michael; Martinez, Tony (2012). "Robust manifold learning with CycleCut" (PDF). Connection Science. 24 (1): 57–69. doi:10.1080/09540091.2012.664122.
• Gavril, Fănică (2002). "Algorithms for maximum weight induced paths". Information Processing Letters. 81 (4): 203–208. doi:10.1016/S0020-0190(01)00222-8.
• Håstad, Johan (1996). "Clique is hard to approximate within n^1−ε". Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. pp. 627–636. doi:10.1109/SFCS.1996.548522.
• Kautz, William H. (June 1958). "Unit-distance error-checking codes". IRE Transactions on Electronic Computers. EC-7 (2): 179–180. doi:10.1109/TEC.1958.5222529. S2CID 26649532.
• Kratsch, Dieter; Müller, Haiko; Todinca, Ioan (2003). "Feedback vertex set and longest induced path on AT-free graphs". Graph-theoretic concepts in computer science. Berlin: Lecture Notes in Computer Science, Vol. 2880, Springer-Verlag. pp. 309–321. doi:10.1007/b93953. Archived from the original on 2006-11-25.
• Le, Hoàng-Oanh; Le, Van Bang; Müller, Haiko (2003). "Splitting a graph into disjoint induced paths or cycles" (PDF). Discrete Applied Mathematics. The Second International Colloquium "Journées de l'Informatique Messine", Metz, 2000. 131 (1): 199–212. doi:10.1016/S0166-218X(02)00425-0. Archived from the original (PDF) on 2016-03-03.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012). "Chapter 6. Bounded height trees and tree-depth". Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics. Vol. 28. Heidelberg: Springer. pp. 115–144. doi:10.1007/978-3-642-27875-4. ISBN 978-3-642-27874-7. MR 2920058.
• Nikolopoulos, Stavros D.; Palios, Leonidas (2004). "Hole and antihole detection in graphs". Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. pp. 850–859.