Ear decomposition
வரைபடக் கோட்பாட்டில், திசைதிருப்பப்படாத வரைபடம் G இன் காது என்பது பாதையின் இரண்டு இறுதிப் புள்ளிகள் ஒத்துப்போகும் ஒரு பாதை P ஆகும், இல்லையெனில் விளிம்புகள் அல்லது செங்குத்துகளை மீண்டும் மீண்டும் செய்ய அனுமதிக்கப்படுவதில்லை, எனவே P இன் ஒவ்வொரு உள் உச்சியும் G இல் டிகிரி இரண்டைக் கொண்டுள்ளது. கூடுதலாக, பெரும்பாலான சந்தர்ப்பங்களில் இந்த வரிசையில் முதல் காது ஒரு சுழற்சியாக இருக்க வேண்டும். திறந்த காது சிதைவு அல்லது சரியான காது சிதைவு என்பது ஒரு காது சிதைவு ஆகும், இதில் ஒவ்வொரு காதின் இரண்டு இறுதிப் புள்ளிகளும் முதல் இடத்திற்குப் பிறகு ஒருவருக்கொருவர் வேறுபடுகின்றன. பல முக்கியமான வரைபட வகுப்புகளை வகைப்படுத்தவும், திறமையான வரைபட வழிமுறைகளின் ஒரு பகுதியாகவும் காது சிதைவுகள் பயன்படுத்தப்படலாம். அவை வரைபடங்கள் முதல் மேட்ராய்டுகள் வரை பொதுமைப்படுத்தப்படலாம். வரைபட வகுப்புகளை வகைப்படுத்துதல் பல முக்கியமான வகை வரைபடங்கள் சில வகையான காது சிதைவுகளைக் கொண்ட வரைபடங்களாக வகைப்படுத்தப்படலாம். எந்தவொரு (k−1) செங்குத்துகளையும் அகற்றுவது இணைக்கப்பட்ட துணை வரைபடத்தை விட்டு வெளியேறினால் ஒரு வரைபடம் k-வெர்டெக்ஸ்-இணைக்கப்பட்டுள்ளது, மேலும் ஏதேனும் (k−1) விளிம்புகளை அகற்றுவது இணைக்கப்பட்ட துணை வரைபடத்தை விட்டு வெளியேறினால் k-விளிம்பு-இணைக்கப்பட்டுள்ளது. பின்வரும் விளைவு பின்வருமாறுஃ திறந்த காது சிதைவு இருந்தால் மட்டுமே 2-வெர்டெக்ஸ்-இணைக்கப்பட்ட ஒரு வரைபடம். பின்வரும் விளைவு பின்வருமாறுஃ ஒரு வரைபடம் காது சிதைவு இருந்தால் மட்டுமே அது 2-விளிம்புடன் இணைக்கப்பட்டுள்ளது. இரண்டு நிகழ்வுகளிலும் காதுகளின் எண்ணிக்கை கொடுக்கப்பட்ட வரைபடத்தின் சுற்று தரவரிசைக்கு சமமாக இருக்க வேண்டும். ராபின்ஸ் தேற்றத்தை நிரூபிப்பதற்கான ஒரு கருவியாக 2-விளிம்புடன் இணைக்கப்பட்ட வரைபடங்களின் காது சிதைவை ராபின்ஸ் அறிமுகப்படுத்தினார், இவை சரியாக வலுவாக இணைக்கப்பட்ட நோக்குநிலையைக் கொடுக்கக்கூடிய வரைபடங்கள். காது சிதைவுகளில் விட்னி மற்றும் ராபின்ஸின் முன்னோடி பணியின் காரணமாக, ஒரு காது சிதைவு சில நேரங்களில் விட்னி-ராபின்ஸ் தொகுப்பு என்றும் அழைக்கப்படுகிறது. ஒரு பிரிக்கப்படாத காது சிதைவு என்பது ஒரு திறந்த காது சிதைவு ஆகும், ஒவ்வொரு உச்சிக்கும் ஒரே ஒரு விதிவிலக்குடன், வி-க்கு ஒரு அண்டை உள்ளது, அதன் சிதைவில் முதல் தோற்றம் வி-இன் முதல் தோற்றத்தை விட பிற்கால காதில் உள்ளது. இந்த வகை காது சிதைவு விட்னியின் முடிவை பொதுமைப்படுத்த பயன்படுத்தப்படலாம்ஃ ஜி-க்கு பிரிக்கப்படாத காது சிதைவு இருந்தால் மட்டுமே 3-வெர்டெக்ஸ்-இணைக்கப்பட்ட வரைபடம். அத்தகைய சிதைவு இருந்தால், G இன் ஒரு குறிப்பிட்ட விளிம்பைப் பொறுத்தவரை, u முதல் காதில் இருக்கும் வகையில் அதைத் தேர்ந்தெடுக்கலாம், v என்பது ஒன்றுக்கு மேற்பட்ட விளிம்பைக் கொண்ட கடைசி காதில் உள்ள புதிய உச்சி, மற்றும் uv என்பது ஒற்றை விளிம்பைக் கொண்ட காது. இந்த முடிவு முதன்முதலில் வெளிப்படையாக கூறப்பட்டது, ஆனால் விவரிக்கிறபடி, இது 1971 பி. எச். டி. லீ மாண்ட்ஷீனின் ஆய்வறிக்கையின் முடிவுக்கு சமம். அதிகபட்ச பிளானர் வரைபடங்களின் பிரிக்கப்படாத காது சிதைவுகளுடன் நெருக்கமாக தொடர்புடைய கட்டமைப்புகள், நியதி வரிசைமுறைகள் என்று அழைக்கப்படுகின்றன, அவை வரைபட வரைபடத்தில் ஒரு நிலையான கருவியாகும். இயக்கப்படும் வரைபடங்களின் வலுவான இணைப்பு மேற்கண்ட வரையறைகள் இயக்கப்படும் வரைபடங்களுக்கும் பயன்படுத்தப்படலாம். ஒரு காது பின்னர் ஒரு திசைப்படுத்தப்பட்ட பாதையாக இருக்கும், அங்கு அனைத்து உள் செங்குத்துகளும் 1 க்கு சமமான இன்டெக்ரி மற்றும் அவுட் டிகிரியைக் கொண்டிருக்கும். ஒவ்வொரு முனையிலிருந்தும் மற்ற ஒவ்வொரு முனையத்திற்கும் ஒரு வழிநடத்தப்பட்ட பாதையைக் கொண்டிருந்தால் ஒரு வழிநடத்தப்பட்ட வரைபடம் வலுவாக இணைக்கப்பட்டுள்ளது. பின்னர் நம்மிடம் பின்வரும் தேற்றம் உள்ளதுஃ ஒரு இயக்கப்பட்ட வரைபடம் ஒரு காது சிதைவு இருந்தால் மட்டுமே வலுவாக இணைக்கப்படுகிறது. காரணி-முக்கியமான வரைபடங்கள் ஒரு காது சிதைவு அதன் ஒவ்வொரு காதும் ஒற்றைப்படை எண்ணிக்கையிலான விளிம்புகளைப் பயன்படுத்தினால் ஒற்றைப்படை. ஒரு காரணி-முக்கியமான வரைபடம் என்பது ஒற்றைப்படை எண்ணிக்கையிலான செங்குத்துகளைக் கொண்ட ஒரு வரைபடமாகும், அதாவது ஒவ்வொரு உச்சிக்கும் v, வரைபடத்திலிருந்து அகற்றப்பட்டால், மீதமுள்ள செங்குத்துகள் சரியான பொருத்தத்தைக் கொண்டுள்ளன. G க்கு ஒற்றைப்படை காது சிதைவு இருந்தால் மட்டுமே G வரைபடம் காரணி-முக்கியமானதாக இருக்கும் என்று கண்டறியப்பட்டது. மேலும் பொதுவாக, இதன் விளைவாக எந்தவொரு G வரைபடத்திலும் குறைவான சமமான காதுகளுடன் காது சிதைவைக் கண்டறிய முடியும். தொடர்-இணையான வரைபடங்கள் ஒரு மர காது சிதைவு என்பது ஒரு சரியான காது சிதைவு ஆகும், இதில் முதல் காது ஒரு விளிம்பாகவும், அடுத்தடுத்த ஒவ்வொரு காதுக்கும் ஒரு காது உள்ளது, அதாவது இரண்டு இறுதிப் புள்ளிகளும் உள்ளன. ஒரு நெஸ்டட் காது சிதைவு என்பது ஒரு மர காது சிதைவு ஆகும், இது ஒவ்வொரு காதிலும், மற்ற காதுகளின் இறுதிப் புள்ளிகளின் ஜோடிகளின் தொகுப்பாகும், அவை நெஸ்டட் இடைவெளிகளின் தொகுப்பை உருவாக்குகின்றன. ஒரு தொடர்-இணையான வரைபடம் என்பது இரண்டு நியமிக்கப்பட்ட முனையங்களைக் கொண்ட ஒரு வரைபடமாகும், அவை சிறிய தொடர்-இணையான வரைபடங்களை இரண்டு வழிகளில் ஒன்றில் இணைப்பதன் மூலம் மீண்டும் மீண்டும் உருவாக்கப்படலாம்ஃ தொடர் கலவை (ஒரு சிறிய வரைபடத்திலிருந்து ஒரு முனையத்தை மற்றொரு சிறிய வரைபடத்திலிருந்து ஒரு முனையத்துடன் அடையாளம் காணுதல், மற்ற இரண்டு முனையங்களை ஒருங்கிணைந்த வரைபடத்தின் முனையங்களாக வைத்திருத்தல்) மற்றும் இணையான கலவை (இரண்டு சிறிய வரைபடங்களிலிருந்து இரண்டு ஜோடி முனையங்களையும் அடையாளம் காணுதல்). பின்வரும் விளைவு பின்வருமாறுஃ ஒரு 2-வெர்டெக்ஸ்-இணைக்கப்பட்ட வரைபடம் ஒரு நெஸ்டட் காது சிதைவு இருந்தால் மட்டுமே தொடர்-இணையாக இருக்கும். மேலும், 2-வெர்டெக்ஸ்-இணைக்கப்பட்ட தொடர்-இணையான வரைபடத்தின் திறந்த காது சிதைவு கூடாக இருக்க வேண்டும். இரண்டு முனையங்களுக்கு இடையிலான பாதையில் தொடங்கும் திறந்த காது சிதைவுகளைப் பயன்படுத்துவதன் மூலம் 2-வெர்டெக்ஸ்-இணைக்கப்படாத தொடர்-இணையான வரைபடங்களுக்கு இதன் விளைவாக நீட்டிக்கப்படலாம். காது சிதைவு என்ற கருத்தை வரைபடங்களிலிருந்து மேட்ராய்டுகள் வரை நீட்டிக்க முடியும். ஒரு மேட்ராய்டின் காது சிதைவு என்பது இரண்டு பண்புகளைக் கொண்ட மேட்ராய்டின் சுற்றுகளின் வரிசையாக வரையறுக்கப்படுகிறதுஃ வரிசையில் உள்ள ஒவ்வொரு சுற்றும் முந்தைய சுற்றுகளுடன் ஒரு வெற்று குறுக்குவெட்டைக் கொண்டுள்ளது, மேலும் வரிசையில் உள்ள ஒவ்வொரு சுற்றும் முந்தைய அனைத்து சுற்றுகளும் இருந்தாலும் கூட ஒரு சுற்றாக உள்ளது. G வரைபடத்தின் கிராஃபிக் மேட்ராய்டில் பயன்படுத்தப்படும்போது, காது சிதைவின் இந்த வரையறை G இன் சரியான காது சிதைவின் வரையறையுடன் ஒத்துப்போகிறதுஃ முறையற்ற சிதைவுகள் ஒவ்வொரு சுற்றிலும் முந்தைய சுற்றுகளுக்கு சொந்தமான குறைந்தபட்சம் ஒரு விளிம்பையாவது கொண்டிருக்க வேண்டும் என்ற தேவையால் விலக்கப்படுகின்றன. இந்த வரையறையைப் பயன்படுத்தி, ஒரு மேட்ராய்டு ஒரு காது சிதைவைக் கொண்டிருக்கும்போது காரணி-முக்கியமானதாக வரையறுக்கப்படலாம், இதில் வரிசையில் உள்ள ஒவ்வொரு சுற்றிலும் ஒற்றைப்படை எண்ணிக்கையிலான புதிய கூறுகள் உள்ளன. படிமுறைகள் கிளாசிக்கல் கணினிகளில், 2-முனை-இணைக்கப்பட்ட வரைபடங்களின் காது சிதைவுகள் மற்றும் 2-வெர்டெக்ஸ்-இணைக்கப்பட்ட வரைபடங்களின் திறந்த காது சிதைவுகள் ஆகியவை பேராசை வழிமுறைகளால் கண்டறியப்படலாம், அவை ஒவ்வொரு காதையும் ஒரே நேரத்தில் கண்டுபிடிக்கின்றன. ஒரே நேரத்தில் காது சிதைவுகள், திறந்த காது சிதைவுகள், St-எண்கள் மற்றும்-நோக்குநிலைகளை நேரியல் நேரத்தில் (இருந்தால்) கணக்கிடும் ஒரு எளிய பேராசை அணுகுமுறை கொடுக்கப்பட்டுள்ளது. இந்த அணுகுமுறை ஒரு பாதையை உருவாக்கும் விதியால் சங்கிலி சிதைவு என்று அழைக்கப்படும் ஒரு சிறப்பு காது சிதைவைக் கணக்கிடுவதை அடிப்படையாகக் கொண்டது. பிரிக்கப்படாத காது சிதைவுகளும் நேரியல் நேரத்தில் கட்டமைக்கப்படலாம் என்பதைக் காட்டுகிறது. , மற்றும் பல்வேறு வகையான காது சிதைவுகளை உருவாக்குவதற்கான திறமையான இணையான வழிமுறைகளை வழங்கியது. உதாரணமாக, 2-விளிம்புடன் இணைக்கப்பட்ட வரைபடத்தின் காது சிதைவைக் கண்டறிய, பின்வரும் படிநிலைகளின்படி வருமானத்தின் வழிமுறைஃ கொடுக்கப்பட்ட வரைபடத்தின் ஒரு பரவலான மரத்தைக் கண்டுபிடித்து, மரத்திற்கான வேரைத் தேர்ந்தெடுக்கவும். மரத்தின் ஒரு பகுதியாக இல்லாத ஒவ்வொரு விளிம்புக்கும், u மற்றும் v இன் வேர் மற்றும் மிகக் குறைந்த பொதுவான மூதாதையருக்கு இடையிலான தூரத்தை தீர்மானிக்கவும். மரத்தின் ஒரு பகுதியாக இருக்கும் ஒவ்வொரு விளிம்புக்கும், அதனுடன் தொடர்புடைய "மாஸ்டர் எட்ஜ்" ஐக் கண்டறியவும், இது ஒரு மரம் அல்லாத விளிம்பாகும், இது மரத்தில் wx ஐச் சேர்ப்பதன் மூலம் உருவாகும் சுழற்சி uv வழியாகச் செல்கிறது, மேலும் அத்தகைய விளிம்புகளில், w மற்றும் x ஆகியவை மிகக் குறைந்த பொதுவான மூதாதையரைக் கொண்டுள்ளன, அவை முடிந்தவரை வேருக்கு நெருக்கமாக இருக்கும் (விளிம்பு அடையாளங்காட்டிகளால் உடைக்கப்பட்ட உறவுகளுடன்). மரங்கள் அல்லாத ஒவ்வொரு விளிம்பிற்கும், அது எஜமானராக இருக்கும் மரத்தின் விளிம்புகளையும் உள்ளடக்கிய ஒரு காதை உருவாக்கி, காதுகளை அவற்றின் எஜமானரின் விளிம்புகளின் வேரிலிருந்து உள்ள தூரத்தால் வரிசைப்படுத்துங்கள் (அதே டை-பிரேக்கிங் விதியுடன்). இந்த வழிமுறைகள் சோதனை இணைப்பு, தொடர்-இணையான வரைபடங்களை அங்கீகரித்தல் மற்றும் வரைபடங்களின் எஸ். டி-எண்களை உருவாக்குதல் (பிளானாரிட்டி சோதனையில் ஒரு முக்கியமான சப்ரூட்டின்) உள்ளிட்ட பிற சிக்கல்களுக்கு சப்ரூட்டின்களாகப் பயன்படுத்தப்படலாம். கொடுக்கப்பட்ட மேட்ராய்டின் காது சிதைவு, ஒவ்வொரு காதிலும் மேட்ராய்டின் ஒரே நிலையான உறுப்பு உள்ளது என்ற கூடுதல் தடையுடன், மேட்ராய்டுக்கான சுதந்திர ஆரக்கிள் அணுகல் வழங்கப்பட்ட பல்லுறுப்புக்கோவை நேரத்தில் காணலாம். குறிப்புகள். . . . . . . . . . . . . . . . வரைபடக் கோட்பாடு மேட்ராய்டு கோட்பாட்டைக் குறிக்கிறது