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