Euler tour technique
यूलर टूर तकनीक (ई. टी. टी.), जिसका नाम लियोनहार्ड यूलर के नाम पर रखा गया है, पेड़ों का प्रतिनिधित्व करने के लिए ग्राफ सिद्धांत में एक विधि है। पेड़ को एक निर्देशित ग्राफ के रूप में देखा जाता है जिसमें पेड़ के प्रत्येक किनारे के लिए दो निर्देशित किनारे होते हैं। तब वृक्ष को निर्देशित ग्राफ के यूलरियन परिपथ के रूप में दर्शाया जा सकता है, जिसे वृक्ष के यूलर टूर प्रतिनिधित्व (ई. टी. आर.) के रूप में जाना जाता है। ई. टी. टी. एल्गोरिदमिक ग्राफ सिद्धांत में सामान्य समस्याओं के समाधान की कुशल, समानांतर गणना की अनुमति देता है। इसे 1984 में टार्जन और विशकिन द्वारा पेश किया गया था। किनारों के एक समूह के रूप में प्रस्तुत एक दिशाहीन पेड़ को देखते हुए, यूलर टूर प्रतिनिधित्व (ई. टी. आर.) का निर्माण समानांतर रूप से किया जा सकता हैः हम निर्देशित किनारों की एक सममित सूची का निर्माण करते हैंः पेड़ में प्रत्येक दिशाहीन किनारे {यू, वी} के लिए, किनारे की सूची में (यू, वी) और (वी, यू) डालें। किनारों की सूची को शब्दकोशात्मक रूप से क्रमबद्ध करें। (यहाँ हम मानते हैं कि पेड़ के नोड क्रमबद्ध हैं, और मूल इस क्रम में पहला तत्व है।) प्रत्येक नोड (जिसे अगला कहा जाता है) के लिए निकटता सूचियों का निर्माण करें और निकटता सूचियों की पहली प्रविष्टियों के लिए नोड्स से एक मानचित्र बनाएँ (जिसे पहले कहा जाता है): सूची में प्रत्येक किनारे (यू, वी) के लिए, समानांतर में करें यदि पिछले किनारे (एक्स, वाई) में एक्स  ऒत्त यू है, अर्थात। एक अलग नोड से शुरू होता है, पहले सेट करें (u) = (u, v) अन्यथा यदि x = u, अर्थात। उसी नोड से शुरू होता है, अगला सेट करें (x, y) = (u, v) निम्नलिखित नियम के अनुसार समानांतर में सभी किनारों (u, v) के लिए संकेत सक् (u, v) सेट करके यूलर टूर क्रम में एक किनारे की सूची (जिसे सक् कहा जाता है) का निर्माण करेंः परिणामी सूची सक् गोलाकार होगी। समग्र निर्माण में काम W (n) = O (क्रमबद्ध (n)) (n वस्तुओं को समानांतर में क्रमबद्ध करने में लगने वाला समय) लगता है यदि पेड़ में n नोड्स हैं, क्योंकि पेड़ों में किनारों की संख्या नोड्स की संख्या से एक कम है। जड़ें, अग्रिम और पीछे हटने वाले किनारे यदि पेड़ की जड़ है, तो हम उस जड़ पर वृत्ताकार सूची को विभाजित कर सकते हैं। उस स्थिति में, हम अग्रिम और पीछे हटने वाले किनारों की बात कर सकते हैंः यू, वी नोड्स की एक जोड़ी को देखते हुए, ई. टी. आर. में (यू, वी) या (वी, यू) की पहली घटना को अग्रिम किनारा कहा जाता है, और दूसरी घटना को पीछे हटने वाला किनारा कहा जाता है। यह इस अंतर्ज्ञान को आकर्षित करता है कि पहली बार इस तरह के किनारे को पार करने पर जड़ तक की दूरी बढ़ जाती है, जबकि दूसरी बार दूरी कम हो जाती है। नई जड़ पर वृत्ताकार सूची को विभाजित करके पेड़ को फिर से व्यवस्थित किया जा सकता है O (1)। अनुप्रयोग निम्नलिखित सभी समस्याओं को ओ (उपसर्ग राशि (एन)) में हल किया जा सकता है (n वस्तुओं की सूची के लिए उपसर्ग राशि समस्या को समानांतर में हल करने में लगने वाला समय): अग्रिम और पीछे हटने वाले किनारों को वर्गीकृत करनाः ई. टी. आर. पर सूची रैंकिंग करें और परिणाम को द्वि-आयामी सरणी ए में सहेजें। फिर (यू, वी) ए (यू, वी) <ए (वी, यू) का एक अग्रिम किनारा है, और अन्यथा एक पीछे हटने वाला किनारा है। प्रत्येक नोड के स्तर का निर्धारण करेंः ई. टी. आर. पर एक उपसर्ग योग करें, जहाँ प्रत्येक अग्रिम किनारे को 1 के रूप में गिना जाता है, और प्रत्येक पीछे हटने वाले किनारे को-1 के रूप में गिना जाता है। फिर अग्रिम किनारे (यू, वी) पर मान वी का स्तर है। वी पर निहित उप-वृक्ष में नोड्स की संख्याः मान लें कि वी का मूल यू है, अग्रिम किनारे (यू, वी) और पीछे हटने वाले किनारे (वी, यू) को समानांतर में निर्धारित करें, और फिर उपसर्ग योग का उपयोग करके (यू, वी) और (वी, यू) के बीच अग्रिम किनारों की संख्या की गणना करें। एक नोड वी का गहराई-प्रथम खोज सूचकांकः (यू, वी) तक और सहित अग्रिम किनारों की संख्या की गणना करें। दो नोड्स के सबसे कम सामान्य पूर्वज का निर्धारण करें। यूलर टूर ट्री हेंजिंगर और किंग अपने यूलर टूर को एक संतुलित द्विआधारी खोज वृक्ष में रखते हुए किसी दिए गए पेड़ का प्रतिनिधित्व करने का सुझाव देते हैं, जो दौरे में सूचकांक द्वारा प्रमुख होता है। इसलिए उदाहरण के लिए, उपरोक्त उदाहरण में असंतुलित ट्री, जिसमें 7 नोड्स हैं, को 14 नोड्स के साथ एक संतुलित द्विआधारी ट्री द्वारा दर्शाया जाएगा, प्रत्येक बार प्रत्येक नोड दौरे पर दिखाई देता है। हम ई. टी. पेड़ों के संग्रह का उपयोग करके एक वन (एक चक्रीय ग्राफ) का प्रतिनिधित्व कर सकते हैं-एक वन पेड़ के लिए एक ई. टी. पेड़। यह प्रतिनिधित्व हमें इस प्रश्न का त्वरित उत्तर देने की अनुमति देता है कि "नोड वी का मूल क्या है?" केवल ई. टी. ट्री के पहले नोड पर जाकर (क्योंकि ई. टी. ट्री में नोड्स को यूलर टूर में उनके स्थान के आधार पर कुंजीकृत किया जाता है, और रूट टूर में पहला और अंतिम नोड होता है)। जब दर्शाए गए वन को अद्यतन किया जाता है (जैसे। दो पेड़ों को एक ही पेड़ से जोड़कर या एक पेड़ को दो पेड़ों में विभाजित करके), संबंधित यूलर-टूर संरचना को समय ओ (लॉग (एन)) में अद्यतन किया जा सकता है। लिंक/कट पेड़ों में समान प्रदर्शन की गारंटी होती है। जबकि एल. सी. पेड़ एक पेड़ के पथ पर समुच्चय बनाए रखने के लिए अच्छे होते हैं (यह नेटवर्क प्रवाह एल्गोरिदम में एक अच्छा विकल्प डेटा संरचना बनाता है), ई. टी. पेड़ उप-पेड़ों पर समग्र जानकारी रखने में बेहतर होते हैं। संदर्भ ग्राफ एल्गोरिदम समानांतर कंप्यूटिंग