Bipartite dimension
வரைபடக் கோட்பாடு மற்றும் ஒருங்கிணைந்த உகப்பாக்கம் ஆகியவற்றின் கணிதத் துறைகளில், G = (V, E) என்ற வரைபடத்தின் இருதரப்பு பரிமாணம் அல்லது இருதரப்பு கவர் எண் என்பது குறைந்தபட்ச இருதரப்பு எண்ணிக்கையாகும் (அதாவது முழுமையான இருதரப்பு துணை வரைபடங்கள்), இது E இல் உள்ள அனைத்து விளிம்புகளையும் மறைக்க தேவைப்படுகிறது. G இல் உள்ள அனைத்து விளிம்புகளையும் உள்ளடக்கிய இருதரப்பு தொகுப்பு இருதரப்பு விளிம்பு கவர் அல்லது சில நேரங்களில் இருதரப்பு கவர் என்று அழைக்கப்படுகிறது. G இன் இருதரப்பு பரிமாணம் பெரும்பாலும் d (G) குறியீட்டால் குறிக்கப்படுகிறது. எடுத்துக்காட்டு ஒரு இருசக்கர விளிம்பு மறைப்புக்கு ஒரு எடுத்துக்காட்டு பின்வரும் வரைபடங்களில் கொடுக்கப்பட்டுள்ளதுஃ சில வரைபடங்களுக்கான இருதரப்பு பரிமாண சூத்திரங்கள் n-வெர்டெக்ஸ் முழுமையான வரைபடத்தின் இருதரப்பு பரிமாணம், ஆகும். 2n-வெர்டெக்ஸ் கிரீடம் வரைபடத்தின் இருதரப்பு பரிமாணம் சமம், இது மைய இருமக் குணகத்தின் தலைகீழ் செயல்பாடு ஆகும். லட்டிஸ் வரைபடத்தின் இருதரப்பு பரிமாணம், சமமாக இருந்தால் மற்றும் சில முழு எண்களுக்கு; மற்றும் வேறுவிதமாக உள்ளது. சில சிறப்பு வரைபடங்களுக்கான இருதரப்பு பரிமாணத்தை தீர்மானிக்கவும். எடுத்துக்காட்டாக, பாதை உள்ளது மற்றும் சுழற்சி உள்ளது. இருதரப்பு பரிமாணத்தை கணக்கிடுவது கொடுக்கப்பட்ட G வரைபடத்திற்கான இருதரப்பு பரிமாணத்தை தீர்மானிக்கும் கணக்கீட்டு பணி ஒரு உகப்பாக்கம் சிக்கலாகும். இருதரப்பு பரிமாணத்திற்கான முடிவு சிக்கலை பின்வருமாறு சொல்லலாம்ஃ இன்ஸ்டன்ஸ்ஃ ஒரு வரைபடம் மற்றும் ஒரு நேர்மறை முழு எண். கேள்விஃ பெரும்பாலான இருகுழாய்களைக் கொண்ட இருகுழாய் விளிம்பு உறையை ஜி ஒப்புக்கொள்கிறாரா? இந்த சிக்கல் கரே மற்றும் ஜான்சனின் NP-முழுமை குறித்த கிளாசிக்கல் புத்தகத்தில் GT18 சிக்கலாகத் தோன்றுகிறது, மேலும் இது வரையறுக்கப்பட்ட தொகுப்புகளின் குடும்பங்களில் மற்றொரு முடிவு சிக்கலின் நேரடியான மறுசீரமைப்பாகும். கரே மற்றும் ஜான்சனின் புத்தகத்தில் எஸ். பி. 7 சிக்கலாக செட் அடிப்படை சிக்கல் தோன்றுகிறது. இங்கே, ஒரு வரையறுக்கப்பட்ட தொகுப்பின் துணைக்குழுக்களின் குடும்பத்திற்கு, ஒரு தொகுப்பு அடிப்படை என்பது மற்றொரு துணைக்குழுக்களின் குடும்பமாகும், அதாவது ஒவ்வொரு தொகுப்பையும் சில அடிப்படை கூறுகளின் ஒன்றிணைப்பு என்று விவரிக்க முடியும். செட் அடிப்படை சிக்கல் இப்போது பின்வருமாறு கொடுக்கப்பட்டுள்ளதுஃ இன்ஸ்டன்ஸ்ஃ ஒரு வரையறுக்கப்பட்ட தொகுப்பு, துணைக்குழுக்களின் குடும்பம் மற்றும் ஒரு நேர்மறை முழு எண் k. கேள்விஃ அதிகபட்சமாக அளவின் ஒரு செட் அடிப்படை இருக்கிறதா? அதன் முந்தைய சூத்திரத்தில், இருதரப்பு வரைபடங்களுக்கு கூட, சிக்கல் NP-முழுமையானது என்று நிரூபிக்கப்பட்டது. ஒரு தொகுப்பு அடிப்படையிலான சிக்கலாக உருவாக்கம் முன்பு NP-முழுமையானது என்று நிரூபிக்கப்பட்டது. கொடுக்கப்பட்ட சிக்கல் நிகழ்வின் அளவைக் குறிக்கும் n உடன், இருதரப்பு பரிமாணம் அதிகபட்சமாக இருக்கும் என்று உத்தரவாதம் அளிக்கப்பட்ட இருதரப்பு வரைபடங்களுக்கு நம் கவனத்தை மட்டுப்படுத்தினாலும் சிக்கல் NP-கடினமாக உள்ளது. நேர்மறையான பக்கத்தில், இருதரப்பு டோமினோ இல்லாத வரைபடங்களில் பல்லுறுப்புக்கோவை நேரத்தில் சிக்கலை தீர்க்க முடியும். தோராயமான வழிமுறைகளின் இருப்பைப் பொறுத்தவரை, சிக்கலை நன்கு தோராயமாக மதிப்பிட முடியாது என்பதை நிரூபித்தது (P § NP என்று வைத்துக் கொள்ளுங்கள்). உண்மையில், இருதரப்பு பரிமாணம் NP-கடினமானது, ஏற்கனவே இருதரப்பு வரைபடங்களுக்கு, ஒவ்வொரு நிலைக்குள்ளும் தோராயமாக மதிப்பிடப்படுகிறது. இதற்கு மாறாக, சிக்கல் நிலையான-அளவுரு கையாளக்கூடியது என்பதை நிரூபிப்பது கர்னலைசேஷன் வழிமுறைகளை வடிவமைப்பதில் ஒரு பயிற்சியாகும், இது பாடப்புத்தகத்தில் இவ்வாறு தோன்றுகிறது. இதன் விளைவாக வரும் கர்னலின் அளவில் ஒரு கான்கிரீட் பிணைப்பையும் வழங்குகிறது, இது இதற்கிடையில் மேம்படுத்தப்பட்டுள்ளது. உண்மையில், n செங்குத்துகளில் கொடுக்கப்பட்ட இருதரப்பு வரைபடத்திற்கு, அதன் இருதரப்பு பரிமாணம் அதிகபட்சமாக k பயன்பாடுகளில் உள்ளதா என்பதை சரியான நேரத்தில் தீர்மானிக்க முடியும். உதாரணமாக, கணினி அமைப்புகளில், ஒரு அமைப்பின் வெவ்வேறு பயனர்கள் பல்வேறு வளங்களை அணுக அனுமதிக்கப்படலாம் அல்லது அனுமதிக்கப்படாமல் இருக்கலாம். ஒரு பங்கு அடிப்படையிலான அணுகல் கட்டுப்பாட்டு அமைப்பில், ஒரு பங்கு வளங்களின் தொகுப்பிற்கான அணுகல் உரிமைகளை வழங்குகிறது. ஒரு பயனர் பல பாத்திரங்களை சொந்தமாக வைத்திருக்க முடியும், மேலும் அவரது சில பாத்திரங்களால் வழங்கப்பட்ட அனைத்து வளங்களையும் அணுக அவருக்கு அனுமதி உள்ளது. மேலும், ஒரு பாத்திரத்தை பல பயனர்கள் சொந்தமாக வைத்திருக்கலாம். ஒவ்வொரு பயனருக்கும், அவரது பாத்திரங்கள் ஒன்றாக எடுக்கப்பட்டு அனைத்து குறிப்பிட்ட வளங்களுக்கும் அணுகலை வழங்குவது போன்ற குறைந்தபட்ச பாத்திரங்களின் தொகுப்பைக் கண்டுபிடிப்பதே பங்கு சுரங்க சிக்கலாகும். கணினியில் உள்ள வளங்களின் தொகுப்புடன் பயனர்களின் தொகுப்பு இயற்கையாகவே இருதரப்பு வரைபடத்தைத் தூண்டுகிறது, அதன் விளிம்புகள் அனுமதிகளாகும். இந்த வரைபடத்தில் உள்ள ஒவ்வொரு பைக்ளிக் ஒரு சாத்தியமான பங்கு, மற்றும் பங்கு சுரங்கப் பிரச்சினைக்கு உகந்த தீர்வுகள் துல்லியமாக குறைந்தபட்ச பைக்ளிக் எட்ஜ் கவர்கள் ஆகும். இதேபோன்ற சூழ்நிலை கணினி பாதுகாப்பிலும், குறிப்பாக பாதுகாப்பான ஒளிபரப்பிலும் அறியப்படுகிறது. அந்த அமைப்பில், பல செய்திகளை ஒவ்வொன்றும் பெறுநர்களின் தொகுப்புக்கு, பாதுகாப்பற்ற சேனலில் அனுப்ப வேண்டும். ஒவ்வொரு செய்தியும் சில கிரிப்டோகிராஃபிக் விசையைப் பயன்படுத்தி குறியாக்கம் செய்யப்பட வேண்டும், இது விரும்பிய பெறுநர்களுக்கு மட்டுமே தெரியும். ஒவ்வொரு பெறுநரும் பல குறியாக்க விசைகளைக் கொண்டிருக்கலாம், மேலும் ஒவ்வொரு விசையும் பல பெறுநர்களுக்கு விநியோகிக்கப்படும். பாதுகாப்பான பரிமாற்றத்தை உறுதி செய்வதற்காக குறைந்தபட்ச குறியாக்க விசைகளின் தொகுப்பைக் கண்டுபிடிப்பதே உகந்த முக்கிய தலைமுறை சிக்கலாகும். மேலே உள்ளபடி, இருதரப்பு வரைபடத்தைப் பயன்படுத்தி சிக்கலை மாதிரியாக்கலாம், அதன் குறைந்தபட்ச இரு கிளைக் விளிம்பு உறைகள் உகந்த விசை தலைமுறை சிக்கலுக்கான தீர்வுகளுடன் ஒத்துப்போகின்றன. உயிரியலில் வேறுபட்ட பயன்பாடு உள்ளது, அங்கு மனித லுகோசைட் ஆன்டிஜென் (எச். எல். ஏ) செரோலஜியின் கணித மாதிரிகளில் குறைந்தபட்ச பைக்ளிக் எட்ஜ் கவர்கள் பயன்படுத்தப்படுகின்றன. மேலும் காண்க NP-முழுமையான சிக்கல்களின் பட்டியல் குறுக்குவெட்டு எண் (வரைபடக் கோட்பாடு), ஒரு வரைபட குறிப்புகளின் விளிம்புகளை மறைக்க தேவையான குறைந்தபட்ச குழுக்களின் எண்ணிக்கை. . . . . . . . . . . . . . . வெளிப்புற இணைப்புகள் இருதரப்பு பரிமாணத்தைப் பற்றிய வலைப்பதிவு உள்ளீடு டேவிட் எப்ஸ்டீன் என்பி-முழுமையான சிக்கல்கள் வரைபட மாறிலிகள் இருதரப்பு வரைபடங்கள் உள்ளடக்கிய சிக்கல்கள்