Barnette's conjecture
பார்னெட்டின் அனுமானம் என்பது வரைபடக் கோட்பாட்டில் தீர்க்கப்படாத ஒரு சிக்கலாகும், இது கணிதத்தின் ஒரு கிளையாகும், இது வரைபடங்களில் உள்ள ஹாமில்டோனியன் சுழற்சிகளைப் பற்றியது. டேவிஸ், கலிபோர்னியா பல்கலைக்கழகத்தின் பேராசிரியரான டேவிட் டபிள்யூ. பார்னெட்டின் பெயரால் இது பெயரிடப்பட்டுள்ளது; ஒரு உச்சிக்கு மூன்று விளிம்புகளைக் கொண்ட ஒவ்வொரு இருதரப்பு பாலிஹெட்ரல் வரைபடமும் ஹாமில்டோனியன் சுழற்சியைக் கொண்டுள்ளது என்று அது கூறுகிறது. வரையறைகள் ஒரு சமதள வரைபடம் என்பது ஒரு திசைதிருப்பப்படாத வரைபடமாகும், இது யூக்ளிடியன் தளத்தில் எந்த குறுக்கீடுகளும் இல்லாமல் உட்பொதிக்கப்படலாம். ஒரு பிளானர் வரைபடம் 3-வெர்டெக்ஸ்-இணைக்கப்பட்டிருந்தால் மட்டுமே பாலிஹெட்ரல் என்று அழைக்கப்படுகிறது, அதாவது, இரண்டு செங்குத்துகள் இல்லையென்றால், அதை அகற்றுவது மீதமுள்ள வரைபடத்தை துண்டிக்கும். ஒவ்வொரு விளிம்பும் ஒவ்வொரு நிறத்தின் ஒரு இறுதிப் புள்ளியைக் கொண்டிருக்கும் வகையில் அதன் செங்குத்துகள் இரண்டு வெவ்வேறு வண்ணங்களால் வண்ணமயமாக்கப்படலாம் என்றால் ஒரு வரைபடம் இருதரப்பு ஆகும். ஒவ்வொரு முனையும் சரியாக மூன்று விளிம்புகளின் இறுதிப் புள்ளியாக இருந்தால் ஒரு வரைபடம் கனசதுரமாக (அல்லது 3-ஒழுங்காக) இருக்கும். இறுதியாக, ஒரு வரைபடம் அதன் ஒவ்வொரு செங்குத்துகளையும் சரியாக ஒரு முறை கடந்து செல்லும் ஒரு சுழற்சி இருந்தால் அது ஹாமில்டோனியன் ஆகும். பார்னெட்டின் அனுமானம் ஒவ்வொரு கன இருதரப்பு பாலிஹெட்ரல் வரைபடமும் ஹாமில்டோனியன் என்று கூறுகிறது. ஸ்டெய்னிட்ஸ் கோட்பாட்டின் படி, ஒரு சமதள வரைபடம் ஒரு குவிந்த பாலிஹெட்ரானின் விளிம்புகள் மற்றும் செங்குத்துகளை அது பாலிஹெட்ரலாக இருந்தால் மட்டுமே குறிக்கிறது. ஒரு முப்பரிமாண பாலிஹெட்ரான் ஒரு எளிய பாலிஹெட்ரானாக இருந்தால் மட்டுமே அது ஒரு கன வரைபடத்தைக் கொண்டிருக்கும். மேலும், வரைபடத்தின் பிளானர் உட்பொதிப்பில், அனைத்து முக சுழற்சிகளும் சம நீளத்தைக் கொண்டிருந்தால் மட்டுமே ஒரு பிளானர் வரைபடம் இருதரப்பு ஆகும். எனவே, பார்னெட்டின் அனுமானத்தை சமமான வடிவத்தில் கூறலாம்ஃ ஒரு முப்பரிமாண எளிய குவிந்த பாலிஹெட்ரான் அதன் ஒவ்வொரு முகத்திலும் சம எண்ணிக்கையிலான விளிம்புகளைக் கொண்டுள்ளது என்று வைத்துக்கொள்வோம். பின்னர், அனுமானத்தின்படி, பாலிஹெட்ரானின் வரைபடம் ஹாமில்டோனியன் சுழற்சியைக் கொண்டுள்ளது. ஒவ்வொரு கன பாலிஹெட்ரல் வரைபடமும் ஹாமில்டோனியன் என்று வரலாறு ஊகித்தது; இது டைட்டின் அனுமானம் என்று அறியப்பட்டது. 46 செங்குத்துகளுடன் ஒரு எதிர் உதாரணத்தை உருவாக்கியவர் இதை மறுத்தார்; மற்ற ஆராய்ச்சியாளர்கள் பின்னர் இன்னும் சிறிய எதிர் உதாரணங்களைக் கண்டறிந்தனர். இருப்பினும், இந்த அறியப்பட்ட எதிர் எடுத்துக்காட்டுகள் எதுவும் இருதரப்பு அல்ல. ஒவ்வொரு கனசதுர 3-இணைக்கப்பட்ட இருதரப்பு வரைபடமும் ஹாமில்டோனியன் என்று டூட்டே தானே ஊகித்தார், ஆனால் ஹார்டன் வரைபடம் என்ற எதிர் உதாரணத்தின் கண்டுபிடிப்பால் இது தவறானது என்று காட்டப்பட்டது. டைட் மற்றும் டூட்டின் அனுமானங்களின் பலவீனமான கலவையை முன்மொழிந்தார், ஒவ்வொரு இருதரப்பு கன பாலிஹெட்ரானும் ஹாமில்டோனியன் அல்லது அதற்கு சமமாக, டைட்டின் அனுமானத்திற்கு ஒவ்வொரு எதிர் உதாரணமும் இருதரப்பு அல்லாதது என்று கூறினார். சமமான வடிவங்கள் பார்னெட்டின் அனுமானம் ஒரு மேலோட்டமான வலுவான கூற்றுக்கு சமமானது என்பதைக் காட்டியது, இருதரப்பு கன பாலிஹெட்ரானின் ஒரே முகத்தில் உள்ள ஒவ்வொரு இரண்டு விளிம்புகளுக்கும் e மற்றும் f க்கு, e ஐக் கொண்ட ஒரு ஹாமில்டோனியன் சுழற்சி உள்ளது, ஆனால் f ஐக் கொண்டிருக்கவில்லை. தெளிவாக, இந்த கூற்று உண்மையாக இருந்தால், ஒவ்வொரு இருதரப்பு கன பாலிஹெட்ரானும் ஒரு ஹாமில்டோனியன் சுழற்சியைக் கொண்டுள்ளதுஃ e மற்றும் f ஐ தன்னிச்சையாகத் தேர்ந்தெடுக்கவும். மற்ற திசைகளில், கெல்மேன்ஸ் ஒரு எதிர் உதாரணத்தை அசல் பார்னெட் யூகத்திற்கு எதிர் எடுத்துக்காட்டாக மாற்ற முடியும் என்பதைக் காட்டினார். பார்னெட்டின் அனுமானம் ஒவ்வொரு கன இருதரப்பு பாலிஹெட்ரல் வரைபடத்தின் இரட்டை முனைகளின் செங்குத்துகளை இரண்டு துணைக்குழுக்களாகப் பிரிக்கலாம் என்ற கூற்றுக்கு சமமானது, அதன் தூண்டப்பட்ட துணை வரைபடங்கள் மரங்கள். இரட்டை வரைபடத்தில் அத்தகைய பகிர்வால் தூண்டப்பட்ட வெட்டு முதன்மை வரைபடத்தில் உள்ள ஹாமில்டோனியன் சுழற்சிக்கு ஒத்திருக்கிறது. பார்னெட்டின் அனுமானத்தின் உண்மை தெரியவில்லை என்றாலும், கணக்கீட்டு சோதனைகள் 86 க்கும் குறைவான செங்குத்துகளுடன் எதிர் உதாரணம் இல்லை என்பதைக் காட்டுகின்றன. பார்னெட்டின் அனுமானம் தவறானது என்று நிரூபிக்கப்பட்டால், இருதரப்பு கனசதுர பாலிஹெட்ரான் ஹாமில்டோனியன் என்பதை சோதிக்க அது NP-முழுமையானது என்று காட்டப்படலாம். ஒரு பிளானர் வரைபடம் இருதரப்பு மற்றும் கனசதுரமாக இருந்தாலும் இணைப்பு 2 மட்டுமே இருந்தால், அது ஹாமில்டோனியன் அல்லாததாக இருக்கலாம், மேலும் இந்த வரைபடங்களுக்கான ஹாமில்டோனிசிட்டியை சோதிப்பது NP-முழுமையானது. மற்றொரு முடிவு பின்வருமாறு பெறப்பட்டதுஃ இரட்டை வரைபடம் நீலம், சிவப்பு மற்றும் பச்சை நிறங்களுடன் உச்சி-நிறமாக இருக்க முடியும் என்றால், ஒவ்வொரு சிவப்பு-பச்சை சுழற்சியும் டிகிரி 4 இன் உச்சியைக் கொண்டிருக்கும், பின்னர் முதன்மை வரைபடம் ஹாமில்டோனியன் ஆகும். தொடர்புடைய சிக்கல்கள் பார்னெட்டின் தொடர்புடைய அனுமானம், அனைத்து முகங்களும் ஆறு அல்லது அதற்கும் குறைவான விளிம்புகளைக் கொண்ட ஒவ்வொரு கன பாலிஹெட்ரல் வரைபடமும் ஹாமில்டோனியன் என்று கூறுகிறது. ஒரு எதிர் உதாரணம் இருந்தால், அது 177 க்கும் மேற்பட்ட செங்குத்துகளைக் கொண்டிருக்க வேண்டும் என்று கணக்கீட்டு சோதனைகள் காட்டுகின்றன. இந்த அனுமானம் நிரூபிக்கப்பட்டது. இந்த இரண்டு அனுமானங்களின் குறுக்குவெட்டு என்னவென்றால், அனைத்து முகங்களும் நான்கு அல்லது ஆறு விளிம்புகளைக் கொண்ட ஒவ்வொரு இருதரப்பு கன பாலிஹெட்ரல் வரைபடமும் ஹாமில்டோனியன் ஆகும். இது உண்மை என்று நிரூபிக்கப்பட்டது. குறிப்புகள் குறிப்புகள்; அறிவியல் ஆவணங்களில் மறுபதிப்பு செய்யப்பட்டது, தொகுதி. II, pp. 85-98 வெளிப்புற இணைப்புகள் திறந்த சிக்கல் தோட்டத்தில் பார்னெட்டின் அனுமானம், ராபர்ட் சமல், 2007. வரைபடக் கோட்பாட்டில் தீர்க்கப்படாத சிக்கல்கள் பிளானர் வரைபடங்கள் ஹாமில்டோனிய பாதைகள் மற்றும் சுழற்சிகள்