Dense subgraph
வரைபடக் கோட்பாடு மற்றும் கணினி அறிவியலில், அடர்த்தியான துணை வரைபடம் என்பது ஒரு உச்சிக்கு பல விளிம்புகளைக் கொண்ட ஒரு துணை வரைபடமாகும். இது பின்வருமாறு முறைப்படுத்தப்பட்டுள்ளதுஃ ஒரு திசைதிருப்பப்படாத வரைபடமாக இருக்கட்டும் மற்றும் ஒரு துணை வரைபடமாக இருக்கட்டும். பின்னர் அதன் அடர்த்தி பின்வருமாறு வரையறுக்கப்படுகிறதுஃ அடர்த்தியான துணை வரைபட சிக்கல் அதிகபட்ச அடர்த்தி கொண்ட ஒரு துணை வரைபடத்தைக் கண்டுபிடிப்பதாகும். ஒரு வரைபடத்தின் அதிகபட்ச அடர்த்தியான துணை வரைபடத்தின் அடர்த்தி சில நேரங்களில் அதன் துணை வரைபட அடர்த்தி என்று குறிப்பிடப்படுகிறது. 1984 ஆம் ஆண்டில், ஆண்ட்ரூ வி. கோல்ட்பர்க் ஒரு அதிகபட்ச ஓட்ட நுட்பத்தைப் பயன்படுத்தி அதிகபட்ச அடர்த்தி துணை வரைபடத்தைக் கண்டறிய ஒரு பல்லுறுப்புக்கோவை நேர வழிமுறையை உருவாக்கினார். இது 1989 ஆம் ஆண்டில் காலோ, கிரிகோரியாடிஸ் மற்றும் டார்ஜன் ஆகியோரால் சரியான நேரத்தில் இயங்க மேம்படுத்தப்பட்டுள்ளது. உகந்த தீர்வை கண்டுபிடிப்பதற்கான ஒரு எளிய எல்பி 2000 ஆம் ஆண்டில் சாரிகரால் வழங்கப்பட்டது. சப் கிராஃப் அடர்த்தி என்பது ஆர்பரிஸிட்டி மற்றும் கிராஃப் சிதைவு தொடர்பான கருத்துக்கு அறிகுறியற்றது. அடர்த்தியான சப் கிராஃப் சிக்கலில் பல வேறுபாடுகள் உள்ளன. அவற்றில் ஒன்று அடர்த்தியான சப் கிராஃப் சிக்கலாகும், அங்கு சரியான செங்குத்துகளில் அதிகபட்ச அடர்த்தி சப் கிராஃப்பைக் கண்டுபிடிப்பதே நோக்கம். இந்த சிக்கல் கிளைக் சிக்கலை பொதுமைப்படுத்துகிறது, இதனால் பொதுவான வரைபடங்களில் NP-கடினமானது. ஒவ்வொன்றிற்கும் ஒரு விகிதத்திற்குள் அடர்த்தியான துணை வரைபடத்தை தோராயமாக மதிப்பிடும் ஒரு பல்லுறுப்புக்கோவை வழிமுறை உள்ளது, அதே நேரத்தில் அதிவேக நேர கருதுகோள் தவறாக இல்லாவிட்டால் அது பல்லுறுப்புக்கோவை நேரத்தில் ஒரு-ஒப்பீட்டை ஒப்புக்கொள்ளாது. ஒரு பலவீனமான அனுமானத்தின் கீழ், சிக்கலுக்கு பி. டி. ஏ. எஸ் இல்லை. இருதரப்பு வரைபடங்கள் மற்றும் கார்டல் வரைபடங்களில் சிக்கல் NP-கடினமாக உள்ளது, ஆனால் மரங்கள் மற்றும் பிளவு வரைபடங்களுக்கு பல்லுறுப்புக்கோவை ஆகும். (சரியான) இடைவெளி வரைபடங்கள் மற்றும் பிளானர் வரைபடங்களில் சிக்கல் NP-கடினமானதா அல்லது பல்லுறுப்புக்கோவையாக இருக்கிறதா என்பது திறந்திருக்கும்; இருப்பினும், துணை வரைபடத்தை இணைக்க வேண்டிய சிக்கலின் மாறுபாடு பிளானர் வரைபடங்களில் NP-கடினமானது. பெரும்பாலான துணை வரைபடத்தில் அடர்த்தியானது அடர்த்தியான சிக்கலின் நோக்கம் பெரும்பாலான செங்குத்துகளில் அதிகபட்ச அடர்த்தி கொண்ட துணை வரைபடத்தைக் கண்டுபிடிப்பதாகும். ஆண்டர்சன் மற்றும் செல்லாபில்லா ஆகியோர் இந்த சிக்கலுக்கு ஒரு-ஒப்பீடு இருந்தால், அது அடர்த்தியான துணை வரைபட சிக்கலுக்கு ஒரு-ஒப்புதலுக்கு வழிவகுக்கும் என்பதைக் காட்டினர். அடர்த்தியான குறைந்தபட்சம் சப் கிராஃப் குறைந்தபட்சம் சிக்கல் பெரும்பாலான சப் கிராஃப் சிக்கலில் அடர்த்தியானதைப் போலவே வரையறுக்கப்படுகிறது. சிக்கல் NP-முழுமையானது, ஆனால் பல்லுறுப்புக்கோவை நேரத்தில் 2-இணக்கத்தை ஒப்புக்கொள்கிறது. மேலும், இந்த தோராயமான வழிமுறை அடிப்படையில் சாத்தியமான சிறந்தது என்பதற்கு சில சான்றுகள் உள்ளனஃ சிறிய தொகுப்பு விரிவாக்க கருதுகோளை (தனித்துவமான விளையாட்டு அனுமானத்துடன் நெருக்கமாக தொடர்புடைய ஒரு கணக்கீட்டு சிக்கலான அனுமானம்) கருதினால், ஒவ்வொரு மாறிலிக்கும் காரணிக்குள் சிக்கலை தோராயமாக மதிப்பிடுவது NP-கடினம். - கிளிக் அடர்த்தியான துணை வரைபடம் சராலம்போஸ் சௌராகாகிஸ்-கிளிக் அடர்த்தியான துணை வரைபட சிக்கலை அறிமுகப்படுத்தினார். அடர்த்தியான சப் கிராஃப் சிக்கலின் இந்த மாறுபாடு தூண்டப்பட்ட கிளிக்குகளின் சராசரி எண்ணிக்கையை அதிகரிப்பதை நோக்கமாகக் கொண்டுள்ளது, இதில்-கிளிக்குகளின் தொகுப்பு தூண்டப்படுகிறது. அடர்த்தியான சப் கிராஃப் சிக்கல் ஒரு சிறப்பு நிகழ்வாக பெறப்படுகிறது என்பதைக் கவனியுங்கள். இந்த பொதுமைப்படுத்தல் பெரிய அளவிலான நிஜ உலக நெட்வொர்க்குகளிலிருந்து பெரிய நெருக்கமான கிளிக்குகளை பிரித்தெடுப்பதற்கான அனுபவ ரீதியாக வெற்றிகரமான பாலி-டைம் அணுகுமுறையை வழங்குகிறது. உள்ளூர் அளவில் மிக அடர்த்தியான துணை வரைபடம் கின் மற்றும் பலர். ஒரு வரைபடத்தில் உள்ளூரில் அடர்த்தியான துணை வரைபடக் கண்டுபிடிப்பின் சிக்கலை அறிமுகப்படுத்தியது, அவை ஒவ்வொன்றும் வரைபடத்தில் அதன் உள்ளூர் பகுதியில் மிக உயர்ந்த அடர்த்தியை அடைகின்றனஃ இது அதே அல்லது பெரிய அடர்த்தியுடன் எந்த சூப்பர் கிராஃப்பிலும் இல்லை, அல்லது அடர்த்தி கொண்ட துணை வரைபடங்களைக் கொண்டிருக்கவில்லை உள்ளூர் அடர்த்தியான துணை வரைபடத்துடன் தளர்வாக இணைக்கப்பட்டுள்ளது. அடர்த்தியான சப் கிராஃப் சிக்கல் ஒரு சிறப்பு நிகழ்வாக பெறப்படுகிறது என்பதை நினைவில் கொள்க. ஒரு வரைபடத்தில் உள்ளூரில் அடர்த்தியான துணை வரைபடங்களின் தொகுப்பை பல்லுறுப்புக்கோவை நேரத்தில் கணக்கிட முடியும். குறிப்புகள் மேலும் வாசிப்பு. . . . . வரைபடக் கோட்பாடு