Maximum cut
ஒரு வரைபடத்தைப் பொறுத்தவரை, அதிகபட்ச வெட்டு என்பது குறைந்தபட்சம் வேறு எந்த வெட்டு அளவையும் கொண்ட ஒரு வெட்டு ஆகும். அதாவது, இது வரைபடத்தின் செங்குத்துகளை இரண்டு நிரப்பு தொகுப்புகளாகப் பிரிப்பதாகும், அதாவது மற்றும் இடையே உள்ள விளிம்புகளின் எண்ணிக்கை முடிந்தவரை பெரியதாக இருக்கும். அத்தகைய வெட்டு கண்டுபிடிப்பது அதிகபட்ச வெட்டு சிக்கல் என்று அழைக்கப்படுகிறது. இந்தப் பிரச்சினையை பின்வருமாறு எளிமையாகச் சொல்லலாம். உச்சி தொகுப்பின் துணைக்குழுவை ஒருவர் விரும்புகிறார், அதாவது இடையே உள்ள விளிம்புகளின் எண்ணிக்கை மற்றும் நிரப்பு துணைக்குழு முடிந்தவரை பெரியதாக இருக்கும். சமமாக, முடிந்தவரை பல விளிம்புகளைக் கொண்ட வரைபடத்தின் இருதரப்பு துணை வரைபடத்தை ஒருவர் விரும்புகிறார். எடையுள்ள அதிகபட்ச வெட்டு என்று அழைக்கப்படும் சிக்கலின் மிகவும் பொதுவான பதிப்பு உள்ளது, அங்கு ஒவ்வொரு விளிம்பும் ஒரு உண்மையான எண், அதன் எடை ஆகியவற்றுடன் தொடர்புடையது, மேலும் விளிம்புகளின் எண்ணிக்கையை விட இடையில் மற்றும் அதன் நிரப்பு விளிம்புகளின் மொத்த எடையை அதிகரிப்பதே இதன் நோக்கம். நேர்மறை மற்றும் எதிர்மறை எடைகளை அனுமதிக்கும் எடையுள்ள அதிகபட்ச வெட்டு சிக்கலை அனைத்து எடைகளிலும் அடையாளத்தை புரட்டுவதன் மூலம் ஒரு எடையுள்ள குறைந்தபட்ச வெட்டு சிக்கலாக மாற்றலாம். கீழ் எல்லைகள் எட்வர்ட்ஸ் செங்குத்துகள் மற்றும் விளிம்புகளைக் கொண்ட ஒரு வரைபடத்தில் மேக்ஸ்-கட்டுக்கு பின்வரும் இரண்டு கீழ் வரிகளைப் பெற்றார் (அ) தன்னிச்சையானது, ஆனால் (ஆ) அது இணைக்கப்பட்டுள்ளது): (அ) (ஆ) பௌண்ட் (ஆ) பெரும்பாலும் எட்வர்ட்ஸ்-எர்டாஸ் என்று அழைக்கப்படுகிறது. எட்வர்ட்ஸ் எட்வர்ட்ஸ்-எர்டாஸ் பிணைப்பை நிகழ்தகவு முறையைப் பயன்படுத்தி நிரூபித்தார்; க்ரோஸ்டன் மற்றும் பலர். நேரியல் இயற்கணிதம் மற்றும் போலி-பூலியன் செயல்பாடுகளின் பகுப்பாய்வு ஆகியவற்றைப் பயன்படுத்தி பிணைப்பை நிரூபித்தது. க்ரோஸ்டன் மற்றும் பிறரின் சான்று. கையொப்பமிடப்பட்ட வரைபடங்களில் பேலன்ஸ் சப் கிராஃப் பிராப்ளம் (பிஎஸ்பி) உடன் பிணைக்கப்பட்ட எட்வர்ட்ஸ்-எர்டஸை நீட்டிக்க அனுமதிக்கிறது, அதாவது. ஒவ்வொரு விளிம்பும் + அல்லது-ஒதுக்கப்பட்டுள்ள வரைபடங்கள். துணைக்குழுக்களாகப் பிரிப்பதற்கு, மற்றும் மற்றும் ஒரே துணைக்குழுவில் இருந்தால், அல்லது மற்றும் மற்றும் வெவ்வேறு துணைக்குழுக்களாக இருந்தால் ஒரு விளிம்பு சமநிலைப்படுத்தப்படுகிறது. அதிகபட்ச எண்ணிக்கையிலான சமநிலையான விளிம்புகளைக் கொண்ட ஒரு பகிர்வை கண்டுபிடிப்பதை பிஎஸ்பி நோக்கமாகக் கொண்டுள்ளது. எட்வர்ட்ஸ்-எர்டாஸ் இணைக்கப்பட்ட ஒவ்வொரு கையொப்பமிடப்பட்ட வரைபடத்திற்கும் குறைந்த வரம்பை வழங்குகிறது. வரைவுகளின் சிறப்பு வகுப்புகளுக்கு பிணைப்பு (அ) மேம்படுத்தப்பட்டதுஃ முக்கோணம் இல்லாத வரைபடங்கள், கொடுக்கப்பட்ட அதிகபட்ச டிகிரியின் வரைபடங்கள்,-இல்லாத வரைபடங்கள் போன்றவை, எ. கா. போல்ஜாக் மற்றும் டர்சிக் எட்வர்ட்-எர்டாஸை எடையுள்ள மேக்ஸ்-கட் வரை நீட்டித்தனர்ஃ எங்கு மற்றும் அதன் எடைகள் மற்றும் அதன் குறைந்தபட்ச எடை பரவியிருக்கும் மரம். சமீபத்தில், குட்டின் மற்றும் யியோ ஆகியோர் போல்ஜக்-துர்சிக் வரம்பை தன்னிச்சையான எடையுள்ள வரைபடங்கள் மற்றும் சிறப்பு வகை எடையுள்ள வரைபடங்களுக்கான வரம்புகளுக்கு நீட்டிக்கும் எடையுள்ள மேக்ஸ்-கட் பல குறைந்த வரம்புகளைப் பெற்றனர். அதிகபட்ச வெட்டுக்கள் தொடர்பான பின்வரும் முடிவு சிக்கல் கோட்பாட்டு கணினி அறிவியலில் பரவலாக ஆய்வு செய்யப்பட்டுள்ளதுஃ ஒரு வரைபடம் G மற்றும் ஒரு முழு எண் k கொடுக்கப்பட்டால், G இல் குறைந்தபட்சம் k அளவு வெட்டு இருக்கிறதா என்பதை தீர்மானிக்கவும். இந்த சிக்கல் NP-முழுமையானது என்று அறியப்படுகிறது. சிக்கல் NP இல் உள்ளது என்பதைப் பார்ப்பது எளிதுஃ போதுமான அளவு பெரிய வெட்டு வழங்குவதன் மூலம் ஆம் என்ற பதிலை நிரூபிக்க எளிதானது. சிக்கலின் NP-முழுமையைக் காட்டலாம், எடுத்துக்காட்டாக, அதிகபட்ச 2-திருப்தியிலிருந்து குறைப்பதன் மூலம் (அதிகபட்ச திருப்திகரமான சிக்கலின் கட்டுப்பாடு). முடிவு சிக்கலின் எடையுள்ள பதிப்பு கார்பின் 21 NP-முழுமையான சிக்கல்களில் ஒன்றாகும்; கார்ப் பகிர்வு சிக்கலில் இருந்து குறைப்பதன் மூலம் NP-முழுமையைக் காட்டினார். மேற்கண்ட முடிவு சிக்கலின் நியமன உகப்பாக்கம் மாறுபாடு பொதுவாக அதிகபட்ச-வெட்டு சிக்கல் அல்லது அதிகபட்ச-வெட்டு என்று அழைக்கப்படுகிறது, மேலும் இது பின்வருமாறு வரையறுக்கப்படுகிறதுஃ ஒரு வரைபடம் ஜி கொடுக்கப்பட்டால், அதிகபட்ச வெட்டு கண்டுபிடிக்கவும். உகப்பாக்கம் மாறுபாடு NP-ஹார்ட் என்று அறியப்படுகிறது. இதற்கு நேர்மாறான சிக்கல், குறைந்தபட்ச வெட்டு கண்டுபிடிப்பது ஃபோர்டு-ஃபுல்கர்சன் வழிமுறை மூலம் திறம்பட தீர்க்கக்கூடியது என்று அறியப்படுகிறது. வழிமுறைகள் பல்லுறுப்புக்கோவை-நேர வழிமுறைகள் அதிகபட்ச வெட்டு சிக்கல் NP-கடினமாக இருப்பதால், பொது வரைபடங்களில் அதிகபட்ச வெட்டு-க்கான பல்லுறுப்புக்கோவை-நேர வழிமுறைகள் எதுவும் அறியப்படவில்லை. இருப்பினும், பிளானர் வரைபடங்களில், அதிகபட்ச-வெட்டு சிக்கல் பாதை ஆய்வு சிக்கலுக்கு இரட்டை ஆகும் (ஒரு வரைபடத்தின் ஒவ்வொரு விளிம்பையும் குறைந்தது ஒரு முறையாவது பார்வையிடும் குறுகிய சுற்றுப்பயணத்தைக் கண்டுபிடிப்பதில் சிக்கல்), அதாவது ஒரு வரைபடத்தின் அதிகபட்ச வெட்டு-தொகுப்பைச் சேராத விளிம்புகள் ஜி இன் இரட்டை வரைபடத்தின் உகந்த ஆய்வு சுற்றுப்பயணத்தில் இரட்டிப்பாகும் விளிம்புகளின் இரட்டை ஆகும். உகந்த ஆய்வு சுற்றுப்பயணம் ஒரு சுய-குறுக்குவெட்டு வளைவை உருவாக்குகிறது, இது விமானத்தை இரண்டு துணைக்குழுக்களாகப் பிரிக்கிறது, வளைவின் முறுக்கு எண் சமமாக இருக்கும் புள்ளிகளின் துணைக்குழு மற்றும் முறுக்கு எண் ஒற்றைப்படை இருக்கும் துணைக்குழு; இந்த இரண்டு துணைக்குழுக்களும் ஒரு வெட்டை உருவாக்குகின்றன, அதில் அனைத்து விளிம்புகளும் அடங்கும், அவற்றின் இரட்டை தோன்றும். பாதை ஆய்வு சிக்கல் பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கப்படலாம், மேலும் இந்த இரட்டைத்தன்மை பிளானர் வரைபடங்களுக்கான பல்லுறுப்புக்கோவை நேரத்தில் அதிகபட்ச வெட்டு சிக்கலையும் தீர்க்க அனுமதிக்கிறது. இருப்பினும் அதிகபட்ச-பிளவு சிக்கல் NP-கடினமானது என்று அறியப்படுகிறது. தோராய வழிமுறைகள் அதிகபட்ச வெட்டு சிக்கல் APX-கடினமானது, அதாவது P = NP தவிர, உகந்த தீர்வுக்கு தன்னிச்சையாக நெருக்கமாக எந்த பல்லுறுப்புக்கோவை-நேர தோராய திட்டமும் (PTAS) இல்லை. எனவே, அறியப்பட்ட ஒவ்வொரு பல்லுறுப்புக்கோவை-நேர தோராயமான வழிமுறையும் ஒன்றுக்கு குறைவான தோராய விகிதத்தை கண்டிப்பாக அடைகிறது. ஒரு எளிய சீரற்ற 0.5-approximation வழிமுறை உள்ளதுஃ ஒவ்வொரு உச்சிக்கும் ஒரு நாணயத்தை புரட்டி, பகிர்வின் எந்த பாதிக்கு ஒதுக்க வேண்டும் என்பதை தீர்மானிக்கவும். எதிர்பார்ப்பில், விளிம்புகளில் பாதி வெட்டப்பட்ட விளிம்புகள். நிபந்தனைக்குட்பட்ட நிகழ்தகவுகளின் முறை மூலம் இந்த வழிமுறையை வேறுபடுத்தலாம்; எனவே ஒரு எளிய தீர்மானகரமான பல்லுறுப்புக்கோவை-நேரம் 0.5-approximation வழிமுறையும் உள்ளது. அத்தகைய ஒரு வழிமுறை கொடுக்கப்பட்ட வரைபடத்தின் உச்சிகளின் தன்னிச்சையான பகிர்வுடன் தொடங்கி, பகிர்வின் ஒரு பக்கத்திலிருந்து இன்னொரு பக்கத்திற்கு ஒரு நேரத்தில் ஒரு உச்சியை மீண்டும் மீண்டும் நகர்த்துகிறது, ஒவ்வொரு கட்டத்திலும் தீர்வை மேம்படுத்துகிறது, இந்த வகையின் மேலும் மேம்பாடுகள் செய்யப்பட முடியாது வரை. ஒவ்வொரு படிநிலையிலும் குறைந்தபட்சம் ஒரு விளிம்பில் வெட்டுதலை அல்காரிதம் மேம்படுத்துவதால் மறு செய்கைகளின் எண்ணிக்கை அதிகபட்சமாக உள்ளது. வழிமுறை முடிவடையும் போது, ஒவ்வொரு உச்சியிலும் ஏற்படும் விளிம்புகளில் குறைந்தது பாதி வெட்டுக்கு சொந்தமானது, இல்லையெனில் உச்சியை நகர்த்துவது வெட்டுதலை மேம்படுத்தும். எனவே, வெட்டு குறைந்தபட்சம் விளிம்புகளை உள்ளடக்கியது. சிறந்த அறியப்பட்ட தோராய விகிதத்துடன் மேக்ஸ்-கட்டிற்கான பல்லுறுப்புக்கோவை-நேர தோராயமான வழிமுறை என்பது கோய்மன்ஸ் மற்றும் வில்லியம்சன் ஆகியோரால் அரை வரையறுக்கப்பட்ட நிரலாக்கம் மற்றும் சீரற்ற வட்டத்தைப் பயன்படுத்தி ஒரு முறை ஆகும், இது ஒரு தோராயமான விகிதத்தை அடைகிறது, அங்கு தனித்துவமான விளையாட்டு அனுமானம் உண்மையாக இருந்தால், இது அதிகபட்ச வெட்டுக்கான சிறந்த தோராயமான விகிதமாகும். இத்தகைய நிரூபிக்கப்படாத அனுமானங்கள் இல்லாமல், அதிகபட்ச-வெட்டு மதிப்பை தோராயமாக மதிப்பிடுவது NP-கடினம் என்று நிரூபிக்கப்பட்டுள்ளது. இதில் திறந்த மூல அமலாக்கம் உட்பட இந்த சிக்கலுக்கான 10 ஹூரிஸ்டிக்ஸ் பற்றிய விரிவான பகுப்பாய்வு உள்ளது. அளவுருக்கள் கொண்ட வழிமுறைகள் மற்றும் கர்னலைசேஷன் குறைந்தபட்சம் (அளவுரு) k அளவைக் குறைப்பதில் உள்ள சிக்கல் நிலையான-அளவுரு டிராக்டபிள் (FPT) என்பதை நிரூபிப்பது அற்பமானதாக இருந்தாலும், ஒரு வரைபடம் G குறைந்தபட்சம் எட்வர்ட்ஸ்-எர்டாஸ் கீழ் வரம்பைக் கொண்டதா என்பதைத் தீர்மானிக்கும் சிக்கலுக்கு நிலையான-அளவுரு டிராக்டபிலிட்டியைக் காண்பிப்பது மிகவும் கடினம் (மேலே உள்ள கீழ் வரம்புகளைப் பார்க்கவும்) மேலும் (அளவுரு) k. க்ரோஸ்டன் மற்றும் பலர். சிக்கலை சரியான நேரத்தில் தீர்க்க முடியும் என்பதை நிரூபித்து, அளவு கொண்ட கர்னலை ஏற்றுக்கொள்கிறது. க்ரோஸ்டன் மற்றும் பலர். நிலையான-அளவுரு டிராக்டபிலிட்டி முடிவை சமநிலையான சப் கிராஃப் சிக்கலுக்கு (பிஎஸ்பி, மேலே உள்ள கீழ் வரம்புகளைப் பார்க்கவும்) விரிவுபடுத்தி, கர்னல் அளவை (பிஎஸ்பி-க்கும் பொருந்தும்) மேம்படுத்தியது. Etscheid மற்றும் Mnich ஆகியவை பி. எஸ். பி. க்கு நிலையான-அளவுரு டிராக்டபிலிட்டி முடிவையும், கர்னல்-அளவு முடிவையும் செங்குத்துகளுக்கு மேம்படுத்தியது. பயன்பாடுகள் இயந்திர கற்றல் அதன் முனைகளை அம்சங்களாகவும் அதன் விளிம்புகளை தூரங்களாகவும் கருதி, அதிகபட்ச வெட்டு வழிமுறை ஒரு வரைபடத்தை நன்கு பிரிக்கப்பட்ட இரண்டு துணைக்குழுக்களாக பிரிக்கிறது. வேறு வார்த்தைகளில் கூறுவதானால், பைனரி வகைப்பாட்டைச் செய்ய இது இயற்கையாகவே பயன்படுத்தப்படலாம். மிகவும் பொதுவான வகைப்பாட்டு வழிமுறைகளுடன் ஒப்பிடும்போது, இதற்கு ஒரு அம்ச இடம் தேவையில்லை, உள்ளே உள்ள உறுப்புகளுக்கு இடையிலான தூரம் மட்டுமே. கோட்பாட்டு இயற்பியல் புள்ளிவிவர இயற்பியல் மற்றும் ஒழுங்கற்ற அமைப்புகளில், மேக்ஸ் கட் சிக்கல் ஒரு சுழல் கண்ணாடி மாதிரியின் ஹாமில்டோனியனைக் குறைப்பதற்கு சமம், மிகவும் எளிமையாக ஐசிங் மாதிரி. G வரைபடத்தில் உள்ள ஐசிங் மாதிரியைப் பொறுத்தவரை மற்றும் அருகிலுள்ள அண்டை தொடர்புகளுக்கு, ஹாமில்டோனியன் இங்கே வரைபடத்தின் ஒவ்வொரு முனையும் ஒரு சுழல் தளமாகும், இது ஒரு சுழல் மதிப்பை எடுக்க முடியும் ஒரு சுழல் உள்ளமைவு பகிர்வுகள் இரண்டு தொகுப்புகளாக, சுழல் மேல் மற்றும் சுழல் கீழ் கொண்டவை இரண்டு தொகுப்புகளை இணைக்கும் விளிம்புகளின் தொகுப்பைக் குறிக்கின்றன. இந்த ஆற்றலைக் குறைப்பது குறைந்தபட்ச வெட்டு சிக்கலுக்கு சமம் அல்லது வரைபட எடைகளை அதிகபட்ச வெட்டு சிக்கலாக அமைப்பதன் மூலம் ஹாமில்டோனியனை மீண்டும் எழுதலாம். சுற்று வடிவமைப்பு அதிகபட்ச வெட்டு சிக்கல் விஎல்எஸ்ஐ வடிவமைப்பில் பயன்பாடுகளைக் கொண்டுள்ளது. குறைந்தபட்ச வெட்டு குறைந்தபட்ச கே-வெட்டு ஒற்றைப்படை சுழற்சி குறுக்குவெட்டையும் பார்க்கவும், இது மிகப்பெரிய இருதரப்பு தூண்டப்பட்ட துணை வரைபடம் நட்பற்ற பகிர்வைக் கேட்பதற்கு சமம், இது எல்லையற்ற வரைபட குறிப்புகள் குறிப்புகளுக்கான தொடர்புடைய கருத்தாகும். . அதிகபட்ச வெட்டு (உகப்பாக்கம் பதிப்பு) என்பது பின் இணைப்பு பி (பக்கம் 399) இல் உள்ள என். டி. 14 சிக்கலாகும். . . . . . . . . . அதிகபட்ச வெட்டு (முடிவு பதிப்பு) என்பது பின் இணைப்பு ஏ 2 இல் உள்ள என். டி 16 சிக்கலாகும். அதிகபட்ச இருதரப்பு துணை வரைபடம் (முடிவு பதிப்பு) என்பது பின் இணைப்பு A1.2 இல் உள்ள GT25 சிக்கலாகும். . . . . . . . . . . . . . . . . . வெளிப்புற இணைப்புகள் பியர்லுய்கி கிரெசென்ஸி, விக்கோ கான், மேக்னஸ் ஹால்டர்சன், மாரேக் கார்பின்ஸ்கி, கெர்ஹார்ட் வோயிங்கர் (2000), "மேக்ஸிமம் கட்", "NP ஆப்டிமைசேஷன் சிக்கல்களின் தொகுப்பு". ஆண்ட்ரியா காசினி, நிக்கோலா ரெபாக்லியாட்டி (2012), "மேக்ஸ் கட் தீர்ப்பதற்கான ஒரு பைதான் நூலகம்" வரைபடக் கோட்பாடு பொருள்கள் ஒருங்கிணைந்த உகப்பாக்கம் NP-முழுமையான சிக்கல்கள் வரைபடக் கோட்பாட்டில் கணக்கீட்டு சிக்கல்கள்