Trémaux tree
ग्राफ सिद्धांत में, एक दिशाहीन ग्राफ का एक ट्रेमॉक्स वृक्ष एक प्रकार का फैला हुआ वृक्ष है, जो गहराई-प्रथम खोज वृक्षों को सामान्यीकृत करता है। उन्हें इस गुण से परिभाषित किया जाता है कि पेड़ का प्रत्येक किनारा पेड़ में एक पूर्वज-वंशज जोड़ी को जोड़ता है। ट्रेमॉक्स पेड़ों का नाम 19वीं शताब्दी के फ्रांसीसी लेखक चार्ल्स पियरे ट्रेमॉक्स के नाम पर रखा गया है, जिन्होंने भूलभुलैया को हल करने की रणनीति के रूप में गहराई-पहली खोज के एक रूप का उपयोग किया था। विशेष रूप से अनंत ग्राफ के संदर्भ में उन्हें सामान्य फैले हुए पेड़ भी कहा गया है। सभी गहराई-पहले खोज पेड़ और सभी हैमिल्टनियन पथ ट्रेमॉक्स पेड़ हैं। परिमित ग्राफ में, प्रत्येक ट्रेमॉक्स ट्री एक गहराई-प्रथम खोज ट्री है, लेकिन हालांकि गहराई-प्रथम खोज स्वयं स्वाभाविक रूप से अनुक्रमिक है, ट्रेमॉक्स ट्री का निर्माण जटिलता वर्ग आरएनसी में एक यादृच्छिक समानांतर एल्गोरिथ्म द्वारा किया जा सकता है। इनका उपयोग ग्राफ की वृक्ष-गहराई को परिभाषित करने के लिए किया जा सकता है, और यह परीक्षण करने के लिए कि क्या ग्राफ एक समतलीय ग्राफ है, बाएं-दाएं समतलीयता परीक्षण के हिस्से के रूप में किया जा सकता है। ग्राफ के monadic दूसरे क्रम के तर्क में ट्रेमॉक्स पेड़ों का एक लक्षण वर्णन कोरसेल के प्रमेय का उपयोग करके बंधे हुए त्रि-चौड़ाई के ग्राफ के लिए अभिविन्यास से जुड़े ग्राफ गुणों को कुशलता से पहचानने की अनुमति देता है। हर अनंत जुड़े ग्राफ में एक ट्रेमॉक्स वृक्ष नहीं होता है, और हर अनंत ट्रेमॉक्स वृक्ष एक गहराई-प्रथम खोज वृक्ष नहीं होता है। जिन ग्राफों में ट्रेमॉक्स के पेड़ हैं, उन्हें निषिद्ध नाबालिगों द्वारा चिह्नित किया जा सकता है। एक अनंत ट्रेमॉक्स ट्री में ग्राफ के प्रत्येक छोर के लिए बिल्कुल एक अनंत मार्ग होना चाहिए, और एक ट्रेमॉक्स ट्री का अस्तित्व उन ग्राफों की विशेषता है जिनकी टोपोलॉजिकल पूर्णता, प्रत्येक छोर के लिए अनंत पर एक बिंदु जोड़कर बनाई गई है, जो मीट्रिक रिक्त स्थान हैं। परिभाषा और उदाहरण एक ट्रेमॉक्स ट्री, एक ग्राफ के लिए, एक फैला हुआ पेड़ है, जिसमें प्रत्येक किनारे के लिए, दो अंतिम बिंदुओं में से एक है और दूसरे का पूर्वज है। एक फैला हुआ वृक्ष होने के लिए, इसे केवल के किनारों का उपयोग करना चाहिए, और प्रत्येक शीर्ष को शामिल करना चाहिए, जिसमें शीर्षों की प्रत्येक जोड़ी के बीच एक अद्वितीय सीमित पथ हो। इसके अतिरिक्त, इस वृक्ष में पूर्वज-वंशज संबंध को परिभाषित करने के लिए, इसके शीर्षों में से एक को इसके मूल के रूप में नामित किया जाना चाहिए। यदि एक परिमित ग्राफ में एक हैमिल्टनियन पथ है, तो उस मार्ग को उसके दो अंतिम बिंदुओं में से एक पर जड़ देने से एक ट्रेमॉक्स वृक्ष उत्पन्न होता है। इस तरह के मार्ग के लिए, शीर्षों की प्रत्येक जोड़ी एक पूर्वज-वंशज जोड़ी है। नीचे दिखाए गए ग्राफ में, 1-3,2-3 और 3-4 किनारों वाला पेड़ एक ट्रेमॉक्स पेड़ है जब यह शीर्ष 1 या शीर्ष 2 पर जड़ें रखता हैः ग्राफ का हर किनारा पेड़ से संबंधित है, सिवाय किनारे 1-2 के, जो (जड़ के इन विकल्पों के लिए) एक पूर्वज-वंशज जोड़ी को जोड़ता है। हालांकि, उसी पेड़ को शीर्ष 3 या शीर्ष 4 पर जड़ देने से एक जड़ वाला पेड़ पैदा होता है जो ट्रेमॉक्स पेड़ नहीं है, क्योंकि इस जड़ के साथ 1 और 2 अब एक दूसरे के पूर्वज और वंशज नहीं हैं। परिमित ग्राफ में अस्तित्व प्रत्येक परिमित जुड़े अनिर्दिष्ट ग्राफ में कम से कम एक ट्रेमॉक्स ट्री होता है। इस तरह के पेड़ का निर्माण गहराई से पहले खोज करके और प्रत्येक शीर्ष (खोज के शुरुआती शीर्ष के अलावा) को पहले के शीर्ष से जोड़कर किया जा सकता है जहां से इसकी खोज की गई थी। इस तरह से बनाए गए पेड़ को गहराई-पहले खोज पेड़ के रूप में जाना जाता है। यदि ग्राफ में एक मनमाना किनारा है, और खोज द्वारा पहुँचा जाने वाले दो शीर्षों में से पहला है, तो गहराई-प्रथम खोज वृक्ष से उतरने वाले उप-वृक्ष से संबंधित होना चाहिए, क्योंकि खोज आवश्यक रूप से इस उप-वृक्ष की खोज करते समय पता लगाएगी, या तो उप-वृक्ष के अन्य शीर्षों में से एक से या, ऐसा न करने पर, सीधे। प्रत्येक परिमित ट्रेमॉक्स वृक्ष को एक गहराई-प्रथम खोज वृक्ष के रूप में उत्पन्न किया जा सकता हैः यदि एक सीमित ग्राफ का एक ट्रेमॉक्स वृक्ष है, और किसी अन्य शीर्ष की खोज करने से पहले प्रत्येक शीर्ष के बच्चों की गहराई-प्रथम खोज की जाती है, तो यह आवश्यक रूप से अपने गहराई-प्रथम खोज वृक्ष के रूप में उत्पन्न होगा। समानान्तर निर्माण ट्रेमॉक्स वृक्ष को खोजना पी-पूर्ण है जो एक अनुक्रमिक गहराई-प्रथम खोज एल्गोरिथ्म द्वारा पाया जाएगा, जिसमें प्रत्येक शीर्ष के पड़ोसियों को उनकी पहचान के क्रम में खोजा जाता है। फिर भी, एक यादृच्छिक समानांतर एल्गोरिथ्म द्वारा एक अलग ट्रेमॉक्स ट्री का पता लगाना संभव है, जिससे पता चलता है कि ट्रेमॉक्स पेड़ों का निर्माण जटिलता वर्ग आरएनसी से संबंधित है। एल्गोरिथ्म एक अन्य यादृच्छिक समानांतर एल्गोरिथ्म पर आधारित है, जो 0-1-भारित ग्राफ में न्यूनतम-वजन पूर्ण मिलान खोजने के लिए है। 1997 तक, यह अज्ञात रहा कि क्या ट्रेमॉक्स वृक्ष का निर्माण जटिलता वर्ग एन. सी. में एक नियतात्मक समानांतर एल्गोरिथ्म द्वारा किया जा सकता है। यदि मिलान एन. सी. में पाए जा सकते हैं, तो ट्रेमॉक्स के पेड़ भी मिल सकते हैं। तार्किक अभिव्यक्ति इस गुण को व्यक्त करना संभव है कि मूल शीर्ष के विकल्प के साथ किनारों का एक समूह एक ट्रेमॉक्स ट्री बनाता है, ग्राफ के monadic द्वितीय-क्रम तर्क में, और विशेष रूप से इस तर्क के रूप में जिसे MSO2 कहा जाता है, जो शीर्ष और किनारे दोनों सेटों पर परिमाणीकरण की अनुमति देता है। इस गुण को निम्नलिखित गुणों के संयोजन के रूप में व्यक्त किया जा सकता हैः ग्राफ किनारों से जुड़ा हुआ है। इसे तार्किक रूप से इस कथन के रूप में व्यक्त किया जा सकता है कि, ग्राफ के शीर्षों के प्रत्येक गैर-खाली उचित उपसमुच्चय के लिए, दिए गए उपसमुच्चय में बिल्कुल एक अंतिम बिंदु के साथ एक किनारा मौजूद है। चक्रीय होता है। इसे तार्किक रूप से इस कथन के रूप में व्यक्त किया जा सकता है कि एक गैर-खाली उपसमुच्चय मौजूद नहीं है जिसके लिए प्रत्येक शीर्ष शून्य या दो किनारों पर होता है। प्रत्येक किनारा जो पूर्वजों-वंशजों के शीर्षों की जोड़ी को जोड़ता है। यह तब सच होता है जब दोनों अंतिम बिंदु एक पथ से संबंधित होते हैं। इसे तार्किक रूप से इस कथन के रूप में व्यक्त किया जा सकता है कि, सभी किनारों के लिए, इस तरह का एक उपसमुच्चय मौजूद है कि ठीक दो शीर्ष, उनमें से एक, के एक किनारे पर आपतित हैं, और इस तरह कि दोनों के अंतिम बिंदु कम से कम एक किनारे पर आपतित हैं। एक बार जब एक ट्रेमॉक्स पेड़ को इस तरह से पहचाना जाता है, तो कोई भी दिए गए ग्राफ के अभिविन्यास का वर्णन कर सकता है, जो मोनडिक द्वितीय-क्रम तर्क में भी है, किनारों के समूह को निर्दिष्ट करके जिसका अभिविन्यास पैतृक अंतिम बिंदु से वंशज अंतिम बिंदु तक है। इस समूह के बाहर शेष किनारों को दूसरी दिशा में उन्मुख होना चाहिए। यह तकनीक आरेखण से जुड़े ग्राफ गुणों को मोनडिक द्वितीय क्रम तर्क में निर्दिष्ट करने की अनुमति देती है, जिससे इन गुणों को कोरसेल के प्रमेय का उपयोग करके बंधे हुए त्रि-चौड़ाई के ग्राफ पर कुशलता से परीक्षण किया जा सकता है। संबंधित गुण यदि किसी ग्राफ में हैमिल्टनियन पथ है, तो वह मार्ग (उसके अंतिम बिंदुओं में से एक पर निहित) भी एक ट्रेमॉक्स वृक्ष है। जिन अनिर्दिष्ट ग्राफों के लिए प्रत्येक ट्रेमॉक्स पेड़ का यह रूप होता है, वे हैं चक्र ग्राफ, पूर्ण ग्राफ और संतुलित पूर्ण द्विदलीय ग्राफ। ट्रेमॉक्स पेड़ पेड़ की गहराई की अवधारणा से निकटता से संबंधित हैं। ग्राफ की ट्री-डेप्थ को सबसे छोटी संख्या के रूप में परिभाषित किया जा सकता है जिसके लिए एक ग्राफ मौजूद है, जिसमें गहराई का ट्रेमॉक्स ट्री है, जैसे कि एक सबग्राफ है। ग्राफ के एक परिवार में वृक्ष-गहराई की सीमा, एक ऐसे मार्ग के अस्तित्व के बराबर है जो परिवार में ग्राफ के लघु ग्राफ के रूप में नहीं हो सकता है। ग्राफ पर कई कठिन कम्प्यूटेशनल समस्याओं में एल्गोरिदम होते हैं जो निश्चित-पैरामीटर ट्रैक्टेबल होते हैं जब उनके इनपुट की ट्री-डेप्थ द्वारा पैरामीटर किए जाते हैं। दिए गए ग्राफ समतल है या नहीं, इसका परीक्षण करने के लिए ट्रेमॉक्स पेड़ फ्रेसेक्स-रोसेनस्टीहल समतलीयता मानदंड में भी महत्वपूर्ण भूमिका निभाते हैं। इस मानदंड के अनुसार, एक ग्राफ समतल है, यदि किसी दिए गए ट्रेमॉक्स पेड़ के लिए, शेष किनारों को पेड़ के बाएं या दाएं हिस्से में एक सुसंगत तरीके से रखा जा सकता है, जो बाधाओं के अधीन है जो एक ही स्थान वाले किनारों को एक दूसरे को पार करने से रोकते हैं। अनंत ग्राफ में अस्तित्व प्रत्येक अनंत ग्राफ में एक सामान्य फैलाव वृक्ष नहीं होता है। उदाहरण के लिए, शीर्षों के एक अनगिनत समूह पर एक पूर्ण ग्राफ में एक नहीं होता हैः एक पूर्ण ग्राफ में एक सामान्य फैला हुआ वृक्ष केवल एक पथ हो सकता है, लेकिन एक पथ में केवल शीर्षों की एक गणना योग्य संख्या होती है। हालांकि, शीर्षों के एक गणना योग्य समूह पर प्रत्येक ग्राफ में एक सामान्य फैलाव वृक्ष होता है। गणना योग्य ग्राफों में भी, एक गहराई-प्रथम खोज अंततः पूरे ग्राफ की खोज करने में सफल नहीं हो सकती है, और हर सामान्य फैले हुए पेड़ को गहराई-प्रथम खोज से उत्पन्न नहीं किया जा सकता हैः एक गहराई-प्रथम खोज पेड़ होने के लिए, एक गणना योग्य सामान्य फैले हुए पेड़ में केवल एक अनंत पथ या एक नोड होना चाहिए जिसमें असीम रूप से कई बच्चे हों (और दोनों नहीं)। यदि एक अनंत ग्राफ में एक सामान्य फैलाव वृक्ष होता है, तो हर जुड़ा हुआ ग्राफ भी छोटा होता है। इससे पता चलता है कि जिन ग्राफों में सामान्य फैले हुए पेड़ हैं, उनमें निषिद्ध नाबालिगों द्वारा एक लक्षण वर्णन किया गया है। वर्जित नाबालिगों के दो वर्गों में से एक में द्विदलीय ग्राफ होते हैं जिसमें द्विदलीय विभाजन का एक पक्ष गणना योग्य होता है, दूसरा पक्ष गणना योग्य नहीं होता है, और प्रत्येक शीर्ष में अनंत डिग्री होती है। वर्जित नाबालिगों के दूसरे वर्ग में अरोन्ज़ाज़न पेड़ों से प्राप्त कुछ ग्राफ होते हैं। इस लक्षण वर्णन का विवरण गणित को औपचारिक बनाने के लिए उपयोग किए जाने वाले सेट-सैद्धांतिक स्वयंसिद्धीकरण के विकल्प पर निर्भर करता है। विशेष रूप से, सेट सिद्धांत के मॉडलों में जिनके लिए मार्टिन का स्वयंसिद्ध सत्य है और निरंतरता परिकल्पना गलत है, इस लक्षण वर्णन में द्विदलीय ग्राफ के वर्ग को एकल निषिद्ध लघु द्वारा प्रतिस्थापित किया जा सकता है। हालांकि, उन मॉडलों के लिए जिनमें निरंतरता परिकल्पना सच है, इस वर्ग में ऐसे ग्राफ हैं जो मामूली क्रम में एक दूसरे के साथ अतुलनीय हैं। अंत और मापनीयता सामान्य फैले हुए पेड़ भी एक अनंत ग्राफ के सिरों से निकटता से संबंधित हैं, जो अनंत पथों के समतुल्य वर्ग हैं, जो सहज रूप से, एक ही दिशा में अनंत तक जाते हैं। यदि किसी ग्राफ में एक सामान्य फैला हुआ वृक्ष है, तो इस वृक्ष में ग्राफ के प्रत्येक छोर के लिए बिल्कुल एक अनंत मार्ग होना चाहिए। एक अनंत ग्राफ का उपयोग ग्राफ को एक सरल परिसर के रूप में देखकर और ग्राफ के प्रत्येक छोर के लिए अनंत पर एक बिंदु जोड़कर एक स्थलवैज्ञानिक स्थान बनाने के लिए किया जा सकता है। इस टोपोलॉजी के साथ, एक ग्राफ में एक सामान्य फैलाव वृक्ष होता है यदि और केवल तभी जब इसके शीर्षों के सेट को बंद सेटों के गणना योग्य संघ में विघटित किया जा सके। इसके अतिरिक्त, इस स्थलवैज्ञानिक स्थान को एक मीट्रिक स्थान द्वारा तभी दर्शाया जा सकता है जब ग्राफ में एक सामान्य फैला हुआ वृक्ष हो। संदर्भ ग्राफ सिद्धांत वस्तुएं वृक्ष का विस्तार ग्राफ लघु सिद्धांत अनंत ग्राफ