Euler tour technique
லியோன்ஹார்ட் யூலரின் பெயரால் பெயரிடப்பட்ட யூலர் சுற்றுப்பயண நுட்பம் (ஈ. டி. டி), மரங்களைக் குறிக்கும் வரைபடக் கோட்பாட்டில் ஒரு முறையாகும். மரத்தின் ஒவ்வொரு விளிம்புக்கும் இரண்டு திசைப்படுத்தப்பட்ட விளிம்புகளைக் கொண்ட ஒரு திசைப்படுத்தப்பட்ட வரைபடமாக மரம் பார்க்கப்படுகிறது. மரத்தின் யூலர் சுற்று பிரதிநிதித்துவம் (ஈ. டி. ஆர்) என்று அழைக்கப்படும் இயக்கப்பட்ட வரைபடத்தின் யூலேரியன் சுற்றாக மரத்தை பின்னர் குறிப்பிடலாம். வழிமுறை வரைபடக் கோட்பாட்டில் பொதுவான சிக்கல்களுக்கான தீர்வுகளின் திறமையான, இணையான கணக்கீட்டை ETT அனுமதிக்கிறது. இது 1984 ஆம் ஆண்டில் டார்ஜன் மற்றும் விஷ்கின் ஆகியோரால் அறிமுகப்படுத்தப்பட்டது. ஓரங்களின் தொகுப்பாக வழங்கப்பட்ட ஒரு திசைதிருப்பப்படாத மரத்தைக் கருத்தில் கொண்டு, யூலர் சுற்றுப்பயண பிரதிநிதித்துவத்தை (ஈ. டி. ஆர்) பின்வருமாறு இணையாக கட்டமைக்க முடியும்ஃ திசைதிருப்பப்பட்ட விளிம்புகளின் சமச்சீர் பட்டியலை நாம் உருவாக்குகிறோம்ஃ மரத்தில் உள்ள ஒவ்வொரு திசைதிருப்பப்படாத விளிம்புக்கும் (யு, வி), விளிம்பு பட்டியலில் (யு, வி) மற்றும் (வி, யு) ஆகியவற்றைச் செருகவும். விளிம்புப் பட்டியலை அகராதியியல் ரீதியாக வரிசைப்படுத்துங்கள். (இங்கே மரத்தின் முனைகள் வரிசைப்படுத்தப்பட்டுள்ளன என்றும், இந்த வரிசையில் வேர் முதல் உறுப்பு என்றும் கருதுகிறோம்.) ஒவ்வொரு முனைக்கும் (அடுத்தது என்று அழைக்கப்படும்) அருகாமைப் பட்டியல்களையும், முனைகளிலிருந்து அருகாமைப் பட்டியல்களின் முதல் உள்ளீடுகளுக்கு (முதல் என்று அழைக்கப்படும்) ஒரு வரைபடத்தையும் உருவாக்குங்கள்ஃ பட்டியலில் உள்ள ஒவ்வொரு விளிம்புக்கும் (u, v), இணையாகச் செய்யுங்கள்ஃ முந்தைய விளிம்பில் (x, y) x  ஒத்ததாக இருந்தால், அதாவது. வேறு முனையிலிருந்து தொடங்கி, முதலில் அமைக்கவும் (u) = (u, v) இல்லையெனில் x = u என்றால், அதாவது. அதே முனையிலிருந்து தொடங்கி, அடுத்ததாக அமைக்கவும் (x, y) = (u, v) பின்வரும் விதியின்படி இணையாக அனைத்து விளிம்புகளுக்கும் (u, v) சுட்டிகள் ஸக் (u, v) ஐ அமைப்பதன் மூலம் ஆய்லர் சுற்றுப்பயண வரிசையில் ஒரு விளிம்பு பட்டியலை (சக் என்று அழைக்கப்படுகிறது) உருவாக்கவும்ஃ இதன் விளைவாக வரும் பட்டியல் சக் வட்டமாக இருக்கும். மரங்களில் n முனைகள் இருந்தால், ஒட்டுமொத்த கட்டுமானத்திற்கு W (n) = O (வரிசைப்படுத்தல் (n)) (n உருப்படிகளை இணையாக வரிசைப்படுத்த எடுக்கும் நேரம்) வேலை எடுக்கும், மரங்களில் விளிம்புகளின் எண்ணிக்கை முனைகளின் எண்ணிக்கையை விட ஒன்று குறைவாக இருக்கும். வேர்கள், முன்கூட்டியே மற்றும் பின்வாங்கும் விளிம்புகள் மரத்திற்கு ஒரு வேர் இருந்தால், அந்த வேரில் வட்டப் பட்டியலை நாம் பிரிக்கலாம். அவ்வாறான நிலையில், முன்கூட்டிய மற்றும் பின்வாங்கும் விளிம்புகளைப் பற்றி நாம் பேசலாம்ஃ ஒரு ஜோடி முனைகள் u, v கொடுக்கப்பட்டால், ETR இல் (u, v) அல்லது (v, u) இன் முதல் நிகழ்வு முன்கூட்டிய விளிம்பு என்றும், இரண்டாவது நிகழ்வு பின்வாங்கும் விளிம்பு என்றும் அழைக்கப்படுகிறது. முதல் முறையாக அத்தகைய விளிம்பைக் கடக்கும்போது வேருக்கான தூரம் அதிகரிக்கப்படுகிறது, அதே நேரத்தில் இரண்டாவது முறையாக தூரம் குறைகிறது என்ற உள்ளுணர்வுக்கு இது முறையீடு செய்கிறது. புதிய வேரில் வட்டப் பட்டியலைப் பிரிப்பதன் மூலம் ஓ (1) நிலையான நேரத்தில் மரத்தை மறுசீரமைக்கலாம். பயன்பாடுகள் பின்வரும் அனைத்து சிக்கல்களையும் O (முன்னொட்டு தொகை (n)) இல் தீர்க்க முடியும் (n உருப்படிகளின் பட்டியலுக்கு இணையாக முன்னொட்டு தொகை சிக்கலைத் தீர்க்க எடுக்கும் நேரம்): முன்கூட்டியே மற்றும் பின்வாங்கும் விளிம்புகளை வகைப்படுத்துதல்ஃ ETR இல் தரவரிசையை பட்டியலிட்டு முடிவை இரு பரிமாண வரிசை A இல் சேமிக்கவும். பின்னர் (u, v) என்பது A (u, v) <A (v, u) இன் முன்கூட்டிய விளிம்பாகும், இல்லையெனில் பின்வாங்கும் விளிம்பாகும். ஒவ்வொரு முனையின் அளவையும் தீர்மானிக்கவும்ஃ ETR இல் ஒரு முன்னொட்டு தொகையைச் செய்யுங்கள், அங்கு ஒவ்வொரு முன்கூட்டிய விளிம்பும் 1 ஆகக் கணக்கிடப்படுகிறது, மேலும் ஒவ்வொரு பின்வாங்கும் விளிம்பும்-1 ஆகக் கணக்கிடப்படுகிறது. பின்னர் முன்கூட்டிய விளிம்பில் உள்ள மதிப்பு (u, v) என்பது v இன் நிலை. v இல் வேரூன்றிய ஒரு துணை மரத்தில் உள்ள முனைகளின் எண்ணிக்கைஃ v இன் பெற்றோர் u என்று வைத்துக் கொள்ளுங்கள், முன்கூட்டிய விளிம்பை (u, v) மற்றும் பின்வாங்கும் விளிம்பை (v, u) இணையாக தீர்மானிக்கவும், பின்னர் (u, v) மற்றும் (v, u) க்கு இடையிலான முன்கூட்டிய விளிம்புகளின் எண்ணிக்கையை முன்னொட்டு கூட்டுத்தொகையைப் பயன்படுத்தி கணக்கிடுங்கள். ஒரு முனை v இன் ஆழம்-முதல் தேடல் குறியீடுஃ (u, v) வரை மற்றும் உட்பட முன்கூட்டிய விளிம்புகளின் எண்ணிக்கையை எண்ணுங்கள். இரண்டு முனைகளின் மிகக் குறைந்த பொதுவான மூதாதையரைத் தீர்மானிக்கவும். யூலர் சுற்றுப்பயண மரங்கள் ஹென்சிங்கர் மற்றும் கிங் ஒரு குறிப்பிட்ட மரத்தை அதன் யூலர் சுற்றுப்பயணத்தை ஒரு சமநிலையான பைனரி தேடல் மரத்தில் வைத்திருப்பதன் மூலம் பிரதிநிதித்துவப்படுத்த பரிந்துரைக்கிறார்கள், இது சுற்றுப்பயணத்தின் குறியீட்டால் முக்கியமானது. எனவே எடுத்துக்காட்டாக, மேலே உள்ள எடுத்துக்காட்டில் உள்ள சமநிலையற்ற மரம், 7 முனைகளைக் கொண்ட, 14 முனைகளைக் கொண்ட ஒரு சீரான பைனரி மரத்தால் குறிக்கப்படும், ஒவ்வொரு முறை ஒவ்வொரு முனையும் சுற்றுப்பயணத்தில் தோன்றும். ET மரங்களின் தொகுப்பைப் பயன்படுத்தி ஒரு காட்டை (ஒரு அசைக்ளிக் கிராஃப்) நாம் பிரதிநிதித்துவப்படுத்தலாம்-ஒரு வன மரத்திற்கு ஒரு ET மரம். இந்த பிரதிநிதித்துவம் "முனை v இன் வேர் என்ன?" என்ற கேள்விக்கு விரைவாக பதிலளிக்க அனுமதிக்கிறது. ET மரத்தின் முதல் முனைக்குச் செல்வதன் மூலம் (ET மரத்தில் உள்ள முனைகள் யூலர் சுற்றுப்பயணத்தில் அவற்றின் இருப்பிடத்தால் முக்கியப்படுத்தப்படுவதால், சுற்றுப்பயணத்தின் முதல் மற்றும் கடைசி முனை வேர் ஆகும்). குறிப்பிடப்பட்ட காடு புதுப்பிக்கப்படும் போது (எ. கா. இரண்டு மரங்களை ஒரே மரத்துடன் இணைப்பதன் மூலமோ அல்லது ஒரு மரத்தை இரண்டு மரங்களாகப் பிரிப்பதன் மூலமோ), அதனுடன் தொடர்புடைய ஆய்லர்-டூர் கட்டமைப்பை ஓ (பதிவு (என்)) நேரத்தில் புதுப்பிக்க முடியும். இணைப்பு/வெட்டப்பட்ட மரங்கள் இதே போன்ற செயல்திறன் உத்தரவாதங்களைக் கொண்டுள்ளன. எல். சி மரங்கள் ஒரு மரத்தின் பாதைகளில் திரட்டல்களைப் பராமரிப்பதற்கு நல்லவை என்றாலும் (நெட்வொர்க் ஃப்லோ வழிமுறைகளில் இது ஒரு நல்ல தேர்வு தரவு கட்டமைப்பாக அமைகிறது), ஈ. டி மரங்கள் துணை மரங்கள் பற்றிய மொத்த தகவல்களை வைத்திருப்பதில் சிறந்தவை. குறிப்புகள் வரைபட வழிமுறைகள் இணையான கணக்கீடு