Well-covered graph
வரைபடக் கோட்பாட்டில், நன்கு மூடப்பட்ட வரைபடம் என்பது ஒரு திசைதிருப்பப்படாத வரைபடமாகும், இதில் ஒவ்வொரு குறைந்தபட்ச உச்சி மறைப்பும் மற்ற ஒவ்வொரு குறைந்தபட்ச உச்சி மறைப்பையும் போலவே இருக்கும். சமமாக, இவை அனைத்து அதிகபட்ச சுயாதீன தொகுப்புகளும் சம அளவைக் கொண்ட வரைபடங்கள். நன்கு மூடப்பட்ட வரைபடங்கள் 1970 ஆம் ஆண்டில் மைக்கேல் டி. பிளம்மரால் வரையறுக்கப்பட்டு முதன்முதலில் ஆய்வு செய்யப்பட்டன. நன்கு மூடப்பட்ட வரைபடங்களில் அனைத்து முழுமையான வரைபடங்களும், சீரான முழுமையான இருதரப்பு வரைபடங்களும் அடங்கும், மேலும் ரூக்கின் வரைபடங்கள் அதன் செங்குத்துகள் ஒரு சதுரங்கப் பலகையின் சதுரங்களைக் குறிக்கின்றன மற்றும் விளிம்புகள் ஒரு சதுரங்க ரூக்கின் நகர்வுகளைக் குறிக்கின்றன. நன்கு மூடப்பட்ட கனசதுர வரைபடங்களின் அறியப்பட்ட குணாதிசயங்கள், நன்கு மூடப்பட்ட நகங்கள் இல்லாத வரைபடங்கள் மற்றும் உயர் சுற்றளவு நன்கு மூடப்பட்ட வரைபடங்கள் இந்த வரைபடங்களை பல்லுறுப்புக்கோவை நேரத்தில் அடையாளம் காண அனுமதிக்கின்றன, ஆனால் மற்ற வகையான வரைபடங்கள் நன்கு மூடப்பட்டிருக்கிறதா என்பதை சோதிப்பது ஒரு கோஎன்பி-முழுமையான சிக்கலாகும். வரையறைகள் ஒரு வரைபடத்தில் ஒரு உச்சி உறை என்பது வரைபடத்தின் ஒவ்வொரு விளிம்பையும் தொடும் செங்குத்துகளின் தொகுப்பாகும். ஒரு வெர்டெக்ஸ் கவர் குறைந்தபட்சம், அல்லது குறைக்கப்படாதது, அதிலிருந்து எந்த வெர்டெக்ஸையும் அகற்றுவது கவரிங் சொத்தை அழிக்கும். குறைவான செங்குத்துகளுடன் வேறு உச்சி மறைப்பு இல்லையென்றால் இது குறைந்தபட்சமாகும். நன்கு மூடப்பட்ட வரைபடம் என்பது ஒவ்வொரு குறைந்தபட்ச அட்டையும் குறைந்தபட்சமாக இருக்கும். நன்கு மூடப்பட்ட வரைபடங்களை வரையறுக்கும் அசல் காகிதத்தில், ஒவ்வொரு இரண்டு குறைந்தபட்ச அட்டைகளும் ஒன்றுக்கொன்று ஒரே எண்ணிக்கையிலான செங்குத்துகளைக் கொண்டுள்ளன என்ற பண்புக்கு இது "வெளிப்படையாக சமமானது" என்று பிளம்மர் எழுதுகிறார். ஒரு வரைபடத்தில் ஒரு சுயாதீன தொகுப்பு என்பது செங்குத்துகளின் தொகுப்பாகும், அவற்றில் இரண்டு ஒன்றுக்கொன்று அருகில் இல்லை. ஒரு வரைபடத்தில் ஒரு உச்சி உறை இருந்தால், அதன் நிரப்பு ஒரு சுயாதீனமான தொகுப்பாக இருக்க வேண்டும், அதற்கு நேர்மாறாகவும் இருக்க வேண்டும். அதன் நிரப்பு அதிகபட்ச சுயாதீன தொகுப்பாக இருந்தால் மட்டுமே குறைந்தபட்ச உச்சி உறை ஆகும், மேலும் அதன் நிரப்பு அதிகபட்ச சுயாதீன தொகுப்பாக இருந்தால் மட்டுமே குறைந்தபட்ச உச்சி உறை ஆகும். எனவே, நன்கு மூடப்பட்ட வரைபடம், சமமாக, ஒவ்வொரு அதிகபட்ச சுயாதீன தொகுப்பும் ஒரே அளவைக் கொண்ட ஒரு வரைபடம், அல்லது ஒவ்வொரு அதிகபட்ச சுயாதீன தொகுப்பும் அதிகபட்சமாக இருக்கும் வரைபடம். நன்கு மூடப்பட்ட வரைபடங்களை வரையறுக்கும் அசல் காகிதத்தில், இந்த வரையறைகள் இணைக்கப்பட்ட வரைபடங்களுக்கு மட்டுப்படுத்தப்பட்டன, இருப்பினும் அவை துண்டிக்கப்பட்ட வரைபடங்களுக்கும் அர்த்தமுள்ளவை. சில பிற்கால எழுத்தாளர்கள் இணைப்புத் தேவையை பலவீனமான தேவையுடன் மாற்றியுள்ளனர், நன்கு மூடப்பட்ட வரைபடம் எந்த தனிமைப்படுத்தப்பட்ட செங்குத்துகளையும் கொண்டிருக்கக்கூடாது. இணைக்கப்பட்ட நன்கு மூடப்பட்ட வரைபடங்கள் மற்றும் தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாமல் நன்கு மூடப்பட்ட வரைபடங்கள் ஆகிய இரண்டிற்கும், ஒவ்வொரு குறைந்தபட்ச உச்சி மறைப்புக்கும் சொந்தமான அத்தியாவசிய செங்குத்துகள், செங்குத்துகள் எதுவும் இருக்க முடியாது. கூடுதலாக, நன்கு மூடப்பட்ட ஒவ்வொரு வரைபடமும் உச்சியை மறைப்பதற்கான ஒரு முக்கியமான வரைபடமாகும், அதாவது, ஒவ்வொரு உச்சிக்கும், வரைபடத்திலிருந்து நீக்குவது சிறிய குறைந்தபட்ச உச்சி மறைப்புடன் ஒரு வரைபடத்தை உருவாக்குகிறது. ஒரு வரைபடத்தின் சுதந்திர வளாகம் என்பது ஒவ்வொரு சுயாதீன செட்டுக்கும் ஒரு சிம்ப்ளக்ஸ் கொண்ட எளிய வளாகமாகும். ஒரு எளிய சிக்கலானது அதன் அதிகபட்ச எளிமைகள் அனைத்தும் ஒரே கார்டினாலிட்டியைக் கொண்டிருந்தால் தூய்மையானது என்று கூறப்படுகிறது, எனவே நன்கு மூடப்பட்ட வரைபடம் என்பது தூய சுதந்திர சிக்கலான வரைபடத்திற்கு சமம். எடுத்துக்காட்டுகள் நான்கு அல்லது ஐந்து நீளம் கொண்ட ஒரு சுழற்சி வரைபடம் நன்கு மூடப்பட்டுள்ளதுஃ ஒவ்வொரு சந்தர்ப்பத்திலும், ஒவ்வொரு அதிகபட்ச சுயாதீன தொகுப்பும் அளவு இரண்டைக் கொண்டுள்ளது. ஏழு நீளம் கொண்ட ஒரு சுழற்சியும், மூன்று நீளம் கொண்ட ஒரு பாதையும் நன்கு மூடப்பட்டுள்ளன. ஒவ்வொரு முழுமையான வரைபடமும் நன்கு மூடப்பட்டுள்ளதுஃ ஒவ்வொரு அதிகபட்ச சுயாதீன தொகுப்பும் ஒரு ஒற்றை உச்சியைக் கொண்டுள்ளது. இதேபோல், ஒவ்வொரு கிளஸ்டர் வரைபடமும் (முழுமையான வரைபடங்களின் வேறுபட்ட ஒன்றிணைப்பு) நன்கு மூடப்பட்டிருக்கும். ஒரு முழுமையான இருதரப்பு வரைபடம் அதன் இருபங்குகளின் இரு பக்கங்களும் சம எண்ணிக்கையிலான செங்குத்துகளைக் கொண்டிருந்தால் நன்கு மூடப்பட்டிருக்கும், ஏனெனில் இவை அதன் அதிகபட்ச இரண்டு சுயாதீன தொகுப்புகள் மட்டுமே. தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாத முக்கோண-இல்லாத வரைபடத்தின் நிரப்பு வரைபடம் நன்கு மூடப்பட்டுள்ளதுஃ இது இரண்டுக்கு மேற்பட்ட சுயாதீன தொகுப்புகளைக் கொண்டிருக்கவில்லை, மேலும் ஒவ்வொரு உச்சியையும் இரண்டு-வெர்டெக்ஸ் சுயாதீன தொகுப்புக்கு நீட்டிக்க முடியும். ஒரு ரூக்கின் வரைபடம் நன்கு மூடப்பட்டிருக்கும்ஃ இரண்டு ரூக்குகள் ஒருவருக்கொருவர் தாக்காமல் இருக்க ஒரு சதுரங்கப் பலகையில் ஏதேனும் ரூக்குகளை வைத்தால், சதுரங்கப் பலகையின் ஒவ்வொரு வரிசையிலும் நெடுவரிசையிலும் ஒன்று இருக்கும் வரை அதிக தாக்குதல் இல்லாத ரூக்குகளை தொடர்ந்து வைக்க முடியும். செங்குத்துகள் ஒரு எளிய பலகோணத்தின் மூலைவிட்டங்களாக இருக்கும் வரைபடம் மற்றும் அதன் விளிம்புகள் ஒருவருக்கொருவர் கடக்கும் மூலைவிட்ட ஜோடிகளை இணைக்கின்றன, ஏனெனில் அதன் அதிகபட்ச சுயாதீன தொகுப்புகள் பலகோணத்தின் முக்கோணங்கள் மற்றும் அனைத்து முக்கோணங்களும் ஒரே எண்ணிக்கையிலான விளிம்புகளைக் கொண்டுள்ளன. ஏதேனும்-வெர்டெக்ஸ் வரைபடம் இருந்தால், ஒரு முனை வரைபடத்துடன் வேரூன்றிய பெருக்கல் (அதாவது, புதிய செங்குத்துகளைச் சேர்ப்பதன் மூலம் உருவாக்கப்பட்ட வரைபடம், ஒவ்வொன்றும் டிகிரி ஒன்று மற்றும் ஒவ்வொன்றும் ஒரு தனித்துவமான உச்சிக்கு அருகில்) நன்கு மூடப்பட்டிருக்கும். ஏனெனில், ஒரு அதிகபட்ச சுயாதீன தொகுப்பு நிரப்பு தொகுப்பின் டிகிரி-ஒன் அண்டை நாடுகளுடன் சேர்ந்து ஒரு தன்னிச்சையான சுயாதீன தொகுப்பைக் கொண்டிருக்க வேண்டும், எனவே அளவு இருக்க வேண்டும். மேலும் பொதுவாக, எந்தவொரு வரைபடத்தையும் ஒரு கிளிக்குடன் (கிளிக்குகளில் செங்குத்துகளின் பகிர்வு) ஒன்றாக கொடுக்கப்பட்டால், ஒவ்வொரு கிளிக்கிலும் மற்றொரு உச்சியை சேர்ப்பதன் மூலம் உருவாக்கப்பட்ட வரைபடம் நன்கு மூடப்பட்டிருக்கும்; ஒரு வெர்டெக்ஸ் கிளிக்குகளைக் கொண்டிருக்கும்போது வேரூன்றிய தயாரிப்பு இந்த கட்டமைப்பின் சிறப்பு நிகழ்வாகும். எனவே, ஒவ்வொரு வரைபடமும் நன்கு மூடப்பட்ட வரைபடத்தின் தூண்டப்பட்ட துணை வரைபடமாகும். இருதரப்பு, நன்கு மூடப்பட்ட வரைபடங்கள் மற்றும் சுற்றளவு ஆகியவை நன்கு மூடப்பட்ட வரைபடத்தை நன்கு மூடப்பட்ட வரைபடமாக வரையறுக்கின்றன (ஒருவேளை துண்டிக்கப்பட்டிருக்கலாம், ஆனால் தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாமல்) இதில் ஒவ்வொரு அதிகபட்ச சுயாதீன தொகுப்பும் (எனவே ஒவ்வொரு குறைந்தபட்ச உச்சி மறைப்பும்) சரியாக பாதி செங்குத்துகளைக் கொண்டுள்ளது. இந்த வரையறை ஒரு வரைபடத்தின் வேரூன்றிய தயாரிப்புகள் மற்றும் ஒரு முனை வரைபடத்தை உள்ளடக்கியது. உதாரணமாக, இருதரப்பு நன்கு மூடப்பட்ட வரைபடங்களும் இதில் அடங்கும்ஃ தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாமல் இருதரப்பு வரைபடத்தில், எந்தவொரு இருதரப்பு வடிவத்தின் இரு பக்கங்களும் அதிகபட்ச சுயாதீன தொகுப்புகளை (மற்றும் குறைந்தபட்ச உச்சி உறைகள்) உருவாக்குகின்றன, எனவே வரைபடம் நன்கு மூடப்பட்டிருந்தால் இரு பக்கங்களும் சமமாக பல செங்குத்துகளைக் கொண்டிருக்க வேண்டும். செங்குத்துகளுடன் நன்கு மூடப்பட்ட வரைபடத்தில், தனிமைப்படுத்தப்பட்ட செங்குத்துகள் இல்லாமல், அதிகபட்ச சுயாதீன தொகுப்பின் அளவு அதிகபட்சமாக இருக்கும், எனவே நன்கு மூடப்பட்ட வரைபடங்கள் நன்கு மூடப்பட்ட வரைபடங்களாகும், இதில் அதிகபட்ச சுயாதீன தொகுப்பு அளவு முடிந்தவரை பெரியதாக இருக்கும். ஒவ்வொரு விளிம்பிற்கும், அண்டை நாடுகளின் தூண்டப்பட்ட துணை வரைபடம் மற்றும் ஒரு முழுமையான இருதரப்பு வரைபடத்தை உருவாக்கும் பண்புடன் சரியான பொருத்தத்தைக் கொண்டிருந்தால் மட்டுமே இருதரப்பு வரைபடம் நன்கு மூடப்பட்டிருக்கும். பொருத்தங்களின் அடிப்படையில் குணாதிசயத்தை இருதரப்பு வரைபடங்களிலிருந்து நன்கு மூடப்பட்ட வரைபடங்களுக்கு நீட்டிக்க முடியும்ஃ பின்வரும் இரண்டு பண்புகளுடன் சரியான பொருத்தம் இருந்தால் மட்டுமே ஒரு வரைபடம் நன்கு மூடப்பட்டிருக்கும்ஃ முக்கோணத்தின் எந்த விளிம்பும் ஒரு முக்கோணத்திற்கு சொந்தமானது அல்ல, மற்றும் ஒரு விளிம்பு மூன்று விளிம்பு பாதையின் மைய விளிம்பாக இருந்தால், பாதையின் இரண்டு இறுதிப் புள்ளிகளும் அருகிலேயே இருக்க வேண்டும். மேலும், நன்கு மூடப்பட்டிருந்தால், ஒவ்வொரு சரியான பொருத்தமும் இந்த பண்புகளை திருப்திப்படுத்துகிறது. மரங்கள் இருதரப்பு வரைபடங்களின் ஒரு சிறப்பு வழக்கு, மேலும் ஒரு மரம் நன்கு மூடப்பட்டிருக்கிறதா என்பதைச் சோதிப்பது நன்கு மூடப்பட்ட இருதரப்பு வரைபடங்களின் குணாதிசயத்தின் மிகவும் எளிமையான சிறப்பு நிகழ்வாக கையாளப்படலாம்ஃ இரண்டுக்கும் மேற்பட்ட செங்குத்துகளைக் கொண்ட ஒரு மரம் என்றால், மரத்தின் ஒவ்வொரு இலை அல்லாத முனையும் சரியாக ஒரு இலைக்கு அருகில் இருந்தால் மட்டுமே அது நன்கு மூடப்பட்டிருக்கும். அதே தன்மை உள்ளூரில் மரம் போன்ற வரைபடங்களுக்கும் பொருந்தும், அதாவது ஒவ்வொரு உச்சியின் குறைந்த விட்டம் கொண்ட சுற்றுப்புறங்களும் அசைக்லிக் ஆகும்ஃ ஒரு வரைபடம் எட்டு அல்லது அதற்கு மேற்பட்ட சுற்றளவைக் கொண்டிருந்தால் (இதனால், ஒவ்வொரு உச்சிக்கும், மூன்று தூரத்திற்குள் உள்ள செங்குத்துகளின் துணை வரைபடம் அசைக்லிக் ஆகும்) பின்னர், ஒன்றுக்கு மேற்பட்ட டிகிரியின் ஒவ்வொரு உச்சியும் சரியாக ஒரு டிகிரி ஒன்றைக் கொண்டிருந்தால் மட்டுமே அது நன்கு மூடப்பட்டிருக்கும். நெருங்கிய தொடர்புடைய ஆனால் மிகவும் சிக்கலான தன்மை ஐந்து அல்லது அதற்கு மேற்பட்ட சுற்றளவு நன்கு மூடப்பட்ட வரைபடங்களுக்கு பொருந்தும். சீரான தன்மை மற்றும் தெளிவான தன்மை கனசதுர (3-சீரான) நன்கு மூடப்பட்ட வரைபடங்கள் வகைப்படுத்தப்பட்டுள்ளனஃ அவை ஏழு 3-இணைக்கப்பட்ட எடுத்துக்காட்டுகளைக் கொண்டுள்ளன, அதோடு குறைந்த இணைப்பைக் கொண்ட கனசதுர வரைபடங்களின் மூன்று எல்லையற்ற குடும்பங்களும் உள்ளன. ஏழு 3-இணைக்கப்பட்ட கனசதுர நன்கு மூடப்பட்ட வரைபடங்கள் முழுமையான வரைபடம், முக்கோண ப்ரிஸம் மற்றும் ஐங்கோண ப்ரிஸத்தின் வரைபடங்கள், டுரர் வரைபடம், பயன்பாட்டு வரைபடம், ஒய்-டி உருமாற்றத்தால் பயன்பாட்டு வரைபடத்திலிருந்து பெறப்பட்ட எட்டு-வெர்டெக்ஸ் வரைபடம் மற்றும் 14-வெர்டெக்ஸ் பொதுமைப்படுத்தப்பட்ட பீட்டர்சன் வரைபடம் ஆகும். இந்த வரைபடங்களில், முதல் நான்கு சமதள வரைபடங்கள் ஆகும். அவை மட்டுமே நன்கு மூடப்பட்டிருக்கும் நான்கு கன பாலிஹெட்ரல் வரைபடங்கள் (எளிய குவிந்த பாலிஹெட்ராவின் வரைபடங்கள்) ஆகும். நான்கு வரைபடங்கள் (இரண்டு முக்கோணங்கள், டுரர் வரைபடம் மற்றும்) பீட்டர்சன் வரைபடங்களாக பொதுமைப்படுத்தப்பட்டுள்ளன. 1 மற்றும் 2 இணைக்கப்பட்ட கனசதுர நன்கு மூடப்பட்ட வரைபடங்கள் அனைத்தும் ஒரு பாதை அல்லது சுழற்சியின் முனைகளை மூன்று துண்டுகள் வரைபடங்களால் மாற்றுவதன் மூலம் உருவாகின்றன, அவை லேபிள்கள், மற்றும். துண்டுகள் அல்லது ஒரு சுழற்சியின் முனைகள் அல்லது ஒரு பாதையின் உட்புற முனைகளை மாற்ற பயன்படுத்தப்படலாம், அதே நேரத்தில் ஒரு பாதையின் இரண்டு முனை முனைகளை மாற்ற துண்டு பயன்படுத்தப்படுகிறது. துண்டு ஒரு பாலத்தைக் கொண்டுள்ளது, எனவே ஒரு பாதையில் இந்த மாற்று செயல்முறையைச் செய்வதன் விளைவாகவும், சில பாதை முனைகளை (மற்றும் மீதமுள்ள முனைகளுக்கான மற்ற இரண்டு துண்டுகள்) மாற்றுவதற்கு துண்டுகளைப் பயன்படுத்துவதன் விளைவாகவும் 1-வெர்டெக்ஸ்-இணைக்கப்பட்ட கனசதுரம் நன்கு மூடப்பட்ட வரைபடமாகும். அனைத்து 1-வெர்டெக்ஸ்-இணைக்கப்பட்ட கியூபிக் நன்கு மூடப்பட்ட வரைபடங்களும் இந்த வடிவத்தைக் கொண்டுள்ளன, மேலும் அத்தகைய வரைபடங்கள் அனைத்தும் சமதளமாக உள்ளன. இரண்டு வகையான 2-வெர்டெக்ஸ்-இணைக்கப்பட்ட கியூபிக் நன்கு மூடப்பட்ட வரைபடங்கள் உள்ளன. இந்த இரண்டு குடும்பங்களில் ஒன்று ஒரு சுழற்சியின் முனைகளை துண்டுகளால் மாற்றுவதன் மூலம் உருவாகிறது, மேலும் குறைந்தது இரண்டு துண்டுகள் வகையாக இருக்கும்; இந்த வகையின் வரைபடம் எந்த வகையான துண்டுகளையும் கொண்டிருக்காவிட்டால் மட்டுமே சமதளமாக இருக்கும். மற்ற குடும்பம் ஒரு பாதையின் முனைகளை வகை துண்டுகளால் மாற்றுவதன் மூலம் உருவாகிறது மற்றும் அத்தகைய வரைபடங்கள் அனைத்தும் சமதளமாக உள்ளன. மூன்று பரிமாணங்களில் நன்கு மூடப்பட்ட எளிய பாலிஹெட்ராவின் குணாதிசயத்தை பூர்த்தி செய்யும் வகையில், ஆராய்ச்சியாளர்கள் நன்கு மூடப்பட்ட எளிய பாலிஹெட்ரா அல்லது அதற்கு சமமாக நன்கு மூடப்பட்ட அதிகபட்ச பிளானர் வரைபடங்களையும் கருத்தில் கொண்டுள்ளனர். ஐந்து அல்லது அதற்கு மேற்பட்ட செங்குத்துகளைக் கொண்ட ஒவ்வொரு அதிகபட்ச சமதள வரைபடமும் 3,4 அல்லது 5 உச்சி இணைப்பைக் கொண்டுள்ளது. நன்கு மூடப்பட்ட 5-இணைக்கப்பட்ட அதிகபட்ச பிளானர் வரைபடங்கள் எதுவும் இல்லை, மேலும் நான்கு 4-இணைக்கப்பட்ட நன்கு மூடப்பட்ட அதிகபட்ச பிளானர் வரைபடங்கள் மட்டுமே உள்ளனஃ வழக்கமான எண்முகத்தின் வரைபடங்கள், ஐங்கோண இருமுனை, ஸ்னப் டிஸ்பீனாய்டு மற்றும் 12 செங்குத்துகள், 30 விளிம்புகள் மற்றும் 20 முக்கோண முகங்களைக் கொண்ட ஒரு ஒழுங்கற்ற பாலிஹெட்ரான் (ஒரு கன்வெக்ஸ் அல்லாத டெல்டா ஹெட்ரான்). இருப்பினும், எண்ணற்ற பல 3-இணைக்கப்பட்ட நன்கு மூடப்பட்ட அதிகபட்ச சமதள வரைபடங்கள் உள்ளன. உதாரணமாக, ஒரு-வெர்டெக்ஸ் அதிகபட்ச பிளானர் வரைபடம் வேறுபட்ட முக்கோண முகங்களைக் கொண்டிருந்தால், இந்த முகங்கள் ஒரு கிளிக் அட்டையை உருவாக்கும். எனவே, இந்த வரைபடங்களுக்கான கிளைக் கவர் கட்டுமானம், இந்த முக்கோணங்கள் ஒவ்வொன்றையும் ஒரு மைய உச்சியில் சந்திக்கும் மூன்று புதிய முக்கோணங்களாகப் பிரித்து, நன்கு மூடப்பட்ட அதிகபட்ச பிளானர் வரைபடத்தை உருவாக்குகிறது. ஒரு வரைபடம் வெவ்வேறு அளவுகளில் இரண்டு அதிகபட்ச சுயாதீன தொகுப்புகளைக் கொண்டிருக்கிறதா என்பதைச் சரிபார்ப்பது NP-முழுமையானது; அதாவது, ஒரு வரைபடம் நன்கு மூடப்பட்டிருக்கிறதா என்பதைச் சரிபார்ப்பது CoNP-முழுமையானது. நன்கு மூடப்பட்டதாக அறியப்படும் வரைபடங்களில் அதிகபட்ச சுயாதீன தொகுப்புகளைக் கண்டுபிடிப்பது எளிதானது என்றாலும், அனைத்து வரைபடங்களிலும், அதிகபட்ச சுயாதீன தொகுப்பாகவோ அல்லது உள்ளீடு இல்லை என்பதற்கான உத்தரவாதமாகவோ ஒரு வழிமுறை வெளியீடாக உருவாக்குவது NP-கடினம். இதற்கு மாறாக, கொடுக்கப்பட்ட வரைபடம் பல்லுறுப்புக்கோவை நேரத்தில் நன்கு மூடப்பட்டிருக்கிறதா என்பதை சோதிக்க முடியும். அவ்வாறு செய்ய, நன்கு மூடப்பட்ட வரைபடத்தில் பொருந்திய விளிம்பின் இரண்டு பண்புகளை திருப்திப்படுத்தும் விளிம்புகளைக் கொண்ட துணை வரைபடத்தைக் கண்டறியவும், பின்னர் சரியான பொருத்தம் உள்ளதா என்பதை சோதிக்க பொருத்தமான வழிமுறையைப் பயன்படுத்தவும். தன்னிச்சையான வரைபடங்களுக்கு NP-முழுமையான சில சிக்கல்கள், ஹாமில்டோனியன் சுழற்சியைக் கண்டுபிடிப்பதில் உள்ள சிக்கல் போன்றவை, நன்கு மூடப்பட்ட வரைபடங்களுக்கு பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கப்படலாம். ஒவ்வொரு அதிகபட்ச பொருத்தமும் அதிகபட்சமாக இருந்தால் ஒரு வரைபடம் சமமானதாகக் கூறப்படுகிறது; அதாவது, அதன் வரி வரைபடம் நன்கு மூடப்பட்டிருந்தால் அது சமமானதாக இருக்கும். ஒவ்வொரு அதிகபட்ச பொருத்தமும் சரியான பொருத்தமாக இருந்தால் அது சீரற்ற முறையில் பொருந்தக்கூடியது என்று அழைக்கப்படுகிறது. சீரற்ற முறையில் பொருந்தக்கூடிய ஒரே இணைக்கப்பட்ட வரைபடங்கள் முழுமையான வரைபடங்கள் மற்றும் சீரான முழுமையான இருதரப்பு வரைபடங்கள் ஆகும். ஒரு வரி வரைபடம், அல்லது பொதுவாக ஒரு நகம் இல்லாத வரைபடம், பல்லுறுப்புக்கோவை நேரத்தில் நன்கு மூடப்பட்டிருக்கிறதா என்பதை சோதிக்க முடியும். ஐந்து அல்லது அதற்கு மேற்பட்ட சுற்றளவு கொண்ட நன்கு மூடப்பட்ட வரைபடங்களின் குணாதிசயங்களும், 3-ஒழுங்கான நன்கு மூடப்பட்ட வரைபடங்களும் இந்த வரைபடங்களை அடையாளம் காண திறமையான பல்லுறுப்புக்கோவை நேர வழிமுறைகளுக்கு வழிவகுக்கின்றன. குறிப்புகள் குறிப்புகள். . மேற்கோள் காட்டியபடி. . . . . . . . . . . . . . . . . . . . . . . . . மேற்கோள் காட்டியபடி. . . . வரைபடக் குடும்பங்கள்