Cactus graph
வரைபடக் கோட்பாட்டில், ஒரு கற்றாழை (சில நேரங்களில் கற்றாழை மரம் என்று அழைக்கப்படுகிறது) என்பது ஒரு இணைக்கப்பட்ட வரைபடமாகும், இதில் எந்த இரண்டு எளிய சுழற்சிகளும் அதிகபட்சம் ஒரு உச்சியில் பொதுவானவை. சமமாக, இது ஒரு இணைக்கப்பட்ட வரைபடமாகும், இதில் ஒவ்வொரு விளிம்பும் அதிகபட்சம் ஒரு எளிய சுழற்சியைச் சேர்ந்தது, அல்லது (அற்பமான கற்றாழைக்கு) இதில் ஒவ்வொரு தொகுதியும் (வெட்டு-வெர்டெக்ஸ் இல்லாத அதிகபட்ச துணை வரைபடம்) ஒரு விளிம்பு அல்லது சுழற்சியாகும். பண்புகள் கற்றாழை வெளிப்புற பிளானர் வரைபடங்கள் ஆகும். ஒவ்வொரு போலி மரமும் ஒரு கற்றாழை. ஒவ்வொரு தொகுதியும் ஒரு எளிய சுழற்சி அல்லது ஒரு விளிம்பாக இருந்தால் மட்டுமே ஒரு அற்பமான வரைபடம் ஒரு கற்றாழை ஆகும். ஒவ்வொரு கூறுகளும் ஒரு கற்றாழை இருக்கும் வரைபடங்களின் குடும்பம் வரைபட சிறிய செயல்பாடுகளின் கீழ் கீழ்நோக்கி மூடப்பட்டுள்ளது. இந்த வரைபடக் குடும்பத்தை ஒரு தடைசெய்யப்பட்ட சிறிய, முழுமையான வரைபடம் K4 இலிருந்து ஒரு விளிம்பை அகற்றுவதன் மூலம் உருவாக்கப்பட்ட நான்கு-வெர்டெக்ஸ் வைர வரைபடத்தால் வகைப்படுத்தலாம். முக்கோண கற்றாழை ஒரு முக்கோண கற்றாழை ஒரு சிறப்பு வகை கற்றாழை வரைபடமாகும், அதாவது ஒவ்வொரு சுழற்சியும் மூன்று நீளம் கொண்டது மற்றும் ஒவ்வொரு விளிம்பும் ஒரு சுழற்சியைச் சேர்ந்தது. உதாரணமாக, நட்பு வரைபடங்கள், ஒற்றை பகிரப்பட்ட உச்சியில் ஒன்றாக இணைந்த முக்கோணங்களின் தொகுப்பிலிருந்து உருவாக்கப்பட்ட வரைபடங்கள், முக்கோண கற்றாழைகள் ஆகும். கற்றாழை வரைபடங்களாக இருப்பதோடு, முக்கோண கற்றாழைகளும் தொகுதி வரைபடங்கள் மற்றும் உள்ளூரில் நேரியல் வரைபடங்கள் ஆகும். முக்கோண கற்றாழைகள் அவற்றிலிருந்து ஏதேனும் பொருத்தம் அகற்றப்பட்டால் அவை இணைக்கப்பட்டிருக்கும் பண்பைக் கொண்டுள்ளன; கொடுக்கப்பட்ட எண்ணிக்கையிலான செங்குத்துகளுக்கு, அவை இந்த பண்புடன் மிகக் குறைந்த விளிம்புகளைக் கொண்டுள்ளன. ஒற்றைப்படை எண்ணிக்கையிலான செங்குத்துகளைக் கொண்ட ஒவ்வொரு மரமும் ஒரு முக்கோண கற்றாழைக்கு விளிம்புகளைச் சேர்ப்பதன் மூலம் அதிகரிக்கப்படலாம், இது ஒரு பொருத்தத்தை அகற்றிய பிறகு இணைக்கப்பட்டிருக்கும் பண்புடன் குறைந்தபட்ச வளர்ச்சியைக் கொடுக்கும். எந்தவொரு வரைபடத்திலும் உள்ள மிகப்பெரிய முக்கோண கற்றாழை மேட்ராய்டு பேரிட்டி சிக்கலுக்கான ஒரு வழிமுறையைப் பயன்படுத்தி பல்லுறுப்புக்கோவை நேரத்தில் காணலாம். முக்கோண கற்றாழை வரைபடங்கள் பிளானர் வரைபடங்கள் என்பதால், மிகப்பெரிய முக்கோண கற்றாழை மிகப்பெரிய பிளானர் துணை வரைபடத்திற்கு தோராயமாக பயன்படுத்தப்படலாம், இது பிளானரைசேஷனில் ஒரு முக்கியமான துணை சிக்கலாகும். ஒரு தோராயமான வழிமுறையாக, இந்த முறை தோராயமான விகிதம் 4/9 ஐக் கொண்டுள்ளது, இது அதிகபட்ச பிளானர் சப் கிராஃப் சிக்கலுக்கு மிகவும் பிரபலமானது. மிகப்பெரிய முக்கோண கற்றாழையைக் கண்டுபிடிப்பதற்கான வழிமுறை இந்த மிகப்பெரிய கற்றாழையில் உள்ள முக்கோணங்களின் எண்ணிக்கையை வகைப்படுத்தும் லோவாஸ் மற்றும் பிளம்மரின் தேற்றத்துடன் தொடர்புடையது. Lováss மற்றும் Plummer கொடுக்கப்பட்ட வரைபடத்தின் செங்குத்துகள் மற்றும் விளிம்புகளின் பகிர்வுகளின் ஜோடிகளை துணைக்குழுக்களாக கருதுகின்றனர், வரைபடத்தின் ஒவ்வொரு முக்கோணமும் உச்சி பிரிவின் ஒரு வகுப்பில் இரண்டு செங்குத்துகளைக் கொண்டுள்ளது அல்லது விளிம்புப் பிரிவின் ஒரு வகுப்பில் மூன்று விளிம்புகளையும் கொண்டுள்ளது என்ற பண்பு உள்ளது; இந்த பண்பு செல்லுபடியாகும் ஒரு ஜோடி பகிர்வுகளை அவர்கள் அழைக்கிறார்கள். பின்னர் மிகப்பெரிய முக்கோண கற்றாழையில் உள்ள முக்கோணங்களின் எண்ணிக்கை அதிகபட்சமாக, செல்லுபடியாகும் பகிர்வுகளின் ஜோடிக்கு சமம் மற்றும், இன், கொடுக்கப்பட்ட வரைபடத்தில் செங்குத்துகளின் எண்ணிக்கை எங்கே மற்றும் விளிம்பு வகுப்பால் சந்திக்கும் உச்சி வகுப்புகளின் எண்ணிக்கை. ஒவ்வொரு விமான வரைபடத்திலும் ஒரு கற்றாழை துணை வரைபடம் உள்ளது, இதில் கற்றாழையின் முக்கோண முகங்களின் குறைந்தபட்ச பகுதியையாவது உள்ளடக்கியது. இந்த முடிவு மேலே உள்ள குறைந்தபட்ச-அதிகபட்ச சூத்திரத்தைப் பயன்படுத்தாமல் அதிகபட்ச பிளானர் சப் கிராஃப் சிக்கலுக்கான 4/9-தோராயமான வழிமுறையின் நேரடி பகுப்பாய்வைக் குறிக்கிறது. முக்கோண கற்றாழை தொடர்பான ஒரு முக்கியமான அனுமானம் அலெக்ஸாண்டர் ரோசாவின் பெயரிடப்பட்ட ரோசாவின் அனுமானம் ஆகும், இது அனைத்து முக்கோண கற்றாழைகளும் அழகானவை அல்லது கிட்டத்தட்ட கருணையுள்ளவை என்று கூறுகிறது. இன்னும் துல்லியமாக, t ஷ்ண 0,1 மட்டு 4 தொகுதிகளைக் கொண்ட அனைத்து முக்கோண கற்றாழைகளும் அழகாக உள்ளன, மேலும் t ஷ்ண 2,3 மட்டு 4 கொண்டவை அழகாக உள்ளன. வழிமுறைகள் மற்றும் பயன்பாடுகள் பொதுவான வரைபடங்களுக்கு NP-கடினமான சில வசதி இருப்பிட சிக்கல்கள், அதே போல் வேறு சில வரைபட சிக்கல்கள், கற்றாழைக்கான பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கப்படலாம். கற்றாழை வெளிப்புற பிளானர் வரைபடங்களின் சிறப்பு நிகழ்வுகள் என்பதால், வரைபடங்களில் உள்ள பல ஒருங்கிணைந்த உகப்பாக்கம் சிக்கல்கள் பல்லுறுப்புக்கோவை நேரத்தில் அவர்களுக்கு தீர்க்கப்படலாம். கற்றாழை பயனுள்ள பண்புகளைக் கொண்ட மின் சுற்றுகளைக் குறிக்கிறது. கற்றாழையின் ஆரம்பகால பயன்பாடு ஆப்-ஆம்ப்களின் பிரதிநிதித்துவத்துடன் தொடர்புடையது. வெவ்வேறு மரபணுக்கள் அல்லது மரபணுக்களின் பகுதிகளுக்கு இடையிலான உறவைக் குறிக்கும் ஒரு வழியாக ஒப்பீட்டு மரபியலில் கற்றாழை பயன்படுத்தப்படுகிறது. ஒரு கற்றாழை இணைக்கப்பட்டிருந்தால், அதன் ஒவ்வொரு செங்குத்தும் அதிகபட்சம் இரண்டு தொகுதிகளுக்கு சொந்தமானது என்றால், அது கிறிஸ்துமஸ் கற்றாழை என்று அழைக்கப்படுகிறது. ஒவ்வொரு பாலிஹெட்ரல் வரைபடமும் அதன் அனைத்து செங்குத்துகளையும் உள்ளடக்கிய ஒரு கிறிஸ்துமஸ் கற்றாழை துணை வரைபடத்தைக் கொண்டுள்ளது, இது ஒவ்வொரு பாலிஹெட்ரல் வரைபடமும் யூக்ளிடியன் தளத்தில் ஒரு பேராசை உட்பொதிப்பைக் கொண்டுள்ளது என்பதற்கான சான்றில் முக்கிய பங்கு வகிக்கிறது, இது செங்குத்துகளுக்கான ஆயத்தொகுப்புகளின் ஒரு பணியாகும், இதற்காக பேராசை முன்னோக்கிச் செல்வது அனைத்து ஜோடி செங்குத்துகளுக்கும் இடையில் செய்திகளை வழிநடத்துவதில் வெற்றி பெறுகிறது. இடவியல் வரைபடக் கோட்பாட்டில், செல்லுலார் உட்பொதிப்புகள் அனைத்தும் சமதளமாக இருக்கும் வரைபடங்கள் சரியாக கற்றாழை வரைபடங்களின் துணைக்குடும்பமாகும், ஒவ்வொரு உச்சியும் அதிகபட்சம் ஒரு சுழற்சியைச் சேர்ந்த கூடுதல் பண்பு கொண்டது. இந்த வரைபடங்களில் வைர வரைபடம் மற்றும் ஐந்து-வெர்டெக்ஸ் நட்பு வரைபடம் ஆகிய இரண்டு தடைசெய்யப்பட்ட மைனர்கள் உள்ளன. வரலாற்று கற்றாழைகள் முதன்முதலில் ஹுசிமி மரங்கள் என்ற பெயரில் ஆய்வு செய்யப்பட்டன, அவை ஃபிராங்க் ஹராரி மற்றும் ஜார்ஜ் யூஜின் உஹ்லென்பெக் ஆகியோரால் கோடி ஹுசிமி இந்த வரைபடங்களில் முந்தைய பணியின் நினைவாக வழங்கப்பட்டன. அதே ஹராரி-உஹ்லென்பெக் காகிதத்தில் ஒவ்வொரு சுழற்சியும் ஒரு முக்கோணமாக இருக்கும் இந்த வகை வரைபடங்களுக்கு "கற்றாழை" என்ற பெயரை வைத்திருக்கிறது, ஆனால் இப்போது அனைத்து நீளங்களின் சுழற்சிகளையும் அனுமதிப்பது நிலையானது. இதற்கிடையில், ஹுசிமி மரம் என்ற பெயர் பொதுவாக ஒவ்வொரு தொகுதியும் ஒரு முழுமையான வரைபடமாக இருக்கும் வரைபடங்களைக் குறிக்கிறது (சமமாக, வேறு சில வரைபடத்தில் உள்ள தொகுதிகளின் குறுக்குவெட்டு வரைபடங்கள்). இந்த பயன்பாடு ஹுசிமியின் பணியுடன் சிறிதும் தொடர்புபடுத்தப்படவில்லை, மேலும் மிகவும் பொருத்தமான சொல் பிளாக் கிராஃப் இப்போது இந்த குடும்பத்திற்கு பயன்படுத்தப்படுகிறது; இருப்பினும், இந்த தெளிவின்மை காரணமாக இந்த சொற்றொடர் கற்றாழை வரைபடங்களைக் குறிக்க குறைவாகவே பயன்படுத்தப்படுகிறது. குறிப்புகள் வெளிப்புற இணைப்புகள் மின்னணு சுற்றுகளின் பகுப்பாய்வு மற்றும் வடிவமைப்பில் கற்றாழை வரைபடங்களின் பயன்பாடு வரைபட குடும்பங்கள் பிளானர் வரைபடங்கள் ஒருங்கிணைந்த சுற்றுகள்