Tutte theorem
வரைபடக் கோட்பாட்டின் கணிதத் துறையில், வில்லியம் தாமஸ் டுட்டேவின் பெயரால் பெயரிடப்பட்ட டுட்டே தேற்றம், சரியான பொருத்தங்களுடன் வரையறுக்கப்பட்ட திசைதிருப்பப்படாத வரைபடங்களின் குணாதிசயமாகும். இது ஹாலின் திருமணக் கோட்பாட்டின் இருதரப்பு முதல் தன்னிச்சையான வரைபடங்கள் வரை பொதுமைப்படுத்தலாகும். இது டுட்டே-பெர்ஜ் சூத்திரத்தின் ஒரு சிறப்பு வழக்கு. உள்ளுணர்வு சரியான பொருத்தம் இல்லாத அனைத்து வரைபடங்களையும் வகைப்படுத்துவதே குறிக்கோள். ஒரு சரியான பொருத்தம் இல்லாமல் ஒரு வரைபடத்தின் மிகவும் வெளிப்படையான வழக்கில் தொடங்குங்கள்ஃ ஒற்றைப்படை எண்ணிக்கையிலான செங்குத்துகளுடன் ஒரு வரைபடம். அத்தகைய வரைபடத்தில், எந்தவொரு பொருந்தும் குறைந்தபட்சம் ஒரு ஒப்பிடமுடியாத உச்சியை விட்டுச்செல்கிறது, எனவே அது சரியானதாக இருக்க முடியாது. சற்றே பொதுவான வழக்கு என்பது துண்டிக்கப்பட்ட வரைபடமாகும், இதில் ஒன்று அல்லது அதற்கு மேற்பட்ட கூறுகள் ஒற்றைப்படை எண்ணிக்கையிலான செங்குத்துகளைக் கொண்டுள்ளன (மொத்த செங்குத்துகளின் எண்ணிக்கை சமமாக இருந்தாலும் கூட). அத்தகைய கூறுகளை ஒற்றைப்படை கூறுகள் என்று அழைப்போம். எந்தவொரு பொருத்தத்திலும், ஒவ்வொரு உச்சியையும் ஒரே கூறுகளில் உள்ள உச்சிகளுடன் மட்டுமே பொருத்த முடியும். எனவே, எந்தவொரு பொருந்தும் ஒவ்வொரு ஒற்றைப்படை கூறுகளிலும் குறைந்தபட்சம் ஒரு ஒப்பிடமுடியாத உச்சியை விட்டுச்செல்கிறது, எனவே அது சரியானதாக இருக்க முடியாது. அடுத்து, ஒரு உச்சி u உடன் ஒரு வரைபடம் G ஐக் கவனியுங்கள், அதாவது நாம் G இலிருந்து உச்சி u மற்றும் அதன் அருகிலுள்ள விளிம்புகளை அகற்றினால், மீதமுள்ள வரைபடம் (குறிக்கப்படுகிறது) இரண்டு அல்லது அதற்கு மேற்பட்ட ஒற்றைப்படை கூறுகளைக் கொண்டுள்ளது. மேலே குறிப்பிட்டபடி, பொருந்தக்கூடிய ஏதேனும் ஒன்று, ஒவ்வொரு ஒற்றைப்படை கூறுகளிலும், அதே கூறுகளில் உள்ள மற்ற செங்குத்துகளுடன் ஒப்பிடமுடியாத குறைந்தபட்சம் ஒரு முனையையாவது விட்டுச்செல்கிறது. அத்தகைய உச்சியை u உடன் மட்டுமே பொருத்த முடியும். ஆனால் இரண்டு அல்லது அதற்கு மேற்பட்ட ஒப்பிடமுடியாத செங்குத்துகள் இருப்பதால், அவற்றில் ஒன்றை மட்டுமே u உடன் பொருத்த முடியும் என்பதால், குறைந்தபட்சம் மற்றொரு செங்குத்தாவது ஒப்பிடப்படாமல் உள்ளது, எனவே பொருத்தம் சரியானதல்ல. இறுதியாக, செங்குத்துகளின் தொகுப்பைக் கொண்ட ஒரு வரைபடம் G ஐக் கவனியுங்கள், G இலிருந்து செங்குத்துகள் மற்றும் அவற்றை ஒட்டியுள்ள அனைத்து விளிம்புகளையும் அகற்றினால், மீதமுள்ள வரைபடம் (குறிக்கப்படுகிறது) ஒற்றைப்படை கூறுகளை விட அதிகமாக உள்ளது. மேலே விவரிக்கப்பட்டுள்ளபடி, எந்தவொரு பொருந்தக்கூடிய பகுதியும் ஒவ்வொரு ஒற்றைப்படை கூறுகளிலும் குறைந்தபட்சம் ஒரு ஒப்பிடமுடியாத உச்சியை விட்டுச்செல்கிறது, மேலும் இவை உச்சிகளுடன் மட்டுமே பொருந்த முடியும்-ஆனால் இந்த ஒப்பிடமுடியாத உச்சிகள் அனைத்திற்கும் போதுமான உச்சிகள் இல்லை, எனவே பொருத்தம் சரியானதல்ல. நாம் ஒரு தேவையான நிபந்தனைக்கு வந்துவிட்டோம்ஃ G ஒரு சரியான பொருத்தத்தைக் கொண்டிருந்தால், G இல் உள்ள ஒவ்வொரு உச்சி துணைக்குழுவிற்கும், வரைபடம் மிகவும் ஒற்றைப்படை கூறுகளைக் கொண்டுள்ளது. டுட்டேயின் தேற்றம் இந்த நிபந்தனை சரியான பொருத்தம் இருப்பதற்கு அவசியமானது மற்றும் போதுமானது என்று கூறுகிறது. டூட்டேயின் தேற்றம் ஒரு வரைபடம், ஒவ்வொரு துணைக்குழுவிற்கும், துணை வரைபடம் மிகவும் ஒற்றைப்படை கூறுகளைக் கொண்டிருந்தால் மட்டுமே சரியான பொருத்தத்தைக் கொண்டுள்ளது (இணைக்கப்பட்ட கூறுகள் ஒற்றைப்படை எண்ணிக்கையிலான செங்குத்துகளைக் கொண்டுள்ளன). ஆதாரம் முதலில் நாம் நிபந்தனையை எழுதுகிறோம்ஃ இது தூண்டப்பட்ட துணை வரைபடத்தின் ஒற்றைப்படை கூறுகளின் எண்ணிக்கையைக் குறிக்கிறது. தேவையின் தேவைஃ இந்த திசை ஏற்கனவே கீழே உள்ள உள்ளுணர்வு பிரிவில் விவாதிக்கப்பட்டது, ஆனால் இங்கே ஆதாரத்தை சுருக்கமாகக் கூறுவோம். ஒரு சரியான பொருத்தத்துடன் ஒரு வரைபடத்தைக் கவனியுங்கள். ஒரு தன்னிச்சையான துணைக்குழுவாக இருக்கட்டும். நீக்கவும். ஒரு தன்னிச்சையான ஒற்றைப்படை கூறாக இருக்கட்டும். ஒரு சரியான பொருத்தம் இருந்ததால், குறைந்தபட்சம் ஒரு உச்சியில் ஒரு உச்சியுடன் பொருந்த வேண்டும். எனவே, ஒவ்வொரு ஒற்றைப்படை கூறுகளும் குறைந்தபட்சம் ஒரு உச்சியுடன் பொருந்தக்கூடிய ஒரு உச்சியைக் கொண்டுள்ளன. ஒவ்வொரு உச்சியும் அதிகபட்சம் ஒரு இணைக்கப்பட்ட கூறுடன் இந்த உறவில் இருக்க முடியும் என்பதால் (இது ஒரு சரியான பொருத்தத்தில் அதிகபட்சம் ஒரு முறை பொருந்துவதால்), (ற்றஂ) இன் போதுமான அளவுஃ சரியான பொருத்தம் இல்லாத ஒரு தன்னிச்சையான வரைபடமாக இருக்கட்டும். துட்டே மீறுபவர் என்று அழைக்கப்படுபவரை நாம் கண்டுபிடிப்போம், அதாவது, அத்தகைய ஒரு துணைக்குழு. அது விளிம்பு-அதிகபட்சம் என்று நாம் கருதலாம், அதாவது, ஏற்கனவே இல்லாத ஒவ்வொரு விளிம்பிற்கும் சரியான பொருத்தம் உள்ளது. உண்மையில், விளிம்பு-அதிகபட்ச வரைபடத்தில் ஒரு டூட்டே மீறுபவரைக் கண்டால், ஒவ்வொரு பரவலான துணை வரைபடத்திலும் ஒரு டூட்டே மீறுபவர் ஆவார், ஏனெனில் ஒவ்வொரு ஒற்றைப்படை கூறுகளும் அதிக கூறுகளாகப் பிரிக்கப்படும், அவற்றில் குறைந்தபட்சம் ஒன்று மீண்டும் ஒற்றைப்படை இருக்கும். டிகிரியுடன் கூடிய செங்குத்துகளின் தொகுப்பாக நாம் வரையறுக்கிறோம். முதலில் அனைத்து கூறுகளும் முழுமையான வரைபடங்களாக இருக்கும் வழக்கைக் கருத்தில் கொள்கிறோம். பின்னர் ஒரு டூட்டே மீறுபவராக இருக்க வேண்டும், ஏனென்றால், ஒவ்வொரு ஒற்றைப்படை கூறுகளிலிருந்தும் ஒரு உச்சியை ஒரு உச்சியுடன் பொருத்துவதன் மூலமும், மற்ற அனைத்து உச்சிகளையும் இணைப்பதன் மூலமும் ஒரு சரியான பொருத்தத்தைக் கண்டுபிடிக்க முடியும் (இது ஒற்றைப்படை இல்லையென்றால் வேலை செய்யும், ஆனால் பின்னர் ஒரு டூட்டே மீறுபவர்). இப்போது அது ஒரு கூறு மற்றும் அது போன்ற செங்குத்துகள் என்று வைத்துக்கொள்வோம். குறுகிய பாதையில் முதல் செங்குத்தாக இருக்கட்டும். இது அதை உறுதி செய்கிறது மற்றும். ஏனெனில், அது போன்ற ஒரு உச்சி உள்ளது. விளிம்பு-அதிகபட்சத்திலிருந்து, ஒரு சரியான பொருத்தம் மற்றும் ஒரு சரியான பொருத்தம் என வரையறுக்கிறோம். அதை கண்டிப்பாக கவனியுங்கள். ஒரு விளிம்பில் இருந்து தொடங்கி அதன் விளிம்புகள் மற்றும் இடையே மாறி மாறி வரும் அதிகபட்ச பாதையாக இருக்கட்டும். எப்படி முடிவுக்கு வர முடியும்? அல்லது போன்ற 'சிறப்பு' உச்சிக்கு நாம் வராவிட்டால், நாம் எப்போதும் தொடரலாம்ஃ-பொருந்துகிறது, எனவே முதல் விளிம்பு இல்லை, எனவே இரண்டாவது உச்சி வேறு விளிம்பால் பொருந்துகிறது, மேலும் நாம் இந்த முறையில் தொடர்கிறோம். இதன் கடைசி உச்சியை குறிக்கலாம். கடைசி விளிம்பு இருந்தால், பின்னர் இருக்க வேண்டும், இல்லையெனில் நாம் ஒரு விளிம்புடன் தொடரலாம் (அல்லது அடைய கூட). இந்த விஷயத்தில் நாம் வரையறுக்கிறோம். கடைசி விளிம்பு உள்ளே இருந்தால், நிச்சயமாக ஒத்த காரணத்திற்காக நாம் வரையறுக்கிறோம். இப்போது ஒவ்வொரு விளிம்பிலும் சம நீளமுள்ள ஒரு சுழற்சி. நாம் இப்போது வரையறுக்க முடியும் (சமச்சீர் வேறுபாடு எங்கே) மற்றும் நாம் ஒரு சரியான பொருத்தம், ஒரு முரண்பாடு பெற. டுட்டே-பெர்ஜ் சூத்திரத்திற்கு சமத்துவம் ஒரு வரைபடத்தின் அதிகபட்ச பொருத்தத்தின் அளவு சமம் என்று டுட்டே-பெர்ஜ் சூத்திரம் கூறுகிறது. சமமாக, அதிகபட்ச பொருத்தம் உள்ள ஒப்பிடமுடியாத செங்குத்துகளின் எண்ணிக்கை சமம். இந்த சூத்திரம் டுட்டேயின் தேற்றத்திலிருந்து பின்பற்றப்படுகிறது, புதிய செங்குத்துகளைச் சேர்ப்பதன் மூலம் பெறப்பட்ட வரைபடம், ஒவ்வொன்றும் ஒவ்வொரு அசல் உச்சியிலும் இணைந்தால் மட்டுமே, அளவுடன் பொருந்தக்கூடிய அவதானிப்புடன். ஒன்றுக்கு மேற்பட்ட கூறுகளாகப் பிரியும் எந்தவொரு தொகுப்பும் அனைத்து புதிய செங்குத்துகளையும் கொண்டிருக்க வேண்டும் என்பதால், (*) என்றால் மற்றும் இருந்தால் மட்டுமே திருப்தி அளிக்கப்படுகிறது. எல்லையற்ற வரைபடங்களில் உள்ளூரில் வரையறுக்கப்பட்ட இணைக்கப்பட்ட எல்லையற்ற வரைபடங்களுக்கு (ஒவ்வொரு உச்சிக்கும் வரையறுக்கப்பட்ட டிகிரி உள்ளது), டுட்டேயின் நிபந்தனையின் பொதுமைப்படுத்தல் பின்வருமாறு உள்ளதுஃ வரையறுக்கப்பட்ட துணைக்குழு இல்லையென்றால் மட்டுமே அத்தகைய வரைபடங்கள் சரியான பொருத்தங்களைக் கொண்டுள்ளன, அதன் அகற்றல் துணைக்குழுவின் அளவை விட பெரிய வரையறுக்கப்பட்ட ஒற்றைப்படை கூறுகளை உருவாக்குகிறது. இருதரப்பு பொருந்தும் ஹாலின் திருமணத் தேற்றம் பீட்டர்சனின் தேற்றம் குறிப்புகள் பொருந்தும் குறிப்புகள் (வரைபடக் கோட்பாடு) வரைபடக் கோட்பாட்டில் உள்ள தேற்றம் சான்றுகளைக் கொண்ட கட்டுரைகள்