Trémaux tree
வரைபடக் கோட்பாட்டில், திசைதிருப்பப்படாத வரைபடத்தின் ட்ரெமாக்ஸ் மரம் என்பது ஒரு வகை பரவலான மரமாகும், இது ஆழமான முதல் தேடல் மரங்களை பொதுமைப்படுத்துகிறது. மரத்தின் ஒவ்வொரு விளிம்பும் மரத்தில் ஒரு மூதாதையர்-வம்சாவளி ஜோடியை இணைக்கும் பண்பால் அவை வரையறுக்கப்படுகின்றன. 19 ஆம் நூற்றாண்டின் பிரெஞ்சு எழுத்தாளரான சார்லஸ் பியர் ட்ரெமாக்ஸின் பெயரால் ட்ரெமாக்ஸ் மரங்கள் பெயரிடப்பட்டுள்ளன, அவர் மேஸ்களைத் தீர்ப்பதற்கான ஒரு உத்தியாக ஆழமான-முதல் தேடலின் ஒரு வடிவத்தைப் பயன்படுத்தினார். குறிப்பாக எல்லையற்ற வரைபடங்களின் சூழலில் அவை சாதாரண பரவலான மரங்கள் என்றும் அழைக்கப்படுகின்றன. அனைத்து ஆழம்-முதல் தேடல் மரங்கள் மற்றும் அனைத்து ஹாமில்டோனிய பாதைகளும் ட்ரெமாக்ஸ் மரங்களாகும். வரையறுக்கப்பட்ட வரைபடங்களில், ஒவ்வொரு ட்ரெமாக்ஸ் மரமும் ஒரு ஆழம்-முதல் தேடல் மரமாகும், ஆனால் ஆழம்-முதல் தேடல் இயல்பாகவே தொடர்ச்சியானதாக இருந்தாலும், சிக்கலான வகுப்பு ஆர். என். சி. யில் சீரற்ற இணையான வழிமுறையால் ட்ரெமாக்ஸ் மரங்களை உருவாக்க முடியும். ஒரு வரைபடத்தின் மர-ஆழத்தை வரையறுக்கவும், ஒரு வரைபடம் ஒரு சமதள வரைபடமா என்பதை சோதிப்பதற்கான இடது-வலது சமதளச் சோதனையின் ஒரு பகுதியாகவும் அவற்றைப் பயன்படுத்தலாம். வரைபடங்களின் மோனடிக் இரண்டாவது வரிசை தர்க்கத்தில் ட்ரெமாக்ஸ் மரங்களின் தன்மைப்படுத்தல், கோர்செல்லின் தேற்றத்தைப் பயன்படுத்தி வரம்புக்குட்பட்ட மூன்று அகலத்தின் வரைபடங்களுக்கு நோக்குநிலைகளை உள்ளடக்கிய வரைபட பண்புகளை திறம்பட அடையாளம் காண அனுமதிக்கிறது. எல்லையற்ற இணைக்கப்பட்ட ஒவ்வொரு வரைபடத்திற்கும் ஒரு ட்ரெமாக்ஸ் மரம் இல்லை, மேலும் ஒவ்வொரு எல்லையற்ற ட்ரெமாக்ஸ் மரமும் ஒரு ஆழம்-முதல் தேடல் மரம் அல்ல. ட்ரெமாக்ஸ் மரங்களைக் கொண்ட வரைபடங்கள் தடைசெய்யப்பட்ட சிறார்களால் வகைப்படுத்தப்படலாம். ஒரு எல்லையற்ற ட்ரெமாக்ஸ் மரம் வரைபடத்தின் ஒவ்வொரு முனையிலும் சரியாக ஒரு எல்லையற்ற பாதையைக் கொண்டிருக்க வேண்டும், மேலும் ஒரு ட்ரெமாக்ஸ் மரத்தின் இருப்பு ஒவ்வொரு முனையிலும் முடிவிலியில் ஒரு புள்ளியைச் சேர்ப்பதன் மூலம் உருவாக்கப்பட்ட இடவியல் முழுமைகள், மெட்ரிக் இடைவெளிகள். வரையறை மற்றும் எடுத்துக்காட்டுகள் ஒரு ட்ரெமாக்ஸ் மரம், ஒரு வரைபடத்திற்கு, ஒரு பரவலான மரம், ஒவ்வொரு விளிம்பிற்கும், இரண்டு இறுதிப் புள்ளிகளில் ஒன்று மற்றும் மற்றொன்றின் மூதாதையர். ஒரு பரவலான மரமாக இருக்க, அது விளிம்புகளை மட்டுமே பயன்படுத்த வேண்டும், மேலும் ஒவ்வொரு உச்சியையும் உள்ளடக்கியது, ஒவ்வொரு ஜோடி செங்குத்துகளுக்கும் இடையில் ஒரு தனித்துவமான வரையறுக்கப்பட்ட பாதையுடன். கூடுதலாக, இந்த மரத்தில் மூதாதையர்-வம்சாவளி உறவை வரையறுக்க, அதன் செங்குத்துகளில் ஒன்றை அதன் வேர் என்று குறிப்பிட வேண்டும். ஒரு வரையறுக்கப்பட்ட வரைபடம் ஹாமில்டோனியன் பாதையைக் கொண்டிருந்தால், அதன் இரண்டு இறுதிப் புள்ளிகளில் ஒன்றில் அந்த பாதையை வேரூன்றுவது ஒரு ட்ரெமாக்ஸ் மரத்தை உருவாக்குகிறது. அத்தகைய பாதைக்கு, ஒவ்வொரு ஜோடி செங்குத்துகளும் ஒரு மூதாதையர்-வம்சாவளி ஜோடியாகும். கீழே காட்டப்பட்டுள்ள வரைபடத்தில், 1-3,2-3 மற்றும் 3-4 விளிம்புகளைக் கொண்ட மரம், உச்சி 1 அல்லது உச்சி 2 இல் வேரூன்றும்போது ஒரு ட்ரெமாக்ஸ் மரமாகும்ஃ வரைபடத்தின் ஒவ்வொரு விளிம்பும் மரத்திற்கு சொந்தமானது, விளிம்பு 1-2 ஐத் தவிர, இது (இந்த வேர் தேர்வுகளுக்கு) ஒரு மூதாதையர்-வம்சாவளி ஜோடியை இணைக்கிறது. இருப்பினும், அதே மரத்தை உச்சி 3 அல்லது உச்சி 4 இல் வேரூன்றுவது ஒரு வேரூன்றிய மரத்தை உருவாக்குகிறது, இது ஒரு ட்ரெமாக்ஸ் மரம் அல்ல, ஏனெனில் இந்த வேர் 1 மற்றும் 2 இனி ஒருவருக்கொருவர் மூதாதையர் மற்றும் வழித்தோன்றல்கள் அல்ல. வரையறுக்கப்பட்ட வரைபடங்களில் இருப்பு ஒவ்வொரு வரையறுக்கப்பட்ட இணைக்கப்பட்ட திசைதிருப்பப்படாத வரைபடம் குறைந்தது ஒரு ட்ரெமாக்ஸ் மரத்தைக் கொண்டுள்ளது. ஆழமான முதல் தேடலைச் செய்வதன் மூலமும், ஒவ்வொரு முனையையும் (தேடலின் தொடக்க முனையைத் தவிர) அது கண்டுபிடிக்கப்பட்ட முந்தைய முனையுடன் இணைப்பதன் மூலமும் ஒருவர் அத்தகைய மரத்தை உருவாக்க முடியும். இந்த வழியில் கட்டப்பட்ட மரம் ஆழம்-முதல் தேடல் மரம் என்று அழைக்கப்படுகிறது. வரைபடத்தில் ஒரு தன்னிச்சையான விளிம்பாக இருந்தால், தேடல் மூலம் அடையப்பட வேண்டிய இரண்டு செங்குத்துகளில் முந்தையது என்றால், ஆழமான முதல் தேடல் மரத்தில் இருந்து இறங்கும் துணை மரத்தைச் சேர்ந்ததாக இருக்க வேண்டும், ஏனென்றால் இந்த துணை மரத்தை ஆராயும் போது தேடல் அவசியம் கண்டறியப்படும், இது துணை மரத்தில் உள்ள மற்ற செங்குத்துகளில் ஒன்றிலிருந்து அல்லது தோல்வியுற்றால், நேரடியாக இருந்து. ஒவ்வொரு வரையறுக்கப்பட்ட ட்ரெமாக்ஸ் மரத்தையும் ஒரு ஆழமான-முதல் தேடல் மரமாக உருவாக்க முடியும்ஃ ஒரு வரையறுக்கப்பட்ட வரைபடத்தின் ஒரு ட்ரெமாக்ஸ் மரமாக இருந்தால், மேலும் ஆழமான-முதல் தேடல் மற்ற எந்த செங்குத்துகளையும் ஆராய்வதற்கு முன்பு ஒவ்வொரு உச்சியிலும் உள்ள குழந்தைகளை ஆராய்கிறது என்றால், அது அதன் ஆழமான-முதல் தேடல் மரமாக உருவாக்கப்படும். இணையான கட்டுமானம் ட்ரெமாக்ஸ் மரத்தைக் கண்டுபிடிப்பது பி-முழுமையானது, இது ஒரு தொடர்ச்சியான ஆழம்-முதல் தேடல் வழிமுறையால் கண்டறியப்படும், இதில் ஒவ்வொரு உச்சியின் அண்டை நாடுகளும் அவற்றின் அடையாளங்களால் வரிசைப்படுத்தப்படுகின்றன. ஆயினும்கூட, சீரற்ற இணையான வழிமுறை மூலம் வேறுபட்ட ட்ரெமாக்ஸ் மரத்தைக் கண்டுபிடிக்க முடியும், இது ட்ரெமாக்ஸ் மரங்களின் கட்டுமானம் சிக்கலான வகுப்பு ஆர். என். சி. க்கு சொந்தமானது என்பதைக் காட்டுகிறது. 0-1 எடையுள்ள வரைபடங்களில் குறைந்தபட்ச எடை சரியான பொருத்தங்களைக் கண்டுபிடிப்பதற்கான மற்றொரு சீரற்ற இணையான வழிமுறையை அடிப்படையாகக் கொண்டது இந்த வழிமுறை. 1997 ஆம் ஆண்டு நிலவரப்படி, சிக்கலான வகுப்பு NC இல், டிரெமாக்ஸ் மர கட்டுமானத்தை ஒரு தீர்மானகரமான இணையான வழிமுறையால் செய்ய முடியுமா என்பது தெரியவில்லை. NC இல் பொருத்தங்களைக் காண முடிந்தால், ட்ரெமாக்ஸ் மரங்களும் காணலாம். தர்க்கரீதியான வெளிப்பாடு ரூட் வெர்டெக்ஸின் தேர்வுடன் கூடிய விளிம்புகளின் தொகுப்பு ஒரு ட்ரெமாக்ஸ் மரத்தை உருவாக்குகிறது, வரைபடங்களின் மோனடிக் இரண்டாவது வரிசை தர்க்கத்தில், மேலும் குறிப்பாக எம்எஸ்ஓ 2 எனப்படும் இந்த தர்க்கத்தின் வடிவத்தில், இது வெர்டெக்ஸ் மற்றும் எட்ஜ் செட் இரண்டிலும் அளவீட்டை அனுமதிக்கிறது. இந்த பண்பு பின்வரும் பண்புகளின் இணைப்பாக வெளிப்படுத்தப்படலாம்ஃ வரைபடம் விளிம்புகளால் இணைக்கப்பட்டுள்ளது. வரைபடத்தின் செங்குத்துகளின் ஒவ்வொரு காலியாக இல்லாத சரியான துணைக்குழுவிற்கும், கொடுக்கப்பட்ட துணைக்குழுவில் சரியாக ஒரு இறுதிப் புள்ளியுடன் ஒரு விளிம்பு உள்ளது என்ற கூற்றாக இதை தர்க்கரீதியாக வெளிப்படுத்தலாம். அசிக்ளிக் ஆகும். ஒவ்வொரு உச்சியும் பூஜ்ஜியம் அல்லது இரண்டு விளிம்புகளில் நிகழும் ஒரு காலியாக இல்லாத துணைக்குழு இல்லை என்ற அறிக்கையாக இதை தர்க்கரீதியாக வெளிப்படுத்தலாம். உள்ளே இல்லாத ஒவ்வொரு விளிம்பும் ஒரு மூதாதையர்-வம்சாவளி ஜோடி செங்குத்துகளை இணைக்கிறது. இரண்டு இறுதிப் புள்ளிகளும் ஒரு பாதையைச் சேர்ந்ததாக இருக்கும்போது இது உண்மை. அனைத்து விளிம்புகளுக்கும், சரியாக இரண்டு செங்குத்துகள், அவற்றில் ஒன்று, ஒரு விளிம்பில் தற்செயலாக இருக்கும், மேலும் இரண்டு இறுதிப் புள்ளிகளும் குறைந்தபட்சம் ஒரு விளிம்பில் தற்செயலாக இருக்கும் வகையில் ஒரு துணைக்குழு உள்ளது என்ற கூற்றாக தர்க்கரீதியாக வெளிப்படுத்தப்படலாம். ஒரு ட்ரெமாக்ஸ் மரம் இந்த வழியில் அடையாளம் காணப்பட்டவுடன், கொடுக்கப்பட்ட வரைபடத்தின் நோக்குநிலையை, மோனடிக் இரண்டாவது வரிசை தர்க்கத்திலும், மூதாதையர் இறுதிப் புள்ளியில் இருந்து வழித்தோன்றல் இறுதிப் புள்ளி வரை நோக்குநிலையைக் கொண்ட விளிம்புகளின் தொகுப்பைக் குறிப்பிடுவதன் மூலம் விவரிக்க முடியும். இந்த தொகுப்புக்கு வெளியே மீதமுள்ள விளிம்புகள் வேறு திசையில் அமைந்திருக்க வேண்டும். இந்த நுட்பம் நோக்குநிலைகளை உள்ளடக்கிய வரைபட பண்புகளை மோனடிக் இரண்டாவது வரிசை தர்க்கத்தில் குறிப்பிட அனுமதிக்கிறது, இது கோர்செல்லின் தேற்றத்தைப் பயன்படுத்தி வரம்புக்குட்பட்ட மூன்று அகலத்தின் வரைபடங்களில் இந்த பண்புகளை திறம்பட சோதிக்க அனுமதிக்கிறது. தொடர்புடைய பண்புகள் ஒரு வரைபடம் ஹாமில்டோனியன் பாதையைக் கொண்டிருந்தால், அந்த பாதையும் (அதன் இறுதிப் புள்ளிகளில் ஒன்றில் வேரூன்றியுள்ளது) ஒரு ட்ரெமாக்ஸ் மரமாகும். ஒவ்வொரு ட்ரெமாக்ஸ் மரமும் இந்த வடிவத்தைக் கொண்ட திசைதிருப்பப்படாத வரைபடங்கள் சுழற்சி வரைபடங்கள், முழுமையான வரைபடங்கள் மற்றும் சீரான முழுமையான இருதரப்பு வரைபடங்கள் ஆகும். ட்ரீமாக்ஸ் மரங்கள் மர ஆழம் என்ற கருத்துடன் நெருக்கமாக தொடர்புடையவை. ஒரு வரைபடத்தின் மர-ஆழத்தை ஒரு வரைபடம் இருக்கும் மிகச்சிறிய எண் என்று வரையறுக்கலாம், ஆழத்தின் ட்ரெமாக்ஸ் மரத்துடன், இது ஒரு துணை வரைபடமாகும். வரையறுக்கப்பட்ட மர ஆழம், வரைபடங்களின் குடும்பத்தில், குடும்பத்தில் உள்ள வரைபடங்களின் சிறிய வரைபடமாக ஏற்பட முடியாத ஒரு பாதையின் இருப்புக்கு சமம். வரைபடங்களில் உள்ள பல கடினமான கணக்கீட்டு சிக்கல்கள் அவற்றின் உள்ளீடுகளின் மர-ஆழத்தால் அளவுருவாக இருக்கும்போது நிலையான-அளவுரு கையாளக்கூடிய வழிமுறைகளைக் கொண்டுள்ளன. கொடுக்கப்பட்ட வரைபடம் சமதளமாக உள்ளதா என்பதைச் சோதிப்பதற்கான ஃப்ரேஸிக்ஸ்-ரோசன்ஸ்டியல் பிளானாரிட்டி அளவுகோலில் ட்ரெமாக்ஸ் மரங்கள் முக்கிய பங்கு வகிக்கின்றன. இந்த அளவுகோலின் படி, கொடுக்கப்பட்ட ட்ரெமாக்ஸ் மரத்திற்கு, மீதமுள்ள விளிம்புகளை மரத்தின் இடது அல்லது வலதுபுறத்தில் சீரான முறையில் வைக்க முடியும் என்றால், அதே இடத்தைக் கொண்ட விளிம்புகள் ஒன்றையொன்று கடப்பதைத் தடுக்கும் கட்டுப்பாடுகளுக்கு உட்பட்டு ஒரு வரைபடம் சமதளமாக இருக்கும். எல்லையற்ற வரைபடங்களில் இருப்பு ஒவ்வொரு எல்லையற்ற வரைபடமும் ஒரு சாதாரண பரவலான மரத்தைக் கொண்டிருக்கவில்லை. உதாரணமாக, எண்ணற்ற செங்குத்துகளின் தொகுப்பில் ஒரு முழுமையான வரைபடம் ஒன்றைக் கொண்டிருக்கவில்லைஃ ஒரு முழுமையான வரைபடத்தில் ஒரு சாதாரண பரவலான மரம் ஒரு பாதையாக மட்டுமே இருக்க முடியும், ஆனால் ஒரு பாதையில் எண்ணக்கூடிய எண்ணிக்கையிலான செங்குத்துகள் மட்டுமே உள்ளன. இருப்பினும், எண்ணக்கூடிய செங்குத்துகளின் தொகுப்பில் உள்ள ஒவ்வொரு வரைபடமும் ஒரு சாதாரண பரவலான மரத்தைக் கொண்டுள்ளது. எண்ணக்கூடிய வரைபடங்களில் கூட, ஆழமான முதல் தேடல் இறுதியில் முழு வரைபடத்தையும் ஆராய்வதில் வெற்றிபெறாமல் போகலாம், மேலும் ஒவ்வொரு சாதாரண பரவலான மரத்தையும் ஆழமான முதல் தேடல் மூலம் உருவாக்க முடியாதுஃ ஒரு ஆழமான முதல் தேடல் மரமாக இருக்க, எண்ணக்கூடிய சாதாரண பரவலான மரத்திற்கு ஒரே ஒரு எல்லையற்ற பாதை அல்லது எண்ணற்ற பல குழந்தைகளுடன் (இரண்டும் அல்ல) ஒரு முனை இருக்க வேண்டும். ஒரு எல்லையற்ற வரைபடம் ஒரு இயல்பான பரவலான மரத்தைக் கொண்டிருந்தால், இணைக்கப்பட்ட ஒவ்வொரு வரைபடமும் சிறியதாக இருக்கும். இதிலிருந்து இயல்பாக பரவியிருக்கும் மரங்களைக் கொண்ட வரைபடங்கள் தடைசெய்யப்பட்ட சிறார்களின் குணாதிசயத்தைக் கொண்டுள்ளன. தடைசெய்யப்பட்ட சிறார்களின் இரண்டு வகுப்புகளில் ஒன்று இருதரப்பு வரைபடங்களைக் கொண்டுள்ளது, இதில் இரு பிரிவின் ஒரு பக்கம் கணக்கிடக்கூடியது, மறுபுறம் கணக்கிட முடியாதது, ஒவ்வொரு உச்சியும் எல்லையற்ற டிகிரியைக் கொண்டுள்ளது. தடைசெய்யப்பட்ட சிறார்களின் மற்ற வகுப்பு அரோன்சாஜன் மரங்களிலிருந்து பெறப்பட்ட சில வரைபடங்களைக் கொண்டுள்ளது. இந்த குணாதிசயத்தின் விவரங்கள் கணிதத்தை முறைப்படுத்த பயன்படுத்தப்படும் தொகுப்பு-கோட்பாட்டு கோட்பாட்டு கோட்பாட்டின் தேர்வைப் பொறுத்தது. குறிப்பாக, மார்ட்டினின் கோட்பாடு உண்மை மற்றும் தொடர்ச்சியான கருதுகோள் தவறான தொகுப்புக் கோட்பாட்டின் மாதிரிகளில், இந்த குணாதிசயத்தில் உள்ள இருதரப்பு வரைபடங்களின் வகுப்பை ஒற்றை தடைசெய்யப்பட்ட சிறியதாக மாற்றலாம். இருப்பினும், தொடர்ச்சியான கருதுகோள் உண்மையாக இருக்கும் மாதிரிகளுக்கு, இந்த வகுப்பில் சிறிய வரிசையில் ஒருவருக்கொருவர் ஒப்பிட முடியாத வரைபடங்கள் உள்ளன. முனைகள் மற்றும் அளவிடுதல் இயல்பான பரவலான மரங்கள் எல்லையற்ற வரைபடத்தின் முனைகளுடன் நெருக்கமாக தொடர்புடையவை, எல்லையற்ற பாதைகளின் சமநிலை வகுப்புகள், உள்ளுணர்வாக, அதே திசையில் முடிவிலிக்குச் செல்கின்றன. ஒரு வரைபடத்தில் ஒரு சாதாரண பரவலான மரம் இருந்தால், இந்த மரம் ஒவ்வொரு வரைபடத்தின் முனைகளுக்கும் சரியாக ஒரு எல்லையற்ற பாதையைக் கொண்டிருக்க வேண்டும். வரைகலை ஒரு எளிமையான சிக்கலாகப் பார்ப்பதன் மூலமும், வரைபடத்தின் ஒவ்வொரு முனையிலும் முடிவிலியில் ஒரு புள்ளியைச் சேர்ப்பதன் மூலமும் ஒரு எல்லையற்ற வரைபடத்தைப் பயன்படுத்தி ஒரு இடவியல் இடத்தை உருவாக்கலாம். இந்த இடவியல் மூலம், ஒரு வரைபடம் ஒரு இயல்பான பரவலான மரத்தைக் கொண்டுள்ளது, அதன் செங்குத்துகளின் தொகுப்பை மூடிய தொகுப்புகளின் எண்ணக்கூடிய சங்கமமாக சிதைக்க முடிந்தால் மட்டுமே. கூடுதலாக, வரைபடத்தில் ஒரு சாதாரண பரவலான மரம் இருந்தால் மட்டுமே இந்த இடவியல் இடத்தை ஒரு மெட்ரிக் இடத்தால் குறிக்க முடியும். குறிப்புகள் வரைபடக் கோட்பாடு பொருள்கள் மர வரைபடம் சிறிய கோட்பாடு எல்லையற்ற வரைபடங்கள்