ஒரு திசையற்ற கோட்டுருவின் எந்த இரு கணுக்களும் "ஒரேயொரு" பாதையால் மட்டுமே இணைக்கப்பட்டிருந்தால் அந்த திசையற்ற கோட்டுருவானது மரம் (tree) எனப்படும். "இணைப்புள்ள சுழலாத் திசையற்ற கோட்டுரு" எனவும் மரம் வரையறுக்கப்படுகிறது[1].
பன்மரம்[2] (திசையுறு மரம்[3], திசைசார் மரம்[4][5], ஒற்றை இணைப்பு வலையமைப்பு[6]) என்பது ஒரு திசையுள்ள சுழலாக் கோட்டுரு ஆகும். இதிலுள்ள திசையற்ற கோட்டுவானது ஒரு மர அமைப்பாக இருக்கும்.
மரங்களின் பொதுவற்ற ஒன்றிப்பு "காடு" எனப்படுகிறது. மேலும் "அதிகபட்சம்" ஒரு பாதையால் இணைக்கப்பட்ட முனைகளைக் கொண்ட திசையற்ற கோட்டுரு அல்லது திசையற்ற சுழலாக் கோட்டுரு எனவும் காடு வரையறுக்கப்படுகிறது.[7]
பல்காடு (திசையுறு காடு, திசைசார் காடு) என்பது ஒரு திசையுள்ள சுழலாக் கோட்டுருவாக இருக்கும். இந்தக் கோட்டுருவிலுள்ள திசையற்ற கோட்டுருவானது ஒரு காடாக இருக்கும்.
மரம் என்பதற்கு இணையான ஆங்கிலப் பெயரான "tree" என்பது 1857 இல் பிரித்தானியக் கணிதவியலாளர் ஆர்தர் கெய்லியால் உருவாக்கப்பட்டது.[8]
வரையறைகள்
மரம்
திசையற்ற கோட்டுருவான G என்பது ஒரு மரமாக இருக்கவேண்டுமானால் பின்வரும் கட்டுப்பாடுகளில் எதேனும் ஒன்றை நிறைவு செய்ய வேண்டும்:
G - இணைப்புள்ள சுழலாக் கோட்டுரு .
G - சுழலாக் கோட்டுரு; மற்றும் G இல் ஏதேனுமொரு விளிம்பு சேர்க்கப்படும்பொழுது எளிய சுழல் கோட்டுருவாதல்.
G இணைப்புள்ள கோட்டுரு; ஆனால் G இலிருந்து ஏதேனுமொரு விளிம்பு நீக்கப்படும்போது இணைப்பற்ற கோட்டுருவாதல்.
G இன் எந்த இரு கணுக்களும் தனித்ததொரு பாதையால் இணைக்கப்படக்கூடியதாக இருக்க வேண்டும்.
G இல் முடிவறு எண்ணிக்கையில் கணுக்கள் இருக்குமானால் மேலே தரப்பட்ட கூற்றுகளுக்குச் சமானமானவையாக பின்வருபவை அமையும்.
கணுக்களின் எண்ணிக்கை n எனில்:
G இணைப்புள்ளது மற்றும் n − 1 விளிம்புகளுடையது.
G இணைப்புள்ளது மற்றும் அதன் ஒவ்வொரு உட்கோட்டுருவும் குறைந்தபட்சம், "0" அல்லது "1" படுகை விளிம்புகொண்ட ஒரு கணுவையாவது கொண்டிருக்கும்.
G க்கு எளிய சுழல்களே கிடையாது மற்றும் n − 1 விளிம்புகள் இருக்கும்.
ஒரு மரத்தின் "உள்முனை" ("உட்கணு", "கிளைமுனை", "கிளைக்கணு") என்பது குறைந்தபட்சம் இரு படியுடைய கணுக்கள்; "வெளிமுனை" ("வெளிக்கணு", இறுதிக்கணு, இலை) என்பது ஒரு படியுடைய கணுக்கள்.
இரண்டு படிகொண்ட கணுக்கள் இல்லாத மரங்கள் "குறைக்கவியலா மரம்" எனப்படுகின்றன.[9]
காடு
காடு
ஒரு திசையற்ற கோட்டுருவின் எந்தவிரு கணுக்களும் அதிகபட்சம் ஒரு பாதையால் இணைக்கப்படக்கூடியவையாக இருப்பின் அந்தக் கோட்டுரு "காடு" எனப்படும். ஒரு காட்டினைத் திசையற்ற சுழலாக் கோட்டுரு எனவும், திசையற்ற கோட்டுருவொன்றின் அனைத்து இணைப்புள்ள கூறுகளும் மரங்களாக இருப்பின் அக்கோட்டுருவைக் காடு எனவும் வரையறுக்கலாம்.
கோட்டுருவியலில் "காடு" என்பது பின்வரும் மூன்று விதங்களில் வரையறுக்கப்படுகிறது:
அதிகபட்சம் ஒரு பாதையால் இணைக்கப்பட்ட கணுக்களைக் கொண்ட திசையற்ற கோட்டுரு
ஒவ்வொரு மரத்திற்கும் அதன் கணுக்களின் (V) எண்ணிக்கையானது அதன் விளிம்புகளின் (E) எண்ணிக்கையைவிட ஒன்று அதிகமாக இருக்கும். (V − E = 1). இதன்மூலம் ஒரு காட்டிலுள்ள மரங்களின் எண்ணிக்கையை எளிதாகக் கணக்கிடலாம். காட்டின் மொத்த கணுக்களின் எண்ணிக்கைக்கும் மொத்த விளிம்புகளின் எண்ணிக்கைக்கும் உள்ள வித்தியாசமே அக்காட்டிலுள்ள மரங்களின் எண்ணிக்கை ஆகும்.
i , i+1 (i=1,...,n−1.) ஆகிய இரு கணுக்களும் ஒரு விளிம்பால் இணைக்கப்படும்வகையில் n கணுக்களும் ஒரு கோட்டில் வரிசைப்படுத்தப்பட்டிருக்கும்.
விண்மீனொத்த மரம்
விண்மீனொத்த மரம் "வேர்" எனப்படும் நடுக்கணு உடையது. இந்த நடுக்கணுவோடு பல பாதைக் கோட்டுருக்கள் சேர்க்கப்பட்டிருக்கும். இந்த மரம் இரண்டிற்கும் அதிகமான படியுடையதாக ஒரேயொரு கணுவை மட்டுமே கொண்டிருக்கும்.
↑Cayley (1857) "On the theory of the analytical forms called trees,"Philosophical Magazine, 4th series, 13 : 172–176. However it should be mentioned that in 1847, K.G.C. von Staudt, in his book Geometrie der Lage (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on pages 20–21. Also in 1847, the German physicist குசுத்தாவ் கிர்க்காஃப் investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), Annalen der Physik und Chemie, 72 (12) : 497–508.
Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR0603363.
