Ore's theorem
ஓரியின் தேற்றம் என்பது 1960 ஆம் ஆண்டில் நோர்வே கணிதவியலாளர் ஓஸ்டீன் ஓரால் நிரூபிக்கப்பட்ட வரைபடக் கோட்பாட்டின் விளைவாகும். இது ஒரு வரைபடம் ஹாமில்டோனியனாக இருக்க போதுமான நிபந்தனையை வழங்குகிறது, அடிப்படையில் போதுமான பல விளிம்புகளைக் கொண்ட ஒரு வரைபடம் ஹாமில்டன் சுழற்சியைக் கொண்டிருக்க வேண்டும் என்று கூறுகிறது. குறிப்பாக, இந்த தேற்றம் அருகில் இல்லாத செங்குத்துகளின் ஜோடிகளின் டிகிரிகளின் கூட்டுத்தொகையைக் கருதுகிறதுஃ அத்தகைய ஒவ்வொரு ஜோடியும் குறைந்தபட்சம் வரைபடத்தில் உள்ள மொத்த செங்குத்துகளின் எண்ணிக்கைக்கு சமமான கூட்டுத்தொகையைக் கொண்டிருந்தால், வரைபடம் ஹாமில்டோனியன் ஆகும். முறையான அறிக்கை செங்குத்துகளுடன் ஒரு (வரையறுக்கப்பட்ட மற்றும் எளிய) வரைபடமாக இருக்கட்டும். நாம் ஒரு உச்சியின் டிகிரியால் குறிக்கிறோம், அதாவது. சம்பவ விளிம்புகளின் எண்ணிக்கை. பின்னர், ஒரேயின் தேற்றம் அப்படியானால் ஹாமில்டோனியன் என்று கூறுகிறது. ஆதாரம் ஒவ்வொரு ஹாமில்டோனியன் அல்லாத வரைபடமும் நிபந்தனைக்கு இணங்கவில்லை என்பதைக் காண்பிப்பதற்கு இது சமம். அதன்படி, ஹாமில்டோனியன் அல்லாத செங்குத்துகளில் ஒரு வரைபடமாக இருக்கட்டும், மேலும் விளிம்புகளைச் சேர்க்க முடியாத வரை, ஹாமில்டோனியன் சுழற்சியை உருவாக்காத ஒரு நேரத்தில் விளிம்புகளைச் சேர்ப்பதன் மூலம் உருவாகலாம். ஏதேனும் இரண்டு அருகருகே இல்லாத செங்குத்துகளாக இருக்கட்டும். பின்னர் விளிம்பைச் சேர்ப்பது குறைந்தபட்சம் ஒரு புதிய ஹாமில்டோனியன் சுழற்சியை உருவாக்கும், மேலும் அத்தகைய சுழற்சியைத் தவிர வேறு விளிம்புகள் மற்றும் உடன் ஒரு ஹாமில்டோனியன் பாதையை உருவாக்க வேண்டும். வரம்பில் உள்ள ஒவ்வொரு குறியீட்டிற்கும், முதல் மற்றும் முதல் இரண்டு சாத்தியமான விளிம்புகளைக் கவனியுங்கள். இந்த இரண்டு விளிம்புகளில் அதிகபட்சம் ஒன்று இருக்கலாம், இல்லையெனில் சுழற்சி ஒரு ஹாமில்டோனியன் சுழற்சியாக இருக்கும். எனவே, மொத்த விளிம்புகளின் எண்ணிக்கை ஒன்று அல்லது அதிகபட்சமாக தேர்வுகளின் எண்ணிக்கைக்கு சமம், இது. எனவே, இந்த மொத்த விளிம்புகளின் எண்ணிக்கை () ஐ விட அதிகமாகவோ அல்லது சமமாகவோ இருக்க வேண்டும் என்று தேவைப்படும் பண்பு (ற்றஂ) க்கு கீழ்ப்படியாது. உச்சியில் உள்ள டிகிரிகள் அதிகபட்சமாக டிகிரிக்கு சமமாக இருப்பதால், அது பின்வருமாறு பண்புக்கு (ir) கீழ்ப்படியாது. அல்காரிதம் ஓர் நிலைமையை சந்திக்கும் வரைபடத்தில் ஹாமில்டோனியன் சுழற்சியை உருவாக்குவதற்கான பின்வரும் எளிய வழிமுறையை விவரிக்கிறது. வரைபடத்தில் உள்ள அருகாமைகளை புறக்கணித்து, செங்குத்துகளை ஒரு சுழற்சியில் தன்னிச்சையாக வரிசைப்படுத்துங்கள். சுழற்சியில் இரண்டு தொடர்ச்சியான செங்குத்துகள் vi மற்றும் vi + 1 உள்ளன, அவை வரைபடத்தில் அருகில் இல்லை, பின்வரும் இரண்டு படிகளைச் செய்யுங்கள்ஃ vi, vi + 1, vj மற்றும் vj + 1 ஆகிய நான்கு செங்குத்துகள் அனைத்தும் தனித்துவமாகவும், வரைபடத்தில் vi முதல் vj வரையிலும், vj + 1 முதல் vi + 1 வரையிலும் விளிம்புகள் இருக்கும் வகையில் ஒரு குறியீட்டு j ஐத் தேடுங்கள். ஒவ்வொரு படியும் வரைபடத்தில் அருகிலுள்ள சுழற்சியில் தொடர்ச்சியான ஜோடிகளின் எண்ணிக்கையை ஒன்று அல்லது இரண்டு ஜோடிகளால் அதிகரிக்கிறது (vj மற்றும் vj + 1 ஏற்கனவே அருகிலுள்ளதா என்பதைப் பொறுத்து), எனவே வெளிப்புற வளையம் வழிமுறை முடிவடைவதற்கு முன்பு அதிகபட்ச n நேரங்களில் மட்டுமே நிகழ முடியும், இதில் n என்பது கொடுக்கப்பட்ட வரைபடத்தில் உள்ள செங்குத்துகளின் எண்ணிக்கை. தேற்றத்தின் ஆதாரத்தில் உள்ளதைப் போன்ற ஒரு வாதத்தின் மூலம், விரும்பிய குறியீடு ஜே இருக்க வேண்டும், இல்லையெனில் அருகிலுள்ள செங்குத்துகள் vi மற்றும் vi + 1 ஆகியவை மொத்த டிகிரியை மிகக் குறைவாகக் கொண்டிருக்கும். i மற்றும் j ஐக் கண்டறிவதும், சுழற்சியின் ஒரு பகுதியை மாற்றியமைப்பதும் அனைத்தும் O (n) நேரத்தில் நிறைவேற்றப்படலாம். எனவே, வழிமுறையின் மொத்த நேரம் O (n2) ஆகும், இது உள்ளீட்டு வரைபடத்தில் உள்ள விளிம்புகளின் எண்ணிக்கையுடன் பொருந்துகிறது. தொடர்புடைய முடிவுகள் ஓரியின் தேற்றம் டிராக்கின் தேற்றத்தின் பொதுமைப்படுத்தலாகும், ஒவ்வொரு உச்சிக்கும் குறைந்தபட்சம் டிகிரி இருக்கும்போது, வரைபடம் ஹாமில்டோனியன் ஆகும். ஏனெனில், ஒரு வரைபடம் டிராக்கின் நிபந்தனையை பூர்த்தி செய்தால், ஒவ்வொரு ஜோடி செங்குத்துகளும் குறைந்தபட்சம் டிகிரிகளைச் சேர்க்கின்றன. இதையொட்டி ஓரியின் தேற்றம் பாண்டி-ச்வாடல் தேற்றத்தால் பொதுமைப்படுத்தப்படுகிறது. ஒரு வரைபடத்தில் ஒரு மூடல் செயல்பாட்டை ஒருவர் வரையறுக்கலாம், இதில் இரண்டு அருகிலுள்ள செங்குத்துகள் குறைந்தபட்சம் டிகிரிகளைச் சேர்க்கும் போதெல்லாம், ஒன்று அவற்றை இணைக்கும் விளிம்பைச் சேர்க்கிறது; ஒரு வரைபடம் ஓரியின் தேற்றத்தின் நிபந்தனைகளை பூர்த்தி செய்தால், அதன் மூடல் ஒரு முழுமையான வரைபடமாகும். பாண்டி-ச்வாடல் தேற்றம் ஒரு வரைபடம் ஹாமில்டோனியன் என்றால் அதன் மூடல் ஹாமில்டோனியன் என்றால் மட்டுமே ஹாமில்டோனியன் என்று கூறுகிறது; முழுமையான வரைபடம் ஹாமில்டோனியன் என்பதால், ஓரியின் தேற்றம் உடனடி விளைவாகும். இயக்கப்பட்ட வரைபடங்களுக்கு பொருந்தும் ஓரின் தேற்றத்தின் பதிப்பைக் கண்டறிந்தார். ஒரு டிகிராஃப் G க்கு, u மற்றும் v ஆகிய இரண்டு செங்குத்துகளுக்கும், u முதல் v வரை ஒரு விளிம்பு உள்ளது அல்லது u இன் அவுட் டிகிரி மற்றும் v இன் இன்டெக்ரி G இல் செங்குத்துகளின் எண்ணிக்கைக்கு சமம் அல்லது அதற்கு மேல் உள்ளது என்று வைத்துக்கொள்வோம். பின்னர், உடாலின் தேற்றத்தின்படி, G ஒரு இயக்கிய ஹாமில்டோனியன் சுழற்சியைக் கொண்டுள்ளது. கொடுக்கப்பட்ட திசைதிருப்பப்படாத வரைபடத்தில் உள்ள ஒவ்வொரு விளிம்பையும் ஒரு ஜோடி திசைதிருப்பப்பட்ட விளிம்புகளால் மாற்றுவதன் மூலம் உடாலிடமிருந்து ஓரத்தின் தேற்றத்தைப் பெறலாம். ஒரு நெருக்கமான தொடர்புடைய தேற்றம், ஒரு n-வெர்டெக்ஸ் டிகிராப்பை ஒரு பண்புடன் வலுவாக இணைத்துள்ளது, ஒவ்வொரு இரண்டு அருகிலுள்ள செங்குத்துகள் u மற்றும் v க்கு, u அல்லது v க்கு ஏற்படும் மொத்த விளிம்புகளின் எண்ணிக்கை குறைந்தது 2n−1 ஹாமில்டோனியனாக இருக்க வேண்டும். தேற்றத்தில் உள்ள டிகிரி நிபந்தனையின் விளைவாக ஹாமில்டோனிசிட்டியை விட வலுவான முடிவைக் கொடுக்க ஓரியின் தேற்றத்தையும் வலுப்படுத்தலாம். குறிப்பாக, ஓர் தேற்றத்தின் நிபந்தனைகளை பூர்த்தி செய்யும் ஒவ்வொரு வரைபடமும் ஒரு வழக்கமான முழுமையான இருதரப்பு வரைபடம் அல்லது பான்சிக்ளிக் ஆகும். குறிப்புகள். . . . . புற வரைபடக் கோட்பாடு வரைபடக் கோட்பாட்டில் உள்ள தேற்றங்கள் ஹாமில்டோனியன் பாதைகள் மற்றும் சுழற்சிகளின் சான்றுகளைக் கொண்ட கட்டுரைகள்