प्रेरित पथ

File:Snake in the box.svg

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

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

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

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

उदाहरण

File:Snakes and coils in the box.svg

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

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

कोग्राफ समूह की विशेषता

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

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

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

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

यह निर्धारित करने के लिए भी np-पूर्ण है कि ग्राफ के कोने को दो प्रेरित पथों या दो प्रेरित चक्रों में विभाजित किया जा सकता है या नहीं इस बात का मुख्य रूप से ध्यान रखा जाता हैं। परिणामस्वरूप, ग्राफ के प्रेरित पथ संख्या का निर्धारण np-कठोर होते हैं।

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

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

परमाणु चक्र

परमाणु चक्र बिना तार से संयोजित चक्रों का सामान्यीकरण रूप होता है, जिसमें कोई n-कॉर्ड नहीं होता है। किसी चक्र को देखते हुए n-कॉर्ड को चक्र पर दो बिंदुओं को जोड़ने वाली लंबाई n के पथ के रूप में परिभाषित किया जाता है, जहां n उन बिंदुओं को जोड़ने वाले चक्र पर सबसे कम पथ की लंबाई से कम है। यदि किसी चक्र में कोई 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.