Halin graph
வரைபடக் கோட்பாட்டில், ஹாலின் வரைபடம் என்பது ஒரு மரத்தின் இலைகளை ஒரு சுழற்சியில் இணைப்பதன் மூலம் கட்டப்பட்ட ஒரு வகை சமதள வரைபடமாகும். மரத்திற்கு குறைந்தது நான்கு செங்குத்துகள் இருக்க வேண்டும், அவற்றில் எதுவுமே சரியாக இரண்டு அண்டை நாடுகளைக் கொண்டிருக்கக்கூடாது; அது விமானத்தில் வரையப்பட வேண்டும், எனவே அதன் விளிம்புகள் எதுவும் கடக்காது (இது ஒரு பிளானர் உட்பொதிப்பு என்று அழைக்கப்படுகிறது), மேலும் சுழற்சி இந்த உட்பொதிப்பில் அவற்றின் கடிகார வரிசையில் இலைகளை இணைக்கிறது. இவ்வாறு, சுழற்சி ஹாலின் வரைபடத்தின் வெளிப்புற முகத்தை உருவாக்குகிறது, அதன் உள்ளே மரம் உள்ளது. 1971 ஆம் ஆண்டில் அவற்றை ஆய்வு செய்த ஜெர்மன் கணிதவியலாளர் ருடால்ப் ஹாலின் பெயரால் ஹாலின் வரைபடங்கள் பெயரிடப்பட்டுள்ளன. கனசதுர ஹாலின் வரைபடங்கள்-ஒவ்வொரு உச்சியும் சரியாக மூன்று விளிம்புகளைத் தொடும் வரைபடங்கள்-ஏற்கனவே ஒரு நூற்றாண்டுக்கு முன்னர் கிர்க்மேனால் ஆய்வு செய்யப்பட்டன. ஹாலின் வரைபடங்கள் பாலிஹெட்ரல் வரைபடங்கள், அதாவது ஒவ்வொரு ஹாலின் வரைபடமும் ஒரு குவிந்த பாலிஹெட்ரானின் செங்குத்துகள் மற்றும் விளிம்புகளை உருவாக்க பயன்படுத்தப்படலாம், மேலும் அவற்றிலிருந்து உருவாகும் பாலிஹெட்ரா கூரை இல்லாத பாலிஹெட்ரா அல்லது குவிமாடங்கள் என்று அழைக்கப்படுகின்றன. ஒவ்வொரு ஹாலின் வரைபடமும் அதன் அனைத்து செங்குத்துகளிலும் ஒரு ஹாமில்டோனியன் சுழற்சியைக் கொண்டுள்ளது, அதே போல் வரைபடத்தின் செங்குத்துகளின் எண்ணிக்கை வரை கிட்டத்தட்ட அனைத்து நீளங்களின் சுழற்சிகளும் உள்ளன. ஹாலின் வரைபடங்களை நேரியல் நேரத்தில் அடையாளம் காணலாம். ஹாலின் வரைபடங்கள் குறைந்த மூன்று அகலத்தைக் கொண்டிருப்பதால், ஹாமில்டோனியன் சுழற்சிகளைக் கண்டுபிடிப்பது போன்ற பிற வகையான பிளானர் வரைபடங்களில் கடினமாக இருக்கும் பல கணக்கீட்டு சிக்கல்களை ஹாலின் வரைபடங்களில் விரைவாக தீர்க்க முடியும். எடுத்துக்காட்டுகள் ஒரு நட்சத்திரம் என்பது சரியாக ஒரு உள் உச்சியைக் கொண்ட ஒரு மரம். ஒரு நட்சத்திரத்தில் ஹாலின் வரைபட கட்டமைப்பைப் பயன்படுத்துவது ஒரு சக்கர வரைபடத்தை உருவாக்குகிறது, இது ஒரு பிரமிடின் (விளிம்புகளின்) வரைபடமாகும். முக்கோண முக்கோணத்தின் வரைபடமும் ஒரு ஹாலின் வரைபடமாகும்ஃ அதன் செவ்வக முகங்களில் ஒன்று வெளிப்புற சுழற்சியாக இருக்கும் வகையில் அதை வரையலாம், மீதமுள்ள விளிம்புகள் நான்கு இலைகள், இரண்டு உட்புற செங்குத்துகள் மற்றும் ஐந்து விளிம்புகளைக் கொண்ட ஒரு மரத்தை உருவாக்குகின்றன. ஃப்ரூக்ட் வரைபடம், அற்பமான வரைபட தானியங்கிகள் இல்லாத ஐந்து மிகச்சிறிய கன வரைபடங்களில் ஒன்றாகும், இது ஒரு ஹாலின் வரைபடமாகும். பண்புகள் ஒவ்வொரு ஹாலின் வரைபடமும் 3-இணைக்கப்பட்டுள்ளது, அதாவது அதிலிருந்து இரண்டு செங்குத்துகளை நீக்கி மீதமுள்ள செங்குத்துகளை துண்டிக்க முடியாது. இது விளிம்பு-குறைந்தபட்சம் 3-இணைக்கப்பட்டுள்ளது, அதாவது அதன் விளிம்புகளில் ஏதேனும் ஒன்று அகற்றப்பட்டால், மீதமுள்ள வரைபடம் இனி 3-இணைக்கப்படாது. ஸ்டெய்னிட்ஸ் கோட்பாட்டின் படி, 3-இணைக்கப்பட்ட சமதள வரைபடமாக, இது ஒரு குவிந்த பாலிஹெட்ரானின் செங்குத்துகள் மற்றும் விளிம்புகளின் தொகுப்பாக குறிப்பிடப்படலாம்; அதாவது, இது ஒரு பாலிஹெட்ரல் வரைபடமாகும். வரைபடத்தை உணரும் பாலிஹெட்ரானை தேர்வு செய்யலாம், இதனால் மரத்தின் அனைத்து இலைகளையும் கொண்ட முகம் கிடைமட்டமாக இருக்கும், மற்ற அனைத்து முகங்களும் அதற்கு மேலே சமமான சரிவுகளுடன் இருக்கும். ஒவ்வொரு பாலிஹெட்ரல் வரைபடத்தையும் போலவே, ஹாலின் வரைபடங்களும் ஒரு தனித்துவமான பிளானர் உட்பொதிப்பைக் கொண்டுள்ளன, அதன் முகங்களில் எது வெளிப்புற முகமாக இருக்க வேண்டும் என்பதைத் தேர்ந்தெடுக்கும் வரை. ஒவ்வொரு ஹாலின் வரைபடமும் ஹாமில்டோனியன் வரைபடமாகும், மேலும் வரைபடத்தின் ஒவ்வொரு விளிம்பும் ஹாமில்டோனியன் சுழற்சியைச் சேர்ந்தது. மேலும், எந்தவொரு ஹாலின் வரைபடமும் எந்தவொரு உச்சியையும் நீக்கிய பிறகு ஹாமில்டோனியனாகவே உள்ளது. டிகிரி 2 செங்குத்துகள் இல்லாத ஒவ்வொரு மரமும் ஒரே பெற்றோரைப் பகிர்ந்து கொள்ளும் இரண்டு இலைகளைக் கொண்டிருப்பதால், ஒவ்வொரு ஹாலின் வரைபடமும் ஒரு முக்கோணத்தைக் கொண்டுள்ளது. குறிப்பாக, ஒரு ஹாலின் வரைபடம் முக்கோணம் இல்லாத வரைபடமாகவோ அல்லது இருதரப்பு வரைபடமாகவோ இருக்க முடியாது. மேலும் வலுவாக, ஒவ்வொரு ஹாலின் வரைபடமும் கிட்டத்தட்ட பான்சிக்ளிக் ஆகும், அதாவது இது 3 முதல் n வரையிலான அனைத்து நீளங்களின் சுழற்சிகளையும் கொண்டுள்ளது, ஒற்றை சம நீளத்தைத் தவிர. மேலும், ஒரு விளிம்பு சுருங்கினால் எந்த ஹாலின் வரைபடமும் கிட்டத்தட்ட பான்சிக்ளிக் ஆக இருக்கும், மேலும் டிகிரி மூன்று உட்புற செங்குத்துகள் இல்லாத ஒவ்வொரு ஹாலின் வரைபடமும் பான்சிக்ளிக் ஆகும். அதிகபட்ச டிகிரி நான்கை விட அதிகமாக உள்ள ஹாலின் வரைபடத்தின் நிகழ்வு நிற எண். இது அனைத்து ஜோடிகளையும் (v, e) வண்ணமயமாக்குவதற்குத் தேவையான வண்ணங்களின் எண்ணிக்கையாகும், இதில் v என்பது வரைபடத்தின் ஒரு உச்சியாகும், மேலும் e என்பது v க்கு ஒரு விளிம்பு சம்பவமாகும், இது வண்ணமயமாக்கலில் சில கட்டுப்பாடுகளுக்குக் கீழ்ப்படிகிறது. ஒரு உச்சியைப் பகிர்ந்து கொள்ளும் அல்லது ஒரு விளிம்பைப் பகிர்ந்து கொள்ளும் ஜோடிகள் ஒரே நிறத்தைக் கொண்டிருக்க அனுமதிக்கப்படுவதில்லை. கூடுதலாக, ஒரு ஜோடி (v, e) e இன் மற்ற இறுதிப் புள்ளியைப் பயன்படுத்தும் மற்றொரு ஜோடியின் அதே நிறத்தைக் கொண்டிருக்க முடியாது. அல்லது உடன் உள்ள ஹாலின் வரைபடங்களுக்கு, நிகழ்வு நிற எண் முறையே அல்லது பெரியதாக இருக்கலாம். கணக்கீட்டு சிக்கலானது கொடுக்கப்பட்ட-வெர்டெக்ஸ் வரைபடம் நேரியல் நேரத்தில் ஒரு ஹாலின் வரைபடமா என்பதைச் சோதிக்கலாம், வரைபடத்தின் ஒரு பிளானர் உட்பொதிப்பைக் கண்டறிந்து (ஒன்று இருந்தால்), பின்னர் குறைந்தபட்சம் செங்குத்துகளைக் கொண்ட ஒரு முகம் இருக்கிறதா என்று சோதிப்பதன் மூலம், அனைத்தும் டிகிரி மூன்று. அப்படியானால், அதிகபட்சம் நான்கு முகங்கள் இருக்கலாம், மேலும் அவை ஒவ்வொன்றிற்கும் நேரியல் நேரத்தில் சரிபார்க்க முடியும், மீதமுள்ள வரைபடம் இந்த முகத்தின் செங்குத்துகளை அதன் இலைகளாக கொண்டு ஒரு மரத்தை உருவாக்குகிறதா என்பதை சரிபார்க்க முடியும். மறுபுறம், அத்தகைய முகம் இல்லையென்றால், வரைபடம் ஹாலின் அல்ல. மாற்றாக, செங்குத்துகள் மற்றும் விளிம்புகளைக் கொண்ட ஒரு வரைபடம் சமதளமாகவும், 3-இணைக்கப்பட்டதாகவும், செங்குத்துகளின் எண்ணிக்கை வரைபடத்தின் சுற்று தரவரிசைக்கு சமமான முகத்தைக் கொண்டிருந்தால் மட்டுமே ஹாலின் ஆகும், இவை அனைத்தையும் நேரியல் நேரத்தில் சரிபார்க்க முடியும். நேரியல் நேரத்தில் ஹாலின் வரைபடங்களை அங்கீகரிப்பதற்கான பிற முறைகளில் கோர்செல்லின் தேற்றத்தின் பயன்பாடு அல்லது வரைபடத்தை மீண்டும் எழுதுவதை அடிப்படையாகக் கொண்ட ஒரு முறை ஆகியவை அடங்கும், இவை இரண்டும் வரைபடத்தின் பிளானர் உட்பொதிப்பை அறிந்து கொள்வதை நம்பியிருக்கவில்லை. ஒவ்வொரு ஹாலின் வரைபடமும் மூன்று அகலம் = 3 ஐக் கொண்டுள்ளது. எனவே, தன்னிச்சையான பிளானர் வரைபடங்களுக்கு NP-முழுமையான பல வரைபட உகப்பாக்கம் சிக்கல்கள், அதிகபட்ச சுயாதீன தொகுப்பைக் கண்டுபிடிப்பது போன்றவை, டைனமிக் புரோகிராமிங் அல்லது கோர்செல்லின் தேற்றத்தைப் பயன்படுத்தி ஹாலின் வரைபடங்களில் நேரியல் நேரத்தில் தீர்க்கப்படலாம், அல்லது சில சந்தர்ப்பங்களில் (ஹாமில்டோனியன் சுழற்சிகளின் கட்டுமானம் போன்றவை) நேரடி வழிமுறைகள் மூலம். இருப்பினும், கொடுக்கப்பட்ட வரைபடத்தின் மிகப்பெரிய ஹாலின் துணை வரைபடத்தைக் கண்டுபிடிப்பது, கொடுக்கப்பட்ட வரைபடத்தின் அனைத்து செங்குத்துகளையும் உள்ளடக்கிய ஒரு ஹாலின் துணை வரைபடம் உள்ளதா என்பதைச் சோதிப்பது அல்லது கொடுக்கப்பட்ட வரைபடம் ஒரு பெரிய ஹாலின் வரைபடத்தின் துணை வரைபடமா என்பதைச் சோதிப்பது NP-முழுமையானது. 1971 ஆம் ஆண்டில், ஹாலின் குறைந்தபட்ச 3-வெர்டெக்ஸ்-இணைக்கப்பட்ட வரைபடங்களின் ஒரு வகுப்பாக ஹாலின் வரைபடங்களை அறிமுகப்படுத்தினார்ஃ வரைபடத்தில் உள்ள ஒவ்வொரு விளிம்பிற்கும், அந்த விளிம்பை அகற்றுவது வரைபடத்தின் இணைப்பைக் குறைக்கிறது. தன்னிச்சையான பிளானர் வரைபடங்களுக்கு கணக்கீட்டு ரீதியாக சாத்தியமற்ற பல வழிமுறை சிக்கல்களை அவற்றில் திறம்பட தீர்க்க முடியும் என்ற கண்டுபிடிப்புடன் இந்த வரைபடங்கள் முக்கியத்துவம் பெற்றன. இந்த உண்மை பின்னர் அவற்றின் குறைந்த மூன்று அகலத்தின் விளைவாகவும், குறைந்த மூன்று அகலத்தின் எந்த வரைபடத்திலும் இந்த சிக்கல்களுக்கு திறமையான தீர்வுகளை வழங்கும் கோர்செல்லின் தேற்றம் போன்ற வழிமுறை மெட்டா-கோட்பாடுகளின் விளைவாகவும் விளக்கப்பட்டது. இந்த வரைபடங்களில் ஹாலினின் பணிக்கு முன்னர், கனசதுர (அல்லது 3-வழக்கமான) ஹாலின் வரைபடங்கள் தொடர்பான வரைபட கணக்கீட்டு சிக்கல்கள் 1856 ஆம் ஆண்டில் தாமஸ் கிர்க்மேன் மற்றும் 1965 ஆம் ஆண்டில் ஹான்ஸ் ராடெமாச்சர் ஆகியோரால் ஆய்வு செய்யப்பட்டன. ரேடேமாச்சர் இந்த வரைபடங்களை அடிப்படையிலான பாலிஹெட்ரா என்று அழைக்கிறார். முகங்களில் ஒன்று பக்கங்களைக் கொண்ட முகங்களைக் கொண்ட கனசதுர பன்முக வரைபடங்கள் என்று அவர் அவற்றை வரையறுக்கிறார். இந்த வரையறைக்கு பொருந்தக்கூடிய வரைபடங்கள் சரியாக கனசதுர ஹாலின் வரைபடங்களாகும். ஹாலின் வரைபடங்கள் மற்றும் 4-வெர்டெக்ஸ்-இணைக்கப்பட்ட பிளானர் வரைபடங்கள் இரண்டும் ஹாமில்டோனியன் சுழற்சிகளைக் கொண்டுள்ளன என்ற உண்மையால் ஈர்க்கப்பட்டன, ஒவ்வொரு 4-வெர்டெக்ஸ்-இணைக்கப்பட்ட பிளானர் வரைபடமும் ஒரு பரவலான ஹாலின் துணை வரைபடத்தைக் கொண்டுள்ளது என்று ஊகிக்கப்படுகிறது; இங்கே "ஸ்பானிங்" என்றால் துணை வரைபடம் பெரிய வரைபடத்தின் அனைத்து உச்சிகளையும் உள்ளடக்கியது. லோவாஸ்-பிளம்மர் அனுமானம் 2015 வரை திறந்திருந்தது, அப்போது எண்ணற்ற பல எதிர் உதாரணங்களுக்கான கட்டுமானம் வெளியிடப்பட்டது. ஹாலின் வரைபடங்கள் சில நேரங்களில் சறுக்கிய மரங்கள் அல்லது கூரை இல்லாத பாலிஹெட்ரா என்றும் அழைக்கப்படுகின்றன. இருப்பினும், இந்த பெயர்கள் தெளிவற்றவை. சில எழுத்தாளர்கள் மரங்களின் இலைகளை ஒரு சுழற்சியில் இணைப்பதன் மூலம் மரங்களிலிருந்து உருவாக்கப்பட்ட சமதள வரைபடங்களைக் குறிக்க "சறுக்கிய மரங்கள்" என்ற பெயரைப் பயன்படுத்துகின்றனர், ஆனால் மரத்தின் உள் செங்குத்துகள் மூன்று அல்லது அதற்கு மேற்பட்ட டிகிரியைக் கொண்டிருக்க வேண்டிய அவசியமில்லை. "அடிப்படையிலான பாலிஹெட்ராவைப்" போலவே, "கூரை இல்லாத பாலிஹெட்ரா" என்ற பெயரும் கனசதுர ஹாலின் வரைபடங்களைக் குறிக்கலாம். ஹாலின் வரைபடங்களைக் கொண்ட குவிந்த பாலிஹெட்ராக்கள் குவிமாடங்கள் என்றும் அழைக்கப்படுகின்றன. குறிப்புகள் வெளிப்புற இணைப்புகள் ஹாலின் வரைபடங்கள், வரைபட வகுப்பு உள்ளடக்கங்கள் குறித்த தகவல் அமைப்பு. வரைபட குடும்பங்கள் பிளானர் வரைபடங்கள்