Cutwidth
வரைபடக் கோட்பாட்டில், திசைதிருப்பப்படாத வரைபடத்தின் வெட்டு அகலம் பின்வரும் பண்புகளைக் கொண்ட மிகச்சிறிய முழு எண்ணாகும்ஃ வரைபடத்தின் செங்குத்துகளின் வரிசை உள்ளது, அதாவது செங்குத்துகளை முந்தைய மற்றும் பிந்தைய துணைக்குழுக்களாகப் பிரிப்பதன் மூலம் பெறப்படும் ஒவ்வொரு வெட்டும் வரிசையின் பெரும்பாலான விளிம்புகளால் கடக்கப்படுகிறது. அதாவது, செங்குத்துகள் எண்ணப்பட்டிருந்தால், ஒவ்வொன்றிற்கும், விளிம்புகளின் எண்ணிக்கை மற்றும் அதிகபட்சமாக இருக்கும். ஒரு வரைபடத்தின் வெட்டு அகலம் அதன் மடிப்பு எண் என்றும் அழைக்கப்படுகிறது. கட் அகலத்தை உருவாக்கும் உச்சி வரிசை மற்றும் இந்த வரிசை மற்றும் கட் அகலத்தை கணக்கிடுவதில் உள்ள சிக்கல் ஆகிய இரண்டும் குறைந்தபட்ச வெட்டு நேரியல் ஏற்பாடு என்று அழைக்கப்படுகின்றன. மற்ற அளவுருக்களுடனான உறவு கட் அகலம் வரைபடங்களின் பல அகல அளவுருக்களுடன் தொடர்புடையது. குறிப்பாக, இது எப்போதும் ஒரே வரைபடத்தின் மூன்று அகலம் அல்லது பாதை அகலத்தைப் போலவே பெரியதாக இருக்கும். இருப்பினும், இது அதிகபட்ச பாதை அகலத்தால் பெருக்கப்படுகிறது, அல்லது மூன்று அகலம் அதிகபட்ச டிகிரி மற்றும் செங்குத்துகளின் எண்ணிக்கையால் பெருக்கப்படுகிறது. வரைபடங்களின் குடும்பம் அதிகபட்ச டிகிரியை வரம்புக்குட்பட்டதாக இருந்தால், அதன் வரைபடங்களில் வரம்பற்ற அளவிலான முழுமையான பைனரி மரங்களின் உட்பிரிவுகள் இல்லை என்றால், குடும்பத்தில் உள்ள வரைபடங்கள் கட் அகலத்தை வரம்புக்குட்பட்டவை. சப் கியூபிக் வரைபடங்களில் (அதிகபட்ச டிகிரி மூன்று வரைபடங்கள்), கட் அகலம் பாதை அகலம் கூட்டல் ஒன்றுக்கு சமம். வெட்டு அகலம் என்பது எந்தவொரு வரைபடத்தின் குறைந்தபட்ச இருமுனை எண்ணை விட அதிகமாகவோ அல்லது சமமாகவோ இருக்கும். இது செங்குத்துகளை சம அளவிலான (அல்லது முடிந்தவரை சமமான) இரண்டு துணைக்குழுக்களாகப் பிரிப்பதற்கு ஒரு பக்கத்திலிருந்து இன்னொரு பக்கத்திற்கு குறைந்தபட்ச சாத்தியமான விளிம்புகளின் எண்ணிக்கையாகும். ஒரு வரைபடத்தின் எந்த நேரியல் அமைப்பும், அதன் உகந்த வெட்டு அகலத்தை அடைவது, அதே எண்ணிக்கையிலான விளிம்புகளுடன் ஒரு இரு பிரிவையும் வழங்குகிறது, இது அமைப்பை அதன் முதல் மற்றும் இரண்டாவது பகுதிகளாகப் பிரிப்பதன் மூலம் பெறப்படுகிறது. கட் அகலம் என்பது வரைபட அலைவரிசையால் பெருக்கப்படும் அதிகபட்ச டிகிரிக்கு குறைவாகவோ அல்லது சமமாகவோ இருக்கும், இந்த அளவைக் குறைக்க தேர்ந்தெடுக்கப்பட்ட ஒரு நேரியல் ஏற்பாட்டில் எந்த விளிம்பின் இறுதிப் புள்ளிகளையும் பிரிக்கும் அதிகபட்ச படிகளின் எண்ணிக்கை. அலைவரிசையைப் போலல்லாமல், விளிம்புகள் ஒன்றுக்கு மேற்பட்ட விளிம்புகளின் பாதைகளாக பிரிக்கப்படும்போது வெட்டு அகலம் மாறாது. இது கொடுக்கப்பட்ட வரைபடத்தின் விளிம்புகளைப் பிரிப்பதன் மூலம் பெறக்கூடிய குறைந்தபட்ச அலைவரிசையான "இடவியல் அலைவரிசையுடன்" நெருக்கமாக தொடர்புடையது. குறிப்பாக, எந்தவொரு மரத்திற்கும் இது இடவியல் அலைவரிசை மற்றும் சற்றே பெரிய எண்ணிக்கைக்கு இடையில் சாண்ட்விச் செய்யப்படுகிறது. மற்றொரு அளவுரு, ஒரு வரைபடத்தில் வெட்டுக்களை விரிவுபடுத்தும் விளிம்புகளின் எண்ணிக்கையின் அடிப்படையில் வெட்டு அகலத்திற்கு ஒத்ததாக வரையறுக்கப்படுகிறது, இது செதுக்கலின் அகலமாகும். இருப்பினும், செங்குத்துகளின் நேரியல் வரிசை மற்றும் வெட்டுக்களின் நேரியல் வரிசையைப் பயன்படுத்துவதற்குப் பதிலாக, வெட்ட அகலத்தைப் போலவே, செதுக்குதல் அகலம் செங்குத்துகளின் படிநிலைக் கிளஸ்டரிங்கிலிருந்து பெறப்பட்ட வெட்டுக்களைப் பயன்படுத்துகிறது, இது மூன்று அகலம் அல்லது கிளை அகலத்துடன் மிகவும் நெருக்கமாக தொடர்புடையது மற்றும் பாதை அகலம் அல்லது அலைவரிசை போன்ற நேரியல் வரிசைகளை உள்ளடக்கிய பிற அகல அளவுருக்களுடன் குறைவாக ஒத்திருக்கிறது. வரைபட வரைபடங்களின் ஆய்வில் எழும் மற்றொரு அளவுருவான குறுக்குவெட்டு எண்ணில் குறைந்த வரம்பை வழங்க கட் அகலத்தைப் பயன்படுத்தலாம். ஒரு வரைபடத்தின் குறுக்குவெட்டு எண் என்பது குறுக்கிடும் குறைந்தபட்ச ஜோடி விளிம்புகளின் எண்ணிக்கையாகும், ஒவ்வொரு உச்சியும் ஒரு இறுதிப் புள்ளியாக இருக்கும் விளிம்புகளை மட்டுமே தொடும் தளத்தில் உள்ள வரைபடத்தின் எந்த வரைபடத்திலும். வரம்புக்குட்பட்ட டிகிரி வரைபடங்களில், கடக்கும் எண் எப்போதும் குறைந்தபட்சம் கட் அகலத்தின் சதுரத்திற்கு விகிதாசாரமாக இருக்கும். டிகிரி வரம்புகள் இல்லாத வரைபடங்களுக்கு மிகவும் துல்லியமான வரம்பைப் பயன்படுத்துவதுஃ இங்கே, திருத்தம் சொல், வர்க்க டிகிரிகளின் கூட்டுத்தொகைக்கு விகிதாசாரமாக, பிளானர் வரைபடங்களின் இருப்பைக் கணக்கிட அவசியம், அதன் வர்க்க வெட்டு அகலம் இந்த அளவிற்கு விகிதாசாரமாக இருக்கும், ஆனால் அதன் குறுக்கு எண் பூஜ்ஜியமாகும். வரைபட வரைபடத்தின் மற்றொரு பாணியில், புத்தக உட்பொதிப்பு, செங்குத்துகள் ஒரு வரியில் ஏற்பாடு செய்யப்படுகின்றன, மேலும் விளிம்புகள் குறுக்கிடாமல் தனித்தனி அரை-தள பக்கங்களாக இந்த வரியில் சந்திக்கப்படுகின்றன. ஒரு புத்தக உட்பொதிப்பின் பக்க அகலம் அதே உச்சி வரிசையைப் பயன்படுத்தி எந்தவொரு பக்கத்திலும் மிகப்பெரிய வெட்டு அகலமாக வரையறுக்கப்பட்டுள்ளது. கணக்கீட்டு சிக்கலானது வெட்டு அகலத்தைக் காணலாம், மேலும் செங்குத்துகளின் மரத்திற்கு உகந்த அகலத்தின் நேரியல் அமைப்பை உருவாக்கலாம். மேலும் பொதுவான வரைபடங்களுக்கு, இது NP-கடினமானது. இது பிளானர் வரைபடங்களுக்கு கூட NP-கடினமாக உள்ளது, மேலும் சிக்கலின் எடையுள்ள பதிப்பு (ஒரு நேரியல் ஏற்பாட்டின் எந்த வெட்டிலும் விளிம்புகளின் எடையைக் குறைத்தல்) உள்ளீடு ஒரு மரமாக இருக்கும்போது கூட NP-கடினமானது. டைனமிக் புரோகிராமிங்கைப் பயன்படுத்தி ஹெல்ட்-கார்ப் வழிமுறை மூலம் சரியான நேரத்தில் தீர்க்கக்கூடிய உகந்த நேரியல் ஏற்பாட்டின் பல சிக்கல்களில் கட் அகலமும் ஒன்றாகும். நேரத்துடன் கூடிய வேகமான குவாண்டம் வழிமுறையும் அறியப்படுகிறது. கூடுதலாக, இது நிலையான-அளவுரு டிராக்டபிள் ஆகும்ஃ எந்த நிலையான மதிப்பிற்கும், ஒரு வரைபடம் அதிகபட்சமாக வெட் அகலத்தைக் கொண்டிருக்கிறதா என்பதைச் சோதிக்க முடியும், அப்படியானால், அதற்கு உகந்த வெர்டெக்ஸ் வரிசையைக் கண்டறியவும், நேரியல் நேரத்தில். இன்னும் துல்லியமாக, இரண்டையும் பொறுத்தவரை, இந்த வழிமுறையின் இயங்கும் நேரம். ஒரு மாற்று அளவுரு வழிமுறை, ஒரு சிறிய எண்ணிக்கையிலான செங்குத்துகள் அதிக டிகிரியைக் கொண்ட வரைபடங்களுக்கு மிகவும் பொருத்தமானது (வெட் அகலத்தை பெரியதாக ஆக்குகிறது) அதற்கு பதிலாக வரைபடம் வரம்புக்குட்பட்ட அளவின் வெர்டெக்ஸ் கவர் இருக்கும்போது நேர பல்லுறுப்புக்கோவையில் சிக்கலைத் தீர்க்கிறது, அதை ஒரு முழு நிரலாக்க சிக்கலாக மாற்றுவதன் மூலம் சில மாறிகள் மற்றும் மாறி மதிப்புகளில் பல்லுறுப்புக்கோவை வரம்புகளுடன். கட் அகலம் மற்றும் வெர்டெக்ஸ் கவர் எண் மூலம் அளவுருக்கள் இரண்டையும் உட்படுத்தும் வரம்புக்குட்பட்ட மூன்று அகலத்தின் வரைபடங்களுக்கு சிக்கலை திறம்பட தீர்க்க முடியுமா என்பது திறந்த நிலையில் உள்ளது. அடர்த்தியான வரைபடங்களுக்கு கட் அகலம் ஒரு பல்லுறுப்புக்கோவை-நேர தோராய திட்டத்தைக் கொண்டுள்ளது, ஆனால் அடர்த்தியாக இல்லாத வரைபடங்களுக்கு அறியப்பட்ட சிறந்த தோராய விகிதம். இது டாம் லைட்டன் மற்றும் சதீஷ் ராவ் ஆகியோரின் தோராயமான வெட்டு அகலத்தை குறைந்தபட்ச இருமுனை எண்ணாகக் குறைப்பதற்கான ஒரு முறையிலிருந்து வருகிறது, தோராய விகிதத்தில் ஒரு காரணியை இழந்து, செங்குத்துகளை வரிசைப்படுத்த தொடர்ச்சியான இருமுனை பயன்படுத்துவதன் மூலம். குறைந்தபட்ச இருமுனை எண்ணை தோராயமாக மதிப்பிடுவதற்கு சஞ்சீவ் அரோரா, ராவ் மற்றும் உமேஷ் வஜிரானி ஆகியோரின் மற்றொரு முறையுடன் இந்த தொடர்ச்சியான இருமுனை முறையை இணைப்பது, கூறப்பட்ட தோராய விகிதத்தை அளிக்கிறது. சிறிய தொகுப்பு விரிவாக்க கருதுகோளின் கீழ், நிலையான தோராய விகிதத்தை அடைய முடியாது. பயன்பாடுகள் வெட்டு அகலத்திற்கான ஒரு ஆரம்ப ஊக்கமளிக்கும் பயன்பாடு வி. எல். எஸ். ஐ வடிவமைப்பில் சேனல் ரூட்டிங்கை உள்ளடக்கியது, இதில் ஒரு ஒருங்கிணைந்த சுற்றுவட்டத்தின் செவ்வகப் பகுதியின் மேல் மற்றும் கீழ் பகுதியில் அமைக்கப்பட்ட கூறுகள் கூறுகளுடன் இணைக்கப்பட்ட ஜோடி ஊசிகளை இணைக்கும் கடத்திகளால் இணைக்கப்பட வேண்டும். கூறுகள் வெவ்வேறு இடது-வலது வரிசைகளில் ஒழுங்கமைக்கப்படுவதற்கு சுதந்திரமாக இருந்தால், ஆனால் ஒவ்வொரு கூறுகளின் ஊசிகளும் தொடர்ச்சியாக இருக்க வேண்டும், பின்னர் இது ஒவ்வொரு கூறுக்கும் ஒரு உச்சியுடன் ஒரு வரைபடத்தின் நேரியல் ஏற்பாட்டைத் தேர்ந்தெடுப்பதில் ஒரு சிக்கலாக மொழிபெயர்க்கப்படலாம். வரைபடத்தின் வெட்டு அகலம் சுற்றுப்பாதையை வழிநடத்த தேவையான சேனல்களின் எண்ணிக்கையைக் கட்டுப்படுத்துகிறது. புரத பொறியியலில், ஒரு தொடர்புடைய வரைபடம் கட் அகலத்தை வரம்புக்குட்பட்டது என்ற அனுமானம் எம். ஆர். என். ஏ வரிசைகளுக்கான தேடலை விரைவுபடுத்த பயன்படுத்தப்படுகிறது, அவை ஒரே நேரத்தில் கொடுக்கப்பட்ட புரத வரிசைக்கு குறியீடு மற்றும் கொடுக்கப்பட்ட இரண்டாம் நிலை கட்டமைப்பில் மடிக்கப்படுகின்றன. இயக்கப்படும் அசைக்ளிக் வரைபடங்களுக்கு பொருந்தும் சிக்கலின் ஒரு எடையுள்ள மாறுபாடு, மற்றும் வரைபட விளிம்புகளின் நோக்குநிலையுடன் ஒத்துப்போகும் நேரியல் வரிசைகளை மட்டுமே அனுமதிக்கிறது, கணக்கீட்டு பணிகளின் வரிசையை அட்டவணையில் தேவைப்படும் அதிகபட்ச நினைவகத்தை குறைக்கும் வகையில் திட்டமிட பயன்படுத்தப்பட்டுள்ளது, பணிகளுக்குத் தேவையானது மற்றும் பணி-க்கு-பணி தகவல்தொடர்புக்கு பயன்படுத்தப்படும் தரவைப் பராமரிப்பது. தரவுத்தளக் கோட்பாட்டில், கட் அகல சிக்கலின் NP-கடினத்தன்மை, ஒரு இணைப்பைச் செய்யும்போது வட்டு மற்றும் பிரதான நினைவகத்திற்கு இடையில் தரவுகளின் தொகுதிகளை மாற்றுவதை திட்டமிடுவது NP-கடினம் என்பதைக் காட்டப் பயன்படுத்தப்படுகிறது, ஒரே தொகுதியின் தொடர்ச்சியான இடமாற்றங்களைத் தவிர்ப்பதற்காக, ஒரு குறிப்பிட்ட அளவு பிரதான நினைவகத்திற்குள் கணக்கீட்டைப் பொருத்தும்போது. வரைபட வரைபடத்தில், கடக்கும் எண்ணுக்கு கீழ் வரம்பில் பயன்படுத்தப்படுவதோடு, ஒரு குறிப்பிட்ட வகை முப்பரிமாண வரைபட வரைபடத்தின் ஆய்வில் வெட்டு அகலமும் பயன்படுத்தப்பட்டுள்ளது, இதில் விளிம்புகள் அதிகபட்சமாக ஒரு வளைவுடன் இணைந்த பலகோண சங்கிலிகளாக குறிப்பிடப்படுகின்றன, செங்குத்துகள் ஒரு கோட்டில் வைக்கப்படுகின்றன, மேலும் அனைத்து செங்குத்துகள் மற்றும் வளைவு புள்ளிகளும் முழு எண் ஆயத்தொகுதிகளைக் கொண்டிருக்க வேண்டும். இந்த வகை வரைபடங்களுக்கு, வரைபடத்தின் எல்லை பெட்டியின் குறைந்தபட்ச அளவு குறைந்தபட்சம் வெட்டு அகலத்தை செங்குத்துகளின் எண்ணிக்கையால் பெருக்குவதற்கு விகிதாசாரமாக இருக்க வேண்டும். இந்த அளவுடன் ஒரு வரைபடம் எப்போதும் உள்ளது, செங்குத்துகள் ஒரு அச்சு-இணையான கோட்டில் வைக்கப்படுகின்றன. குறிப்புகள் வரைபட மாறிலிகள்