Split graph
வரைபடக் கோட்பாட்டில், கணிதத்தின் ஒரு கிளை, ஒரு பிளவு வரைபடம் என்பது ஒரு வரைபடமாகும், இதில் செங்குத்துகளை ஒரு குழு மற்றும் ஒரு சுயாதீன தொகுப்பாகப் பிரிக்கலாம். பிளவு வரைபடங்கள் முதலில் ஆய்வு செய்யப்பட்டன, மேலும் சுயாதீனமாக அறிமுகப்படுத்தப்பட்டன. ஒரு பிளவு வரைபடம் ஒன்றுக்கு மேற்பட்ட பிரிவுகளை ஒரு குழு மற்றும் ஒரு சுயாதீன தொகுப்பாகக் கொண்டிருக்கலாம்; எடுத்துக்காட்டாக, பாதை ஒரு பிளவு வரைபடமாகும், அதன் செங்குத்துகளை மூன்று வெவ்வேறு வழிகளில் பிரிக்கலாம்ஃ குழு மற்றும் சுயாதீன தொகுப்பு குழு மற்றும் சுயாதீன தொகுப்பு குழு மற்றும் சுயாதீன தொகுப்பு பிளவு வரைபடங்களை அவற்றின் தடைசெய்யப்பட்ட தூண்டப்பட்ட துணை வரைபடங்களின் அடிப்படையில் வகைப்படுத்தலாம்ஃ தூண்டப்பட்ட துணை வரைபடம் நான்கு அல்லது ஐந்து செங்குத்துகளில் ஒரு சுழற்சியாக இல்லாவிட்டால் அல்லது ஒரு ஜோடி இணைந்த விளிம்புகள் (4-சுழற்சியின் நிரப்பு) இருந்தால் மட்டுமே ஒரு வரைபடம் பிரிக்கப்படுகிறது. பிற வரைபடக் குடும்பங்களுடனான உறவு வரையறையிலிருந்து, பிளவு வரைபடங்கள் நிரப்பின் கீழ் தெளிவாக மூடப்பட்டுள்ளன. பிளவு வரைபடங்களின் மற்றொரு தன்மை முழுமையை உள்ளடக்கியதுஃ அவை கார்டல் வரைபடங்கள், அவற்றின் நிரப்பும் கார்டல் ஆகும். கார்டல் வரைபடங்கள் மரங்களின் துணை மரங்களின் குறுக்குவெட்டு வரைபடங்களைப் போலவே, பிளவு வரைபடங்களும் நட்சத்திர வரைபடங்களின் தனித்துவமான அடி மூலக்கூறுகளின் குறுக்குவெட்டு வரைபடங்களாகும். கிட்டத்தட்ட அனைத்து கார்டல் வரைபடங்களும் பிளவுபட்ட வரைபடங்களாகும்; அதாவது, n முடிவிலிக்குச் செல்லும் வரம்பில், பிளவுபட்ட n-வெர்டெக்ஸ் கார்டல் வரைபடங்களின் பின்னம் ஒன்றை அணுகுகிறது. கார்டல் வரைபடங்கள் சரியானவை என்பதால், பிளவு வரைபடங்களும் சரியானவை. இரட்டை பிளவு வரைபடங்கள், ஒவ்வொரு உச்சியையும் இரட்டிப்பாக்குவதன் மூலம் பிளவு வரைபடங்களிலிருந்து பெறப்பட்ட வரைபடங்களின் குடும்பம் (எனவே கிளிக் ஒரு ஆன்டிமேச்சிங்கை தூண்டுகிறது மற்றும் சுயாதீன தொகுப்பு ஒரு பொருத்தத்தைத் தூண்டுகிறது), சரியான வரைபடங்களின் ஐந்து அடிப்படை வகுப்புகளில் ஒன்றாக முக்கியமாகக் கருதப்படுகிறது, இதிலிருந்து மற்ற அனைத்தையும் உருவாக்க முடியும் வலுவான சரியான வரைபட தேற்றத்தின் மூலம் ஆதாரம். ஒரு வரைபடம் ஒரு பிளவு வரைபடம் மற்றும் ஒரு இடைவெளி வரைபடம் ஆகிய இரண்டாக இருந்தால், அதன் நிரப்பு ஒரு பிளவு வரைபடம் மற்றும் ஒரு ஒப்பீட்டு வரைபடம், மற்றும் நேர்மாறாகவும் இருக்கும். பிளவு ஒப்பீட்டு வரைபடங்கள், எனவே பிளவு இடைவெளி வரைபடங்கள், மூன்று தடைசெய்யப்பட்ட தூண்டப்பட்ட துணை வரைபடங்களின் தொகுப்பின் அடிப்படையில் வகைப்படுத்தப்படலாம். பிளவு வரைபடங்கள் சரியாக நுழைவாயில் வரைபடங்கள். பிளவு வரிசைமாற்ற வரைபடங்கள் சரியாக இடைவெளி வரைபட நிரல்களைக் கொண்ட இடைவெளி வரைபடங்கள் ஆகும்; இவை வளைவு-இணைக்கப்பட்ட வரிசைமாற்றங்களின் வரிசைமாற்ற வரைபடங்கள். பிளவு வரைபடங்கள் வண்ணமயமான எண் 2 ஐக் கொண்டுள்ளன. அல்காரிதம் சிக்கல்கள் ஒரு பிளவு வரைபடமாக இருக்கட்டும், இது ஒரு குழு மற்றும் ஒரு சுயாதீன தொகுப்பாக பிரிக்கப்பட்டுள்ளது. பின்னர் ஒரு பிளவு வரைபடத்தில் உள்ள ஒவ்வொரு அதிகபட்ச கிளிக்கும் தானாகவோ அல்லது ஒரு உச்சியின் சுற்றுப்புறமாகவோ இருக்கும். எனவே, அதிகபட்ச கிளிக்கை அடையாளம் காண்பது எளிது, மேலும் ஒரு பிளவு வரைபடத்தில் அதிகபட்ச சுயாதீன தொகுப்பை பூர்த்தி செய்கிறது. எந்தவொரு பிளவு வரைபடத்திலும், பின்வரும் மூன்று சாத்தியக்கூறுகளில் ஒன்று உண்மையாக இருக்க வேண்டும்ஃ முழுமையான ஒரு முனை உள்ளது. இந்த வழக்கில், ஒரு அதிகபட்ச கிளிக்காகும் மற்றும் அதிகபட்ச சுயாதீன தொகுப்பாகும். சுயாதீனமான ஒரு உச்சி உள்ளது. இந்த வழக்கில், ஒரு அதிகபட்ச சுயாதீன தொகுப்பு மற்றும் ஒரு அதிகபட்ச கிளிக்காகும். இது ஒரு அதிகபட்ச கிளிக்காகும் மற்றும் இது ஒரு அதிகபட்ச சுயாதீன தொகுப்பாகும். இந்த வழக்கில், ஒரு கிளிக்கில் ஒரு தனித்துவமான பகிர்வு மற்றும் ஒரு சுயாதீன தொகுப்பு உள்ளது, அதிகபட்ச கிளிக்கில் உள்ளது, மற்றும் அதிகபட்ச சுயாதீன தொகுப்பு உள்ளது. வரைபட வண்ணமயமாக்கல் உட்பட மிகவும் பொதுவான வரைபட குடும்பங்களில் NP-முழுமையான வேறு சில உகப்பாக்கம் சிக்கல்கள், பிளவு வரைபடங்களில் இதேபோல் நேரடியானவை. ஒரு ஹாமில்டோனியன் சுழற்சியைக் கண்டுபிடிப்பது பிளவு வரைபடங்களுக்கு கூட NP-முழுமையானதாக உள்ளது, அவை வலுவான கார்டல் வரைபடங்களாகும். குறைந்தபட்ச ஆதிக்கம் செலுத்தும் தொகுப்பு சிக்கல் பிளவு வரைபடங்களுக்கு NP-முழுமையானதாக உள்ளது என்பதும் அனைவரும் அறிந்ததே. படி வரிசைகள் பிளவு வரைபடங்களின் ஒரு குறிப்பிடத்தக்க பண்பு என்னவென்றால், அவற்றை அவற்றின் படி வரிசைகளிலிருந்து மட்டுமே அடையாளம் காண முடியும். ஒரு வரைபடத்தின் டிகிரி வரிசை இருக்கட்டும், அத்தகைய மிகப்பெரிய மதிப்பாக இருக்கட்டும். அப்படியானால், மிகப்பெரிய டிகிரிகளைக் கொண்ட செங்குத்துகள் அதிகபட்ச கிளிக்கை உருவாக்குகின்றன, மீதமுள்ள செங்குத்துகள் ஒரு சுயாதீனமான தொகுப்பை உருவாக்குகின்றன. ஒரு தன்னிச்சையான வரைபடத்தின் பிளவு இந்த சமத்துவமின்மை எந்த அளவிற்கு உண்மையாக இல்லை என்பதை அளவிடுகிறது. ஒரு வரைபடம் ஒரு பிளவு வரைபடம் இல்லையென்றால், அதை ஒரு பிளவு வரைபடமாக மாற்றும் விளிம்பு செருகல்கள் மற்றும் அகற்றல்களின் மிகச்சிறிய வரிசையை மிகப்பெரிய டிகிரிகளுடன் செங்குத்துகளுக்கு இடையில் காணாமல் போன அனைத்து விளிம்புகளையும் சேர்ப்பதன் மூலமும், மீதமுள்ள செங்குத்துகளின் ஜோடிகளுக்கு இடையில் உள்ள அனைத்து விளிம்புகளையும் அகற்றுவதன் மூலமும் பெறலாம்; பிளவு இந்த வரிசையில் செயல்பாடுகளின் எண்ணிக்கையை கணக்கிடுகிறது. பிளவு வரைபடங்களை எண்ணுவது, n-உடன் n-வெர்டெக்ஸ் பிளவு வரைபடங்கள் சில ஸ்பெர்னர் குடும்பங்களுடன் ஒன்றுக்கு ஒன்று தொடர்புடையவை என்பதைக் காட்டுகிறது. இந்த உண்மையைப் பயன்படுத்தி, n செங்குத்துகளில் ஐசோமார்பிக் அல்லாத பிளவு வரைபடங்களின் எண்ணிக்கைக்கான சூத்திரத்தை அவர் தீர்மானித்தார். n இன் சிறிய மதிப்புகளுக்கு, n = 1 இல் தொடங்கி, இந்த எண்கள் 1,2,4,9,21,56,164,557,2223,10766,64956,501696,. இந்த கணக்கீட்டு முடிவு இதற்கு முன்னரும் நிரூபிக்கப்பட்டது. குறிப்புகள் குறிப்புகள். . . . . . . . . . . . . . . "குறிக்கப்படாத ஒருங்கிணைந்த பொருள்களைக் கணக்கிடுவதற்கான மற்றொரு முறை" (1990) என மொழிபெயர்க்கப்பட்ட, சோவியத் ஒன்றியத்தின் அறிவியல் அகாடமியின் கணிதக் குறிப்புகள் 48 (6): 1239-1245,. . . மார்ட்டின் சார்லஸ் கோலம்பிக் எழுதிய "அல்காரிதம் கிராஃப் தியரி அண்ட் பெர்பெக்ட் கிராஃப்ஸ்" என்ற புத்தகத்தில் பிளவு வரைபடங்கள் பற்றிய ஒரு அத்தியாயம் காணப்படுகிறது. வரைபட குடும்பங்கள் வரைபடங்களின் குறுக்குவெட்டு வகுப்புகள் சரியான வரைபடங்கள்