Degree (graph theory)
வரைபடக் கோட்பாட்டில், ஒரு வரைபடத்தின் உச்சியின் டிகிரி (அல்லது இணைவு) என்பது உச்சிக்கு நிகரான விளிம்புகளின் எண்ணிக்கை; ஒரு பன்முக எழுத்தில், ஒரு வளையம் ஒரு உச்சியின் டிகிரிக்கு 2 பங்களிக்கிறது, விளிம்பின் இரண்டு முனைகளுக்கு. ஒரு உச்சியின் அளவு குறிக்கப்படுகிறது அல்லது. ஒரு வரைபடத்தின் அதிகபட்ச டிகிரி, குறிக்கப்படுகிறது, மற்றும் ஒரு வரைபடத்தின் குறைந்தபட்ச டிகிரி, குறிக்கப்படுகிறது, அதன் செங்குத்துகளின் டிகிரிகளின் அதிகபட்ச மற்றும் குறைந்தபட்சம் ஆகும். வலதுபுறத்தில் காட்டப்பட்டுள்ள பன்முகக் கல்வியில், அதிகபட்ச டிகிரி 5 ஆகவும், குறைந்தபட்ச டிகிரி 0 ஆகவும் உள்ளது. ஒரு வழக்கமான வரைபடத்தில், ஒவ்வொரு உச்சியும் ஒரே டிகிரியைக் கொண்டுள்ளது, எனவே வரைபடத்தின் டிகிரியைப் பற்றி நாம் பேசலாம். ஒரு முழுமையான வரைபடம் (குறிக்கப்படுகிறது, வரைபடத்தில் செங்குத்துகளின் எண்ணிக்கை எங்கே) என்பது ஒரு சிறப்பு வகையான வழக்கமான வரைபடமாகும், இதில் அனைத்து செங்குத்துகளும் அதிகபட்ச சாத்தியமான டிகிரியைக் கொண்டுள்ளன. கையொப்பமிடப்பட்ட வரைபடத்தில், உச்சியுடன் இணைக்கப்பட்ட நேர்மறை விளிம்புகளின் எண்ணிக்கை நேர்மறை டிகிரி என்றும் இணைக்கப்பட்ட எதிர்மறை விளிம்புகளின் எண்ணிக்கை எதிர்மறை டிகிரி என்றும் அழைக்கப்படுகிறது. கைகுலுக்கும் லெம்மா டிகிரி கூட்டுத்தொகை சூத்திரம் ஒரு வரைபடத்தைக் கொடுத்தால், என்று கூறுகிறது. இந்த சூத்திரம் எந்தவொரு திசைதிருப்பப்படாத வரைபடத்திலும், ஒற்றைப்படை டிகிரி கொண்ட செங்குத்துகளின் எண்ணிக்கை சமம் என்பதைக் குறிக்கிறது. இந்த கூற்று (அதே போல் டிகிரி கூட்டுத்தொகை சூத்திரம்) கைகுலுக்கும் லெம்மா என்று அழைக்கப்படுகிறது. பிந்தைய பெயர் ஒரு பிரபலமான கணித சிக்கலில் இருந்து வருகிறது, இது எந்தவொரு குழுவிலும், குழுவில் இருந்து ஒற்றைப்படை எண்ணிக்கையிலான மற்றவர்களுடன் கைகளை அசைத்த நபர்களின் எண்ணிக்கை சமம் என்பதை நிரூபிக்கிறது. டிகிரி வரிசை ஒரு திசைதிருப்பப்படாத வரைபடத்தின் டிகிரி வரிசை என்பது அதன் உச்சநிலை டிகிரிகளின் அதிகரிக்காத வரிசை; மேலே உள்ள வரைபடத்திற்கு இது (5,3,3,2,2,1,0). டிகிரி வரிசை ஒரு வரைபட மாறாதது, எனவே ஐசோமார்பிக் வரைபடங்கள் ஒரே டிகிரி வரிசையைக் கொண்டுள்ளன. இருப்பினும், டிகிரி வரிசை பொதுவாக, ஒரு வரைபடத்தை தனித்துவமாக அடையாளம் காணவில்லை; சில சந்தர்ப்பங்களில், ஐசோமார்பிக் அல்லாத வரைபடங்கள் ஒரே டிகிரி வரிசையைக் கொண்டுள்ளன. டிகிரி வரிசை சிக்கல் என்பது சில அல்லது அனைத்து வரைபடங்களையும் கண்டுபிடிப்பதில் உள்ள சிக்கலாகும், டிகிரி வரிசை நேர்மறை முழு எண்களின் கொடுக்கப்பட்ட அதிகரிக்காத வரிசையாக உள்ளது. (பின்தங்கிய பூஜ்ஜியங்கள் புறக்கணிக்கப்படலாம், ஏனெனில் அவை வரைபடத்தில் பொருத்தமான எண்ணிக்கையிலான தனிமைப்படுத்தப்பட்ட செங்குத்துகளைச் சேர்ப்பதன் மூலம் அற்பமாக உணரப்படுகின்றன.) ஒரு வரிசை என்பது சில வரைபடத்தின் டிகிரி வரிசை, அதாவது. இதற்கு டிகிரி வரிசை சிக்கலுக்கு ஒரு தீர்வு உள்ளது, இது கிராஃபிக் அல்லது கிராஃபிகல் வரிசை என்று அழைக்கப்படுகிறது. டிகிரி கூட்டுத்தொகை சூத்திரத்தின் விளைவாக, (3,3,1) போன்ற ஒற்றைப்படை கூட்டுத்தொகை கொண்ட எந்தவொரு வரிசையையும் ஒரு வரைபடத்தின் டிகிரி வரிசையாக உணர முடியாது. தலைகீழ் உண்மையும் கூடஃ ஒரு வரிசை சமமான கூட்டுத்தொகையைக் கொண்டிருந்தால், அது ஒரு பன்மடங்கு எழுத்தின் டிகிரி வரிசை. அத்தகைய வரைபடத்தின் கட்டுமானம் நேரடியானதுஃ செங்குத்துகளை ஒற்றைப்படை டிகிரிகளுடன் ஜோடியாக இணைக்கவும் (பொருத்தத்தை உருவாக்குகிறது), மீதமுள்ள சம டிகிரி எண்ணிக்கையை சுய-சுழல்கள் மூலம் நிரப்பவும். கொடுக்கப்பட்ட டிகிரி வரிசையை ஒரு எளிய வரைபடத்தால் உணர முடியுமா என்ற கேள்வி மிகவும் சவாலானது. இந்த சிக்கல் வரைபட உணர்தல் சிக்கல் என்றும் அழைக்கப்படுகிறது, மேலும் எர்டாஸ்-கல்லாய் தேற்றம் அல்லது ஹாவெல்-ஹாக்கிமி வழிமுறை மூலம் தீர்க்கப்படலாம். கொடுக்கப்பட்ட டிகிரி வரிசையுடன் வரைபடங்களின் எண்ணிக்கையைக் கண்டுபிடிப்பதில் அல்லது மதிப்பிடுவதில் உள்ள சிக்கல் வரைபடக் கணக்கீட்டு துறையில் உள்ள ஒரு சிக்கலாகும். மேலும் பொதுவாக, ஒரு ஹைபர் கிராஃப்பின் டிகிரி வரிசை என்பது அதன் உச்சி டிகிரிகளின் அதிகரிக்காத வரிசையாகும். ஒரு வரிசை சில-சீரான ஹைப்பர் கிராஃப்பின் டிகிரி வரிசையாக இருந்தால் அது-கிராஃபிக் ஆகும். குறிப்பாக, ஒரு-கிராஃபிக் வரிசை கிராஃபிக் ஆகும். கொடுக்கப்பட்ட வரிசை-கிராஃபிக் என்பதை தீர்மானிப்பது எர்டாஸ்-கல்லாய் தேற்றம் வழியாக பல்லுறுப்புக்கோவை நேரத்தில் செய்யக்கூடியது, ஆனால் அனைவருக்கும் NP-முழுமையானது. சிறப்பு மதிப்புகள் 0 டிகிரி கொண்ட ஒரு உச்சி தனிமைப்படுத்தப்பட்ட உச்சி என்று அழைக்கப்படுகிறது. டிகிரி 1 கொண்ட ஒரு உச்சி இலை உச்சி அல்லது இறுதி உச்சி அல்லது பதக்க உச்சி என்று அழைக்கப்படுகிறது, மேலும் அந்த உச்சியுடன் விளிம்பு நிகழ்வு பதக்க விளிம்பு என்று அழைக்கப்படுகிறது. வலதுபுறத்தில் உள்ள வரைபடத்தில், {3,5} ஒரு பதக்க விளிம்பாகும். வரைபடக் கோட்பாட்டில் மரங்கள் மற்றும் குறிப்பாக மரங்களை தரவு கட்டமைப்புகளாகப் படிப்பதில் இந்த சொல் பொதுவானது. n செங்குத்துகளில் ஒரு வரைபடத்தில் n-1 டிகிரி கொண்ட ஒரு உச்சி ஒரு ஆதிக்கம் செலுத்தும் உச்சி என்று அழைக்கப்படுகிறது. உலகளாவிய பண்புகள் வரைபடத்தின் ஒவ்வொரு முனையும் ஒரே டிகிரி k ஐக் கொண்டிருந்தால், வரைபடம் ஒரு k-வழக்கமான வரைபடம் என்றும், வரைபடமே டிகிரி k ஐக் கொண்டிருப்பதாகவும் கூறப்படுகிறது. இதேபோல், இருதரப்பு வரைபடம், இதில் இருதரப்பு செங்குத்துகளின் ஒரே பக்கத்தில் உள்ள ஒவ்வொரு இரண்டு செங்குத்துகளும் ஒரே டிகிரியைக் கொண்டுள்ளன, இது இருதரப்பு வரைபடம் என்று அழைக்கப்படுகிறது. திசைதிருப்பப்படாத, இணைக்கப்பட்ட வரைபடம் ஒற்றைப்படை டிகிரியின் 0 அல்லது 2 செங்குத்துகளைக் கொண்டிருந்தால் மட்டுமே அது ஒரு யூலேரியன் பாதையைக் கொண்டுள்ளது. இது ஒற்றைப்படை டிகிரியின் 0 செங்குத்துகளைக் கொண்டிருந்தால், யூலேரியன் பாதை ஒரு யூலேரியன் சுற்று ஆகும். ஒவ்வொரு முனையிலும் அதிகபட்சம் 1 டிகிரி வெளிப்புறம் இருந்தால் மட்டுமே ஒரு இயக்கப்படும் வரைபடம் ஒரு இயக்கப்படும் போலி காடு ஆகும். ஒரு செயல்பாட்டு வரைபடம் என்பது ஒரு போலி காடுகளின் ஒரு சிறப்பு வழக்கு, இதில் ஒவ்வொரு உச்சியும் சரியாக 1 டிகிரியைக் கொண்டுள்ளது. ப்ரூக்ஸின் தேற்றத்தின்படி, ஒரு கிளைக் அல்லது ஒற்றைப்படை சுழற்சியைத் தவிர வேறு எந்த வரைபடமும் அதிகபட்சமாக α (G) நிற எண்ணைக் கொண்டுள்ளது, மேலும் வைசிங்கின் தேற்றத்தின்படி எந்த வரைபடமும் அதிகபட்சமாக α (G) + 1 நிறக் குறியீட்டைக் கொண்டுள்ளது. ஒரு கே-டிஜெனரேட் வரைபடம் என்பது ஒரு வரைபடமாகும், இதில் ஒவ்வொரு துணை வரைபடமும் அதிகபட்சமாக k இல் டிகிரியின் உச்சியைக் கொண்டுள்ளது. மேலும் காண்க, இருதரப்பு வரைபடங்களுக்கான டிகிராப்ஸ் டிகிரி டிஸ்ட்ரிபியூஷன் டிகிரி வரிசைக்கான அவுட் டிகிரி குறிப்புகள் குறிப்புகள். . . வரைபடக் கோட்பாடு