Hajós construction
வரைபடக் கோட்பாட்டில், கணிதத்தின் ஒரு கிளை, ஹாஜோஸ் கட்டுமானம் என்பது பெயரிடப்பட்ட வரைபடங்களில் ஒரு செயல்பாடாகும், அதன் பெயரால் எந்தவொரு முக்கியமான வரைபடத்தையும் அல்லது எந்தவொரு வரைபடத்தையும் உருவாக்க பயன்படுத்தப்படலாம், அதன் நிற எண் குறைந்தபட்சம் சில வரம்பாக இருக்கும். கட்டுமானம் இரண்டு திசைதிருப்பப்படாத வரைபடங்களாக இருக்கட்டும், ஒரு விளிம்பாக இருக்கவும், ஒரு விளிம்பாக இருக்கவும். பின்னர் ஹாஜோஸ் கட்டுமானம் ஒரு புதிய வரைபடத்தை உருவாக்குகிறது, இது இரண்டு வரைபடங்களையும் இணைத்து செங்குத்துகளையும் ஒற்றை முனையிலும் அடையாளம் கண்டு, இரண்டு விளிம்புகளையும் அகற்றி, ஒரு புதிய விளிம்பைச் சேர்க்கிறது. எடுத்துக்காட்டாக, ஒவ்வொன்றும் நான்கு செங்குத்துகளில் ஒரு முழுமையான வரைபடமாக இருக்கட்டும்; இந்த வரைபடங்களின் சமச்சீர் காரணமாக, அவை ஒவ்வொன்றிலிருந்தும் எந்த விளிம்பைத் தேர்ந்தெடுப்பது என்பது முக்கியமல்ல. இந்த வழக்கில், ஹாஜோஸ் கட்டுமானத்தைப் பயன்படுத்துவதன் விளைவாக மோசர் சுழல், ஏழு-வெர்டெக்ஸ் அலகு தூர வரைபடம் நான்கு வண்ணங்கள் தேவைப்படுகிறது. மற்றொரு எடுத்துக்காட்டாக, நீளம் மற்றும் முறையே சுழற்சி வரைபடங்களாக இருந்தால், ஹாஜோஸ் கட்டுமானத்தைப் பயன்படுத்துவதன் விளைவாக நீளத்தின் சுழற்சி வரைபடம் இருக்கும். கட்டமைக்கக்கூடிய வரைபடங்கள் ஒரு வரைபடம் பின்வரும் மூன்று வழிகளில் ஒன்றில் உருவாகும்போது-கட்டமைக்கக்கூடியது (அல்லது ஹாஜோஸ்-கட்டமைக்கக்கூடியது) என்று கூறப்படுகிறதுஃ முழுமையான வரைபடம்-கட்டமைக்கக்கூடியது. ஏதேனும் இரண்டு கட்டமைக்கக்கூடிய வரைபடங்களாக இருக்கட்டும். பின்னர் ஹாஜோஸ் கட்டுமானத்தைப் பயன்படுத்துவதன் மூலம் உருவாக்கப்பட்ட வரைபடம்-கட்டமைக்கக்கூடியது. எந்தவொரு கட்டமைக்கக்கூடிய வரைபடமாகவும் இருக்கட்டும், மேலும் ஏதேனும் இரண்டு இணைக்கப்படாத செங்குத்துகளாக இருக்கட்டும். பின்னர் இணைப்பதன் மூலமும் ஒற்றை உச்சியில் உருவாக்கப்படுவதன் மூலமும் உருவாக்கப்பட்ட வரைபடமும்-கட்டமைக்கக்கூடியது. சமமாக, இந்த வரைபடம் வரைபடத்தில் விளிம்பைச் சேர்ப்பதன் மூலமும் பின்னர் சுருங்குவதன் மூலமும் உருவாகலாம். ஒவ்வொரு கட்டமைக்கக்கூடிய வரைபடத்திற்கும் எந்தவொரு சரியான வரைபட வண்ணத்திலும் குறைந்தபட்சம் வண்ணங்கள் தேவை என்பதை சரிபார்க்க எளிதானது. உண்மையில், இது முழுமையான வரைபடத்திற்கு தெளிவாக உள்ளது, மேலும் இரண்டு இணைக்கப்படாத செங்குத்துகளை அடையாளம் காண்பதன் விளைவு எந்த நிறத்திலும் ஒருவருக்கொருவர் ஒரே நிறத்தைக் கொண்டிருக்கும்படி கட்டாயப்படுத்துவதாகும், இது வண்ணங்களின் எண்ணிக்கையைக் குறைக்காது. ஹாஜோஸ் கட்டுமானத்திலேயே, புதிய விளிம்பு இரண்டு செங்குத்துகளில் குறைந்தபட்சம் ஒன்றையாவது கட்டாயப்படுத்துகிறது மற்றும் ஒருங்கிணைந்த உச்சியை விட வேறுபட்ட நிறத்தைக் கொண்டுள்ளது, எனவே ஒருங்கிணைந்த வரைபடத்தின் எந்தவொரு சரியான நிறமும் அது உருவாக்கப்பட்ட இரண்டு சிறிய வரைபடங்களில் ஒன்றின் சரியான நிறத்திற்கு வழிவகுக்கிறது, இதனால் மீண்டும் வண்ணங்கள் தேவைப்படுகின்றன. ஒரு வரைபடத்திற்கு குறைந்தபட்சம் வண்ணங்கள் தேவை என்பதை ஹாஜோஸ் இன்னும் வலுவாக நிரூபித்தார், எந்தவொரு சரியான நிறத்திலும், அது ஒரு துணை வரைபடமாக கட்டமைக்கக்கூடிய வரைபடத்தைக் கொண்டிருந்தால் மட்டுமே. சமமாக, ஒவ்வொரு முக்கியமான வரைபடமும் (வண்ணங்கள் தேவைப்படும் ஆனால் ஒவ்வொரு சரியான துணை வரைபடத்திற்கும் குறைவான வண்ணங்கள் தேவைப்படும் ஒரு வரைபடம்)-கட்டமைக்கக்கூடியது. மாற்றாக, வண்ணங்கள் தேவைப்படும் ஒவ்வொரு வரைபடமும் ஹாஜோஸ் கட்டுமானத்தை இணைப்பதன் மூலமும், ஏதேனும் இரண்டு அருகிலுள்ள செங்குத்துகளை அடையாளம் காணும் செயல்பாடு மற்றும் கொடுக்கப்பட்ட வரைபடத்தில் ஒரு உச்சி அல்லது விளிம்பைச் சேர்க்கும் செயல்பாடுகள், முழுமையான வரைபடத்திலிருந்து தொடங்கி உருவாக்கப்படலாம். வண்ணமயமாக்கலுக்கு பதிலாக பட்டியல் வண்ணமயமாக்கலுக்கு இதேபோன்ற கட்டுமானம் பயன்படுத்தப்படலாம். முக்கியமான வரைபடங்களின் கட்டமைப்பாற்றல் ஏனெனில், ஒவ்வொரு முக்கியமான வரைபடத்தையும் (அதாவது, ஒவ்வொரு ஒற்றைப்படை சுழற்சியும்) அதன் கட்டமைப்பில் உருவாக்கப்பட்ட அனைத்து வரைபடங்களும் முக்கியமானதாக இருக்கும் வகையில் கட்டமைக்கக்கூடிய வரைபடமாக உருவாக்க முடியும். ஏனெனில், இது உண்மையல்லஃ-நிற வரைபடங்கள் ஒரு உட்பிரிவைக் கொண்டுள்ளன என்ற ஹாஜோஸின் அனுமானத்திற்கு ஒரு எதிர் எடுத்துக்காட்டாக காணப்படும் ஒரு வரைபடம், இந்த சிக்கலுக்கு ஒரு எதிர் எடுத்துக்காட்டாகவும் செயல்படுகிறது. அதைத் தொடர்ந்து,-முக்கியமான ஆனால்-கட்டமைக்க முடியாத வரைபடங்கள்-முக்கியமான வரைபடங்கள் மூலம் மட்டுமே அனைவருக்கும் காணப்பட்டன. ஒவ்வொரு ஜோடி ஆன்டிபோடல் செங்குத்துகளுக்கும் இடையில் ஒரு புதிய விளிம்பைச் சேர்ப்பதன் மூலம் டோடெகாஹெட்ரான் வரைபடத்திலிருந்து பெறப்பட்ட வரைபடம் அத்தகைய ஒரு எடுத்துக்காட்டு ஹாஜோஸ் எண் ஏனெனில் இரண்டு இணைக்கப்படாத செங்குத்துகளை இணைப்பது விளைவாக வரும் வரைபடத்தில் செங்குத்துகளின் எண்ணிக்கையைக் குறைக்கிறது, ஹாஜோஸால் வரையறுக்கப்பட்ட செயல்பாடுகளைப் பயன்படுத்தி கொடுக்கப்பட்ட வரைபடத்தைக் குறிக்கத் தேவையான செயல்பாடுகளின் எண்ணிக்கை செங்குத்துகளின் எண்ணிக்கையை விட அதிகமாக இருக்கலாம். மேலும் குறிப்பாக, ஒரு-நிற வரைபடத்தின் ஹாஜோஸ் எண்ணை கட்டமைக்கத் தேவையான குறைந்தபட்ச படிகளின் எண்ணிக்கையாக வரையறுக்கவும், அங்கு ஒவ்வொரு படியும் முன்பு உருவாக்கப்பட்ட இரண்டு வரைபடங்களை இணைப்பதன் மூலம் ஒரு புதிய வரைபடத்தை உருவாக்குகிறது, முன்பு உருவாக்கப்பட்ட வரைபடத்தின் இரண்டு இணைக்கப்படாத செங்குத்துகளை இணைக்கிறது அல்லது முன்பு உருவாக்கப்பட்ட வரைபடத்தில் ஒரு உச்சி அல்லது விளிம்பைச் சேர்க்கிறது. விளிம்புகளைக் கொண்ட-வெர்டெக்ஸ் வரைபடத்திற்கு, அவர்கள் அதைக் காட்டினர். ஒவ்வொரு வரைபடமும் ஒரு பல்லுறுப்புக்கோவை ஹாஜோஸ் எண்ணைக் கொண்டிருந்தால், இது நிர்ணயிக்கப்படாத பல்லுறுப்புக்கோவை நேரத்தில் நிறமற்ற தன்மையை நிரூபிக்க முடியும் என்பதைக் குறிக்கும், எனவே சிக்கலான கோட்பாட்டாளர்களால் சாத்தியமில்லை என்று கருதப்படும் முடிவு NP = இணை-NP என்பதைக் குறிக்கிறது. இருப்பினும், சில சிக்கலான-கோட்பாட்டு அனுமானங்களைச் செய்யாமல் ஹாஜோஸ் எண்ணில் பல்லுறுப்புக்கோவை அல்லாத கீழ் வரம்புகளை எவ்வாறு நிரூபிப்பது என்பது தெரியவில்லை, அத்தகைய வரம்பை நிரூபிக்க முடிந்தால், அது கணித தர்க்கத்தில் சில வகையான ஃப்ரீஜ் அமைப்பில் பல்லுறுப்புக்கோவை அல்லாத வரம்புகள் இருப்பதைக் குறிக்கும். கொடுக்கப்பட்ட வரைபடத்திற்கான ஹஜோஸ் கட்டுமானத்தை விவரிக்கும் ஒரு வெளிப்பாடு மரத்தின் குறைந்தபட்ச அளவு ஹஜோஸ் எண்ணிக்கையை விட கணிசமாக பெரியதாக இருக்கலாம், ஏனென்றால் ஒரு குறுகிய வெளிப்பாடு ஒரே வரைபடங்களை பல முறை மீண்டும் பயன்படுத்தலாம், இது ஒரு வெளிப்பாடு மரத்தில் அனுமதிக்கப்படாத பொருளாதாரம். 3-வண்ண வரைபடங்கள் உள்ளன, அவற்றுக்கான மிகச்சிறிய வெளிப்பாடு மரம் அதிவேக அளவைக் கொண்டுள்ளது. மற்ற பயன்பாடுகள் ஹாஜோஸ் கட்டுமானத்தைப் பயன்படுத்தி 4-முக்கியமான பன்முக வரைபடங்களின் எல்லையற்ற தொகுப்பை உருவாக்கின, ஒவ்வொன்றும் செங்குத்துகளை விட இரண்டு மடங்கு அதிகமான விளிம்புகளைக் கொண்டுள்ளன. இதேபோல், கிரோட்ஷ் வரைபடத்தில் தொடங்கி, பல 4-முக்கியமான முக்கோண-இல்லாத வரைபடங்களை உருவாக்க கட்டுமானத்தைப் பயன்படுத்தினர், அவை பாரம்பரிய பின்தொடர்தல் வழிமுறைகளைப் பயன்படுத்தி வண்ணமயமாக்க கடினமாக இருப்பதைக் காட்டின. பாலிஹெட்ரல் காம்பினடோரிக்கில், நிலையான செட் பாலிடோப்பின் அம்சங்களை உருவாக்க ஹாஜோஸ் கட்டுமானத்தைப் பயன்படுத்தினார். குறிப்புகள் குறிப்புகள். . . . . மேற்கோள் காட்டியபடி. . . . . . . . . வரைபட செயல்பாடுகள் வரைபட வண்ணம்