படி (கோட்டுருவியல்)

கோட்டுருவில் ஒரு கணுவின் படுகை விளிம்புகளின் எண்ணிக்கை அக்கணுவின் படி (degree, valency) ஆகும். பல்கோட்டுருக்களில் படி கணக்கிடும்போது ஒரு கணுவில் கண்ணிகள் இருக்குமானால் அக்கண்ணிகள் இருமுறை எண்ணப்படுகின்றன. கணு $v$ இன் படியின் குறியீடு: $\deg(v)$ அல்லது $\deg v$.

படிகளைக் கொண்டு பெயரிடப்பட்ட கணுக்களுடன் ஒரு பல்கோட்டுரு

$G$ என்ற கோட்டுருவின் "பெருமப் படி" என்பது அதன் கணுக்களின் படிகளின் பெரும மதிப்பாகும்; இதன் குறியீடு: $\Delta (G)$ "சிறுமப் படி" என்பது அதன் கணுக்களின் படிகளின் சிறும மதிப்பாகும்; இதன் குறியீடு: $\delta (G)$படத்தில் உள்ள பல்கோட்டுருவின் பெருமப் படி 5; சிறுமப் படி 0.

ஒரு ஒழுங்கு கோட்டுருவில் எல்லாக் கணுக்களுமே சமமான படியுடைவை. ஒரு முழுக்கோட்டுருவின் எல்லாக் கணுக்களுமே பெருமப் படி கொண்டிருக்கும். இது ஒரு சிறப்புவகை ஒழுங்கு கோட்டுருவாகும். $K_{n}$ என்ற முழு கோட்டுருவில், கணுக்களின் எண்ணிக்கை $n$ ஆகவும் எல்லாக் கணுக்களின் பெருமப் படி $n-1$ ஆகவும் இருக்கும்.

திசையுறு கோட்டுருவில் படியானது "உட்படி", "வெளிப்படி" என வகைப்படுத்தப்படுகிறது.

உட்படி

ஒரு கணுவை நோக்கி அமையும் விளிம்புகளின் எண்ணிக்கை அக்கணுவின் உட்படியாகும். இதன் குறியீடு: deg⁻(v)

வெளிப்படி

ஒரு கணுவிலிருந்து செல்லும் விளிம்புகளின் எண்ணிக்கை அக்கணுவின் வெளிப்படியாகும். இதன் குறியீடு: deg⁺(v)

திசையுறா கோட்டுரு: 4, 5, 6, 7, 10, 11, 12 எண்ணுடையவை இலைக்கணுக்கள்.

இதில் ஒரேயொரு தனித்த கணு உள்ளது

சிறப்பு மதிப்புகள்

• படி = 0 எனில் அக்கணு "தனித்த கணு" எனப்படும்.
• படி = 1 எனில், அக்கணு "இலைக் கணு" அல்லது "இறுதிக் கணு" எனப்படும்.
• n கணுக்கள் கொண்ட கோட்டுருவிலுள்ள ஒரு கணுவின் படி = n − 1 எனில், அக்கணு, "ஓங்கு கணு" எனப்படும்.
• உட்படி = 0 எனில், அக்கணு, "ஊற்று கணு" (source vertex) எனப்படும்.
• 0 - வெளிப்படி = 0 எனில், அக்கணு, "உறிஞ்சு கணு" (sink vertex) எனப்படும்.

கைகொடுத்தல் தேற்றம்

முதன்மைக் கட்டுரை: கைகொடுத்தல் தேற்றம்

படிகளின் கூட்டுத்தொகை வாய்பாடு:

இவ்வாய்பாடின்படி, $G=(V,E)$ என்ற கோட்டுருவில்,

$\sum _{v\in V}\deg(v)=2|E|\,.$ ஆக இருக்கும்.

இதன்படி ஒரு திசையுறா கோட்டுருவில், ஒற்றையெண் படியுடைய கணுக்களின் எண்ணிக்கை இரட்டை எண்ணாக இருக்கும். இக்கூற்று கைகொடுத்தல் துணைத்தேற்றம் எனவும் அழைக்கப்படுகிறது. பேச்சு வழக்கில் கைகொடுத்தல் தேற்றப்படி, ஒரு கூட்டத்திலுள்ளவர்களில் சிலர் ஒருவருக்கொருவர் கைகொடுக்கும்போது ஒற்றைப்படை எண்ணிக்கையில் பிறநபர்களின் கைகளைத் தொட்ட நபர்களின் எண்ணிக்கையானது இரட்டைப்படை எண்ணாக இருக்கும்.

படிகளின் தொடர்வரிசை

(3, 2, 2, 2, 2, 1, 1, 1) என்ற படிகளின் தொடர்வரிசை கொண்ட இரு சம அமைவியமற்றக் கோட்டுருக்கள்.

ஒரு திசையுறா கோட்டுருவின் கணுக்களின் படிகளின் கூடாத் தொடர்வரிசையே அக்கோட்டுருவின் படிகளின் தொடர்வரிசை எனப்படும். படத்தில் தரப்பட்டுள்ள கோட்டுருவின் படிகளின் தொடர்வரிசை: (5, 3, 3, 2, 2, 1, 0). படிகளின் தொடர்வரிசை என்பது கோட்டுரு பண்பு என்பதால் சம அமைவியக் கோட்டுருக்கள் எல்லாம் ஒரே படிகளின் தொடர்வரிசை கொண்டிருக்கும். எனினும் படிகளின் தொடர்வரிசை கோட்டுருக்களைத் தனித்து அடையாளப்படுத்துவதில்லை; சில சம அமைவியமற்ற கோட்டுருக்களின் படிகளின் தொடர்வரிசையும் ஒன்றாக இருக்கும்.

மேற்கோள்கள்

• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
• Erdős, P.; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok (Hungarian), 11: 264–274CS1 maint: Unrecognized language (link).
• Havel, Václav (1955), "A remark on the existence of finite graphs", Časopis pro pěstování matematiky (Czech), 80: 477–480CS1 maint: Unrecognized language (link)
• Hakimi, S. L. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics, 10: 496–506, MR 0148049.
• Sierksma, Gerard; Hoogeveen, Han (1991), "Seven criteria for integer sequences being graphic", Journal of Graph Theory, 15 (2): 223–231, doi:10.1002/jgt.3190150209, MR 1106533.