Treewidth
வரைபடக் கோட்பாட்டில், திசைதிருப்பப்படாத வரைபடத்தின் மூன்று அகலம் என்பது ஒரு முழு எண் ஆகும், இது முறைசாரா முறையில், வரைபடம் ஒரு மரத்திலிருந்து எவ்வளவு தொலைவில் உள்ளது என்பதைக் குறிப்பிடுகிறது. மிகச்சிறிய மூன்று அகலம் 1 ஆகும்; மூன்று அகலம் 1 கொண்ட வரைபடங்கள் சரியாக மரங்கள் மற்றும் காடுகள் ஆகும். அதிகபட்சம் 2 அகலம் கொண்ட வரைபடங்கள் தொடர்-இணையான வரைபடங்களாகும். சரியாக மூன்று அகலம் கொண்ட அதிகபட்ச வரைபடங்கள்-மரங்கள் என்றும், அதிகபட்சமாக மூன்று அகலம் கொண்ட வரைபடங்கள் பகுதி-மரங்கள் என்றும் அழைக்கப்படுகின்றன. நன்கு ஆய்வு செய்யப்பட்ட பல வரைபடக் குடும்பங்களும் முக்கோண அகலத்தை எல்லையாகக் கொண்டுள்ளன. மூன்று அகலத்தை முறைப்படி பல சமமான வழிகளில் வரையறுக்கலாம்ஃ வரைபடத்தின் ஒரு மர சிதைவில் அமைக்கப்பட்ட மிகப்பெரிய உச்சியின் அளவைப் பொறுத்தவரை, வரைபடத்தின் கார்டல் நிறைவு செய்வதில் மிகப்பெரிய குழுவின் அளவைப் பொறுத்தவரை, வரைபடத்தில் ஒரு பின்தொடர்தல்-தவிர்ப்பு விளையாட்டுக்கான ஒரு மூலோபாயத்தை விவரிக்கும் ஒரு புகலிடத்தின் அதிகபட்ச வரிசையின் அடிப்படையில், அல்லது ஒரு பிராம்பிளின் அதிகபட்ச வரிசையின் அடிப்படையில், ஒருவருக்கொருவர் தொடும் இணைக்கப்பட்ட துணை வரைபடங்களின் தொகுப்பு. வரைபட வழிமுறைகளின் அளவுருப்படுத்தப்பட்ட சிக்கலான பகுப்பாய்வில் மூன்று அகலம் பொதுவாக ஒரு அளவுருவாகப் பயன்படுத்தப்படுகிறது. பொதுவான வரைபடங்களுக்கு NP-கடினமான பல வழிமுறைகள், மூன்று அகலம் ஒரு மாறிலியால் கட்டுப்படுத்தப்படும்போது எளிதாகிறது. மூன்று அகலம் என்ற கருத்து முதலில் பரிமாணம் என்ற பெயரில் அறிமுகப்படுத்தப்பட்டது. இது பின்னர் மற்றொரு வரைபட அளவுருவான ஹாட்விகர் எண்ணுடன் பகிர்ந்து கொள்ளும் பண்புகளின் அடிப்படையில் மீண்டும் கண்டுபிடிக்கப்பட்டது. பின்னர் இது மீண்டும் கண்டுபிடிக்கப்பட்டது, பின்னர் பல எழுத்தாளர்களால் ஆய்வு செய்யப்பட்டுள்ளது. வரையறை ஒரு வரைபடத்தின் மர சிதைவு என்பது முனைகளைக் கொண்ட ஒரு மரமாகும், இதில் ஒவ்வொன்றும் ஒரு துணைக்குழுவாகும், இது பின்வரும் பண்புகளை திருப்திப்படுத்துகிறது (முனை என்ற சொல் உச்சிகளுடன் குழப்பத்தைத் தவிர்ப்பதற்காக ஒரு உச்சியைக் குறிக்கப் பயன்படுகிறது): அனைத்து தொகுப்புகளின் ஒன்றிணைப்பும் சமம். அதாவது, ஒவ்வொரு வரைபட உச்சியும் குறைந்தபட்சம் ஒரு மர முனையில் உள்ளது. இரண்டும் ஒரு உச்சியைக் கொண்டிருந்தால், இடையில் உள்ள (தனித்துவமான) பாதையில் உள்ள அனைத்து முனைகளும் உள்ளன. சமமாக, உச்சியைக் கொண்ட மர முனைகள் இணைக்கப்பட்ட துணை மரத்தை உருவாக்குகின்றன. வரைபடத்தில் உள்ள ஒவ்வொரு விளிம்பிற்கும், மற்றும் இரண்டையும் கொண்ட ஒரு துணைக்குழு உள்ளது. அதாவது, தொடர்புடைய சப்ட்ரீக்கள் பொதுவான முனையைக் கொண்டிருக்கும்போது மட்டுமே செங்குத்துகள் வரைபடத்தில் அருகிலேயே இருக்கும். ஒரு மரத்தின் சிதைவின் அகலம் அதன் மிகப்பெரிய தொகுப்பு கழித்தல் ஒன்றின் அளவு ஆகும். ஒரு வரைபடத்தின் மூன்று அகலம் என்பது மரத்தின் சாத்தியமான அனைத்து சிதைவுகளிலும் குறைந்தபட்ச அகலமாகும். இந்த வரையறையில், ஒரு மரத்தின் மூன்று அகலத்தை ஒன்றுக்கு சமமாக்குவதற்காக மிகப்பெரிய தொகுப்பின் அளவு ஒன்றால் குறைக்கப்படுகிறது. சமமாக, இன் மூன்று அகலம் மிகச்சிறிய கிளிக் எண்ணைக் கொண்ட கார்டல் வரைபடத்தில் உள்ள மிகப்பெரிய கிளிக்கின் அளவை விட ஒன்று குறைவாக உள்ளது. ஒவ்வொரு இரண்டு செங்குத்துகளுக்கும் இடையில் ஒரு விளிம்பில் சேர்ப்பதன் மூலம் இந்த கிளிக் அளவைக் கொண்ட ஒரு கார்டல் வரைபடத்தைப் பெறலாம், அவை இரண்டும் குறைந்தபட்சம் ஒரு தொகுப்பைச் சேர்ந்தவை. ஒரு வரைபடத்தில் வரையறுக்கப்பட்ட ஒரு குறிப்பிட்ட பின்தொடர்தல்-தப்பிக்கும் விளையாட்டுக்கான தப்பித்தல் மூலோபாயத்தை விவரிக்கும் செயல்பாடுகள், புகலிடங்களின் அடிப்படையில் மூன்று அகலமும் வகைப்படுத்தப்படலாம். ஒரு வரைபடம் வரிசையின் புகலிடத்தைக் கொண்டிருந்தாலும், ஆனால் உயர் வரிசை இல்லை என்றால் மட்டுமே மூன்று அகலத்தைக் கொண்டுள்ளது, அங்கு வரிசையின் புகலிடமானது ஒவ்வொரு செங்குத்துகளையும் இணைக்கப்பட்ட கூறுகளில் ஒன்றுக்குள் வரைபடமாக்கும் ஒரு செயல்பாடாகும், மேலும் அது எந்த நேரத்திலும் மோனோடோனிசிட்டி பண்புக்குக் கீழ்ப்படிகிறது. பிராம்பிள்களைப் பயன்படுத்தி இதேபோன்ற குணாதிசயத்தையும் உருவாக்கலாம், இணைக்கப்பட்ட துணை வரைபடங்களின் குடும்பங்கள் அனைத்தும் ஒருவருக்கொருவர் தொடுகின்றன (அதாவது அவை ஒரு உச்சியைப் பகிர்ந்து கொள்கின்றன அல்லது ஒரு விளிம்பால் இணைக்கப்பட்டுள்ளன). பிராம்பிளின் வரிசை என்பது துணை வரைபடங்களின் குடும்பத்திற்கான மிகச்சிறிய தாக்கும் தொகுப்பாகும், மேலும் ஒரு வரைபடத்தின் மூன்று அகலம் ஒரு பிராம்பிளின் அதிகபட்ச வரிசையை விட ஒன்று குறைவாக இருக்கும். எடுத்துக்காட்டுகள் ஒவ்வொரு முழுமையான வரைபடத்திற்கும் மூன்று அகலம் உள்ளது. கார்டல் வரைபடங்களின் அடிப்படையில் மூன்று அகலத்தின் வரையறையைப் பயன்படுத்தி இது மிகவும் எளிதாகக் காணப்படுகிறதுஃ முழுமையான வரைபடம் ஏற்கனவே கார்டல் ஆகும், மேலும் அதிக விளிம்புகளைச் சேர்ப்பது அதன் மிகப்பெரிய குழுவின் அளவைக் குறைக்க முடியாது. குறைந்தபட்சம் இரண்டு செங்குத்துகளைக் கொண்ட ஒரு இணைக்கப்பட்ட வரைபடம் ஒரு மரமாக இருந்தால் மட்டுமே மூன்று அகலம் 1 ஐக் கொண்டிருக்கும். ஒரு மரம் முழுமையான வரைபடங்களைப் போலவே அதே காரணத்தால் மூன்று அகலங்களைக் கொண்டுள்ளது (அதாவது, இது கார்டல் மற்றும் அதிகபட்ச கிளைக் அளவு இரண்டைக் கொண்டுள்ளது). மாறாக, ஒரு வரைபடத்திற்கு ஒரு சுழற்சி இருந்தால், வரைபடத்தின் ஒவ்வொரு கார்டல் முடிவும் சுழற்சியின் மூன்று தொடர்ச்சியான செங்குத்துகளைக் கொண்ட குறைந்தது ஒரு முக்கோணத்தையாவது உள்ளடக்கியது, அதில் இருந்து அதன் மூன்று அகலம் குறைந்தது இரண்டு ஆகும். எல்லைக்குட்பட்ட முக்கோண அகல வரைபடக் குடும்பங்கள் எந்தவொரு நிலையான மாறிலிக்கும், முக்கோண அகலத்தின் வரைபடங்கள் அதிகபட்சமாக பகுதி-மரங்கள் என்று அழைக்கப்படுகின்றன. வரம்புக்குட்பட்ட மூன்று அகலம் கொண்ட வரைபடங்களின் பிற குடும்பங்களில் கற்றாழை வரைபடங்கள், போலி காடுகள், தொடர்-இணையான வரைபடங்கள், வெளிப்புற பிளானர் வரைபடங்கள், ஹாலின் வரைபடங்கள் மற்றும் அப்பல்லோனிய நெட்வொர்க்குகள் ஆகியவை அடங்கும். கட்டமைக்கப்பட்ட நிரல்களின் தொகுப்பில் எழும் கட்டுப்பாட்டு-ஓட்ட வரைபடங்களும் மூன்று அகலத்தை வரையறுக்கின்றன, இது பதிவு ஒதுக்கீடு போன்ற சில பணிகளை திறம்பட செய்ய அனுமதிக்கிறது. பிளானர் வரைபடங்கள் வரையறுக்கப்பட்ட மூன்று அகலத்தைக் கொண்டிருக்கவில்லை, ஏனென்றால் கிரிட் வரைபடம் சரியாக மூன்று அகலத்துடன் ஒரு பிளானர் வரைபடமாகும். எனவே, வரையறுக்கப்பட்ட மூன்று அகலம் கொண்ட ஒரு சிறிய மூடிய வரைபடக் குடும்பமாக இருந்தால், அது அனைத்து சமதள வரைபடங்களையும் சேர்க்க முடியாது. மாறாக, சில பிளானர் வரைபடம் குடும்பத்தில் உள்ள வரைபடங்களுக்கு ஒரு சிறியதாக ஏற்பட முடியாவிட்டால், அனைத்து வரைபடங்களும் அதிகபட்சமாக மூன்று அகலத்தைக் கொண்டிருக்கும் வகையில் ஒரு மாறிலி உள்ளது. அதாவது, பின்வரும் மூன்று நிபந்தனைகள் ஒன்றுக்கொன்று சமமானவைஃ வரையறுக்கப்பட்ட-மூன்று அகல வரைபடங்களின் ஒரு சிறிய-மூடப்பட்ட குடும்பம்; வரையறுக்கப்பட்ட பல தடைசெய்யப்பட்ட சிறார்களில் ஒன்று பிளானர்; அனைத்து பிளானர் வரைபடங்களையும் உள்ளடக்காத ஒரு சிறிய-மூடப்பட்ட வரைபட குடும்பம். தடைசெய்யப்பட்ட மைனர்கள் ஒவ்வொரு வரையறுக்கப்பட்ட மதிப்பிற்கும், அதிகபட்சமாக மூன்று அகலத்தின் வரைபடங்கள் தடைசெய்யப்பட்ட மைனர்களின் வரையறுக்கப்பட்ட தொகுப்பால் வகைப்படுத்தப்படலாம். (அதாவது, மூன்று அகலம் கொண்ட எந்த வரைபடமும் தொகுப்பில் உள்ள வரைபடங்களில் ஒன்றை சிறியதாக உள்ளடக்கியது.) தடைசெய்யப்பட்ட சிறார்களின் இந்த தொகுப்புகள் ஒவ்வொன்றும் குறைந்தது ஒரு பிளானர் வரைபடத்தை உள்ளடக்கியது. ஏனெனில், தனித்துவமான தடைசெய்யப்பட்ட சிறியது 3-வெர்டெக்ஸ் சுழற்சி வரைபடமாகும். ஏனெனில், தனித்துவமான தடைசெய்யப்பட்ட சிறியது 4-வெர்டெக்ஸ் முழுமையான வரைபடமாகும். ஏனெனில், நான்கு தடைசெய்யப்பட்ட மைனர்கள் உள்ளனஃ எண்முகத்தின் வரைபடம், ஐங்கோண ப்ரிஸம் வரைபடம் மற்றும் வாக்னர் வரைபடம். இவற்றில், இரண்டு பாலிஹெட்ரல் வரைபடங்கள் சமதளமாக உள்ளன. பெரிய மதிப்புகளுக்கு, தடைசெய்யப்பட்ட சிறார்களின் எண்ணிக்கை குறைந்தபட்சம் சதுர மூலத்தின் அதிவேகத்தைப் போலவே விரைவாக வளர்கிறது. இருப்பினும், தடைசெய்யப்பட்ட சிறார்களின் அளவு மற்றும் எண்ணிக்கையில் அறியப்பட்ட மேல் வரம்புகள் இந்த கீழ் வரம்பை விட மிக அதிகமாக உள்ளன. வழிமுறைகள் மூன்று அகலத்தை கணக்கிடுவது கொடுக்கப்பட்ட வரைபடம் கொடுக்கப்பட்ட மாறிக்கு அதிகபட்சமாக மூன்று அகலத்தைக் கொண்டிருக்கிறதா என்பதைத் தீர்மானிக்க NP-முழுமையானது. இருப்பினும், எந்த நிலையான மாறிலியும் இருக்கும்போது, மூன்று அகலம் கொண்ட வரைபடங்களை அடையாளம் காண முடியும், மேலும் அவற்றுக்கு ஒரு அகல மரம் சிதைவு, நேரியல் நேரத்தில் கட்டப்பட்டது. இந்த வழிமுறையின் நேர சார்பு அதிவேகமானது. ஏராளமான துறைகளில் மூன்று அகலம் வகிக்கும் பாத்திரங்கள் காரணமாக, ஒரு வரைபடத்தின் மூன்று அகலத்தை கணக்கிடும் வெவ்வேறு நடைமுறை மற்றும் தத்துவார்த்த வழிமுறைகள் உருவாக்கப்பட்டன. கையில் உள்ள பயன்பாட்டைப் பொறுத்து, ஒருவர் சிறந்த தோராய விகிதத்தை விரும்பலாம், அல்லது உள்ளீட்டின் அளவு அல்லது மூன்று அகலத்திலிருந்து இயங்கும் நேரத்தில் சிறந்த சார்பு. கீழேயுள்ள அட்டவணை சில மூன்று அகல வழிமுறைகளின் கண்ணோட்டத்தை வழங்குகிறது. இங்கே மூன்று அகலம் மற்றும் ஒரு உள்ளீட்டு வரைபடத்தின் செங்குத்துகளின் எண்ணிக்கை. ஒவ்வொரு வழிமுறையும் தோராயமான நெடுவரிசையில் கொடுக்கப்பட்ட அகலத்தின் சிதைவை காலப்போக்கில் வெளியிடுகிறது. எடுத்துக்காட்டாக, இன் டைம் வழிமுறை அகலத்தின் உள்ளீட்டு வரைபடத்தின் ஒரு மர சிதைவை உருவாக்குகிறது அல்லது அதன் மூன்று அகலம் அதை விட அதிகமாக இருப்பதாக தெரிவிக்கிறது. இதேபோல், காலத்தின் வழிமுறை அகலத்தின் உள்ளீட்டு வரைபடத்தின் ஒரு மர சிதைவை உருவாக்குகிறது அல்லது அதன் மூன்று அகலம் அதை விட அதிகமாக இருப்பதாக தெரிவிக்கிறது. அதே இயங்கும் நேரத்தில் இதை மேம்படுத்தியது. பிளானர் வரைபடங்களின் மூன்று அகலத்தை தீர்மானிப்பது NP-முழுமையானதா, அல்லது அவற்றின் மூன்று அகலத்தை பல்லுறுப்புக்கோவை நேரத்தில் கணக்கிட முடியுமா என்பது தெரியவில்லை. நடைமுறையில், 100 செங்குத்துகள் மற்றும் 11 வரை மூன்று அகலம் கொண்ட வரைபடங்களின் மூன்று அகலத்தை ஒரு வழிமுறை தீர்மானிக்க முடியும், உகந்த மூன்று அகலத்துடன் இந்த வரைபடங்களின் கார்டல் நிறைவைக் கண்டறியலாம். பெரிய வரைபடங்களுக்கு, கிளை மற்றும் பிணைக்கப்பட்ட தேடல் (பி. என். பி) மற்றும் சிறந்த-முதல் தேடல் போன்ற தேடல் அடிப்படையிலான நுட்பங்களைப் பயன்படுத்தி மூன்று அகலத்தைக் கணக்கிடலாம். இந்த வழிமுறைகள் எந்த நேரத்திலும் முன்கூட்டியே நிறுத்தப்படும்போது, அவை மூன்று அகலத்தில் மேல் வரம்பை வெளியிடும். மூன்று அகலத்தை கணக்கிடுவதற்கான முதல் பிஎன்பி வழிமுறை, குவிக்பிபி வழிமுறை என்று அழைக்கப்படுகிறது, இது கோகேட் மற்றும் டெக்டர் ஆகியோரால் முன்மொழியப்பட்டது. எந்தவொரு பி. என். பி வழிமுறையின் தரமும் பயன்படுத்தப்படும் குறைந்த வரம்பின் தரத்தை பெரிதும் சார்ந்திருப்பதால், கோகேட் மற்றும் டெக்ட்டர் ஆகியோர் சிறிய-குறைந்தபட்ச-அகலம் எனப்படும் மூன்று அகலத்தில் குறைந்த வரம்பைக் கணக்கிடுவதற்கான ஒரு புதிய வழிமுறையையும் முன்மொழிந்தனர். உயர் மட்டத்தில், சிறிய-குறைந்தபட்ச-அகல வழிமுறை ஒரு வரைபடத்தின் மூன்று அகலம் அதன் குறைந்தபட்ச டிகிரியை விட பெரியதாகவோ அல்லது மூன்று அகலத்தில் குறைந்த வரம்பை வழங்குவதற்கு சிறியதாகவோ இருக்காது என்ற உண்மைகளை ஒருங்கிணைக்கிறது. சிறிய-குறைந்தபட்ச-அகல வழிமுறை குறைந்தபட்ச டிகிரி உச்சிக்கும் அதன் அண்டை நாடுகளுக்கும் இடையில் ஒரு விளிம்பை சுருக்கி, ஒரு உச்சி மட்டுமே இருக்கும் வரை ஒரு சிறிய வரைபடத்தை மீண்டும் மீண்டும் உருவாக்குகிறது. இந்த கட்டமைக்கப்பட்ட மைனர்களுக்கு மேல் குறைந்தபட்ச டிகிரியின் அதிகபட்சம் வரைபடத்தின் மூன்று அகலத்தில் குறைந்த வரம்பாக இருக்கும் என்று உத்தரவாதம் அளிக்கப்படுகிறது. டவ் மற்றும் கோர்ஃப் சிறந்த-முதல் தேடலைப் பயன்படுத்தி குவிக்பிபி வழிமுறையை மேம்படுத்தினர். சில வரைபடங்களில், இந்த சிறந்த-முதல் தேடல் வழிமுறை குவிக் பிபியை விட வேகமான அளவின் வரிசையாகும். சிறிய மூன்று அகல வரைபடங்களில் உள்ள பிற சிக்கல்களைத் தீர்ப்பது 1970 களின் தொடக்கத்தில், வரைபடங்களில் வரையறுக்கப்பட்ட ஒரு பெரிய வகை ஒருங்கிணைந்த உகப்பாக்கம் சிக்கல்களை வரிசை அல்லாத மாறும் நிரலாக்கத்தால் திறம்பட தீர்க்க முடியும் என்று கண்டறியப்பட்டது, வரைபடம் ஒரு வரம்புக்குட்பட்ட பரிமாணத்தைக் கொண்டிருக்கும் வரை, ஒரு அளவுரு மூன்று அகலத்திற்கு சமமாக இருக்கும் என்று காட்டப்படுகிறது. பின்னர், 1980 களின் இறுதியில் பல எழுத்தாளர்கள் சுயாதீனமாக கவனித்தனர், தன்னிச்சையான வரைபடங்களுக்கு NP-முழுமையான பல வழிமுறை சிக்கல்கள் இந்த வரைபடங்களின் மர-சிதைவுகளைப் பயன்படுத்தி, வரம்புக்குட்பட்ட மூன்று அகல வரைபடங்களுக்கான மாறும் நிரலாக்கத்தின் மூலம் திறம்பட தீர்க்கப்படலாம். எடுத்துக்காட்டாக, ஒரு மரத்தின் சிதைவில் ஒரு மாறும் நிரலாக்க வழிமுறையைப் பயன்படுத்துவதன் மூலம் மூன்று அகலம் கொண்ட வரைபடத்திற்கு வண்ணம் பூசுவதில் உள்ள சிக்கலை தீர்க்க முடியும். மர சிதைவின் ஒவ்வொரு தொகுப்புக்கும், வண்ண வகுப்புகளாக செங்குத்துகளின் ஒவ்வொரு பகிர்வுக்கும், வழிமுறை அந்த நிறம் செல்லுபடியாகுமா என்பதை தீர்மானிக்கிறது மற்றும் மர சிதைவில் உள்ள அனைத்து வழித்தோன்றல் முனைகளுக்கும் நீட்டிக்கப்படலாம், கணக்கிடப்பட்ட மற்றும் சேமிக்கப்பட்ட ஒத்த வகையின் தகவல்களை இணைப்பதன் மூலம் அந்த முனைகளில். இதன் விளைவாக வரும் வழிமுறை காலப்போக்கில் ஒரு-வெர்டெக்ஸ் வரைபடத்தின் உகந்த நிறத்தைக் கண்டறிகிறது, இது ஒரு கால வரம்பாகும், இது இந்த சிக்கலை நிலையான-அளவுருவைக் கையாளக்கூடியதாக ஆக்குகிறது. கொர்செல்லின் தேற்றம் ஒரு பெரிய வகை சிக்கல்களுக்கு, நிலையான எல்லைக்குட்பட்ட மூன்று அகலத்துடன் ஒரு மரம்-சிதைவு வழங்கப்பட்டால் வகுப்பில் இருந்து ஒரு சிக்கலைத் தீர்க்க ஒரு நேரியல் நேர வழிமுறை உள்ளது. குறிப்பாக, மோனடிக் இரண்டாவது வரிசை தர்க்கத்தைப் பயன்படுத்தி வரைபடங்களின் தர்க்கத்தில் ஒரு வரைபட சிக்கலை வெளிப்படுத்த முடிந்தால், அதை வரம்புக்குட்பட்ட மூன்று அகலத்துடன் வரைபடங்களில் நேரியல் நேரத்தில் தீர்க்க முடியும் என்று கொர்செல்லின் தேற்றம் கூறுகிறது. மோனடிக் இரண்டாவது வரிசை தர்க்கம் என்பது பின்வரும் கட்டமைப்புகளைப் பயன்படுத்தும் வரைபட பண்புகளை விவரிக்கும் ஒரு மொழியாகும்ஃ உறுப்பினர் சோதனைகள் போன்ற தர்க்க செயல்பாடுகள், அதாவது செங்குத்துகள், விளிம்புகள், செங்குத்துகளின் தொகுப்புகள் மற்றும்/அல்லது விளிம்புகளின் தொகுப்புகள், அதாவது,,, அட்ஜசென்சி சோதனைகள் (ஒரு இறுதிப் புள்ளி), மற்றும் உகப்பாக்கம் போன்ற விஷயங்களை அனுமதிக்கும் சில நீட்டிப்புகள். எடுத்துக்காட்டாக, வரைபடங்களுக்கான 3-வண்ண சிக்கலைக் கவனியுங்கள். ஒரு வரைபடத்தைப் பொறுத்தவரை, இந்த சிக்கல் ஒவ்வொரு உச்சியையும் 3 வண்ணங்களில் ஒன்றை ஒதுக்க முடியுமா என்று கேட்கிறது, அதாவது இரண்டு அருகிலுள்ள செங்குத்துகள் ஒரே நிறத்தை ஒதுக்குவதில்லை. இந்த சிக்கலை மோனடிக் இரண்டாவது வரிசை தர்க்கத்தில் பின்வருமாறு வெளிப்படுத்தலாம்ஃ, இங்கு, 3 வண்ணங்களில் ஒவ்வொன்றையும் கொண்ட செங்குத்துகளின் துணைக்குழுக்களைக் குறிக்கிறது. எனவே, கொர்செல்லின் முடிவுகளால், வரையறுக்கப்பட்ட நிலையான மூன்று அகலத்தின் மரம்-சிதைவு கொடுக்கப்பட்ட வரைபடத்திற்கு 3-வண்ண சிக்கலை நேரியல் நேரத்தில் தீர்க்க முடியும். தொடர்புடைய அளவுருக்கள் பாதை அகலம் ஒரு வரைபடத்தின் பாதை அகலம் மர சிதைவுகள் வழியாக மூன்று அகலத்திற்கு மிகவும் ஒத்த வரையறையைக் கொண்டுள்ளது, ஆனால் மர சிதைவுகளுக்கு மட்டுப்படுத்தப்பட்டுள்ளது, இதில் சிதைவின் அடிப்படை மரம் ஒரு பாதை வரைபடமாகும். மாற்றாக, பாதை அகலத்தை இடைவெளி வரைபடங்களிலிருந்து கார்டல் வரைபடங்களிலிருந்து மூன்று அகலத்தின் வரையறைக்கு ஒத்ததாக வரையறுக்கலாம். இதன் விளைவாக, ஒரு வரைபடத்தின் பாதை அகலம் எப்போதும் அதன் மூன்று அகலத்தைப் போலவே பெரியதாக இருக்கும், ஆனால் அது ஒரு மடக்கைக் காரணியால் மட்டுமே பெரியதாக இருக்க முடியும். மற்றொரு அளவுருவான வரைபட அலைவரிசை, சரியான இடைவெளி வரைபடங்களிலிருந்து ஒத்த வரையறையைக் கொண்டுள்ளது, மேலும் குறைந்தபட்சம் பாதை அகலத்தைப் போலவே பெரியது. மற்ற தொடர்புடைய அளவுருக்களில் மரம்-ஆழம் அடங்கும், குடும்பம் ஒரு பாதையை விலக்கினால் மட்டுமே ஒரு சிறிய மூடிய வரைபட குடும்பத்திற்கு வரம்புக்குட்பட்ட ஒரு எண், மற்றும் சீரழிவு, ஒரு வரைபடத்தின் விரிந்த அளவீட்டின் அளவீடு அதன் மூன்று அகலத்திற்கு சமமாக இருக்கும். கட்டம் சிறிய அளவு ஒரு கட்டம் வரைபடத்தின் மூன்று அகலம் என்பதால், ஒரு வரைபடத்தின் மூன்று அகலம் எப்போதும் சிறிய சதுர கட்டத்தின் அளவை விட அதிகமாகவோ அல்லது சமமாகவோ இருக்கும். மறுபுறம், ராபர்ட்சன் மற்றும் சீமோர் ஆகியோரின் கிரிட் மைனர் தேற்றம் ஒரு வரம்பற்ற செயல்பாடு இருப்பதைக் காட்டுகிறது, அதாவது மிகப்பெரிய சதுர கிரிட் மைனர் குறைந்தபட்சம் மூன்று அகலம் இருக்கும் இடத்தில் அளவைக் கொண்டுள்ளது. அறியப்பட்ட சிறந்த வரம்புகள் குறைந்தபட்சம் சில நிலையான மாறிலிகளுக்கு இருக்க வேண்டும், மேலும் அதிகபட்சமாக கீழ் வரம்பில் உள்ள குறியீட்டிற்கு, பெரிய O குறியீட்டைப் பார்க்கவும். இறுக்கமான வரம்புகள் கட்டுப்படுத்தப்பட்ட வரைபடக் குடும்பங்களுக்கு அறியப்படுகின்றன, இது இரு பரிமாணக் கோட்பாட்டின் மூலம் அந்த குடும்பங்களில் பல வரைபட உகப்பாக்கம் சிக்கல்களுக்கு திறமையான வழிமுறைகளுக்கு வழிவகுக்கிறது. ஹாலினின் கிரிட் தேற்றம் எல்லையற்ற வரைபடங்களுக்கு மூன்று அகலத்திற்கும் கிரிட் சிறிய அளவிற்கும் இடையிலான உறவின் ஒப்புமையை வழங்குகிறது. விட்டம் மற்றும் உள்ளூர் மூன்று அகலம் துணை வரைபடங்களை எடுத்துக்கொள்வதன் கீழ் மூடப்பட்ட வரைபடங்களின் குடும்பம், குடும்பத்தில் உள்ள வரைபடங்களின் மூன்று அகலம் அவற்றின் விட்டத்தின் செயல்பாட்டால் மேல் வரம்புக்குட்பட்டிருந்தால், உள்ளூர் மூன்று அகலம் அல்லது விட்டம்-மூன்று அகல பண்பு வரம்புக்குட்பட்டதாகக் கூறப்படுகிறது. சிறார்களை எடுத்துக்கொள்வதன் கீழ் வகுப்பும் மூடப்பட்டதாகக் கருதப்பட்டால், தடைசெய்யப்பட்ட சிறார்களில் ஒருவர் உச்ச வரைபடமாக இருந்தால் மட்டுமே உள்ளூர் மூன்று அகலத்தை வரம்புக்குட்பட்டது. இந்த முடிவின் அசல் சான்றுகள், உச்ச-சிறிய-இல்லாத வரைபடக் குடும்பத்தில் மூன்று அகலம் விட்டத்தின் செயல்பாடாக இரு மடங்கு அதிவேகமாக வளர்கிறது என்பதைக் காட்டுகிறது; பின்னர் இது ஒற்றை அதிவேகமாகவும் இறுதியாக ஒரு நேரியல் வரம்பாகவும் குறைக்கப்பட்டது. எல்லைக்குட்பட்ட உள்ளூர் மூன்று அகலம் இரு பரிமாணத்தின் வழிமுறைக் கோட்பாட்டுடன் நெருக்கமாக தொடர்புடையது, மேலும் முதல் வரிசை தர்க்கத்தில் வரையறுக்கக்கூடிய ஒவ்வொரு வரைபட பண்பையும் ஒரு உச்ச-மைனர்-ஃப்ரீ கிராஃப் குடும்பத்திற்கு சற்று மேலோட்டமான நேரத்திற்குள் தீர்மானிக்க முடியும். சிறார்களின் கீழ் மூடப்படாத ஒரு வகை வரைபடங்கள் உள்ளூர் மூன்று அகலத்தை வரையறுக்க முடியும். குறிப்பாக இது எல்லைக்குட்பட்ட டிகிரி வரைபடங்களின் ஒரு வகுப்புக்கு அற்பமான உண்மை, ஏனெனில் எல்லைக்குட்பட்ட விட்டம் கொண்ட துணை வரைபடங்கள் எல்லைக்குட்பட்ட அளவைக் கொண்டுள்ளன. மற்றொரு உதாரணம் 1-பிளானர் வரைபடங்கள் மூலம் வழங்கப்படுகிறது, ஒரு விளிம்பிற்கு ஒரு குறுக்குவெட்டுடன் விமானத்தில் வரையக்கூடிய வரைபடங்கள், மேலும் பொதுவாக ஒரு விளிம்பிற்கு வரம்புக்குட்பட்ட எண்ணிக்கையிலான குறுக்குவெட்டுகளுடன் வரம்புக்குட்பட்ட இனத்தின் மேற்பரப்பில் வரையக்கூடிய வரைபடங்களுக்கு. வரையறுக்கப்பட்ட உள்ளூர் மூன்று அகலத்தின் சிறிய-மூடிய வரைபடக் குடும்பங்களைப் போலவே, இந்த பண்பு இந்த வரைபடங்களுக்கான திறமையான தோராய வழிமுறைகளுக்கு வழிவகுத்துள்ளது. ஹாட்விகர் எண் மற்றும் எஸ்-செயல்பாடுகள் அவர் அழைக்கும் வரைபட அளவுருக்களின் ஒரு வகுப்பை வரையறுக்கிறது-செயல்பாடுகள், இதில் மூன்று அகலமும் அடங்கும். வரைபடங்கள் முதல் முழு எண்கள் வரையிலான இந்த செயல்பாடுகள் விளிம்புகள் இல்லாத வரைபடங்களில் பூஜ்ஜியமாக இருக்க வேண்டும், சிறிய-மோனோடோனாக இருக்க வேண்டும் (ஒரு செயல்பாடு "சிறிய-மோனோடோன்" என்று குறிப்பிடப்படுகிறது, எப்போதெல்லாம் சிறியதாக இருந்தால், ஒருவர் இருந்தால்), முந்தைய அனைத்து செங்குத்துகளுக்கும் அருகில் ஒரு புதிய உச்சி சேர்க்கப்படும்போது ஒன்று அதிகரிக்க வேண்டும், மேலும் ஒரு கிளைக் பிரிப்பானின் இருபுறமும் உள்ள இரண்டு துணை வரைபடங்களிலிருந்து பெரிய மதிப்பை எடுக்க வேண்டும். அத்தகைய அனைத்து செயல்பாடுகளின் தொகுப்பும் உறுப்பு வாரியாக குறைத்தல் மற்றும் அதிகபட்சமாக்கல் செயல்பாடுகளின் கீழ் ஒரு முழுமையான ஜாலத்தை உருவாக்குகிறது. இந்த லட்டிஸில் உள்ள மேல் உறுப்பு மூன்று அகலம், மற்றும் கீழ் உறுப்பு ஹாட்விகர் எண், கொடுக்கப்பட்ட வரைபடத்தில் மிகப்பெரிய முழுமையான சிறிய அளவு. குறிப்புகள் குறிப்புகள். . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . வரைபட மாறிலிகள் வரைபட சிறு கோட்பாடு