மரம் (கோட்டுருவியல்)
ஒரு திசையற்ற கோட்டுருவின் எந்த இரு கணுக்களும் "ஒரேயொரு" பாதையால் மட்டுமே இணைக்கப்பட்டிருந்தால் அந்த திசையற்ற கோட்டுருவானது மரம் (tree) எனப்படும். "இணைப்புள்ள சுழலாத் திசையற்ற கோட்டுரு" எனவும் மரம் வரையறுக்கப்படுகிறது[1].
| மரங்கள் | |
|---|---|
 6 உச்சிகள், 5 விளிம்புகள் கொண்ட பெயரிடப்பட்ட மரம் | |
| முனைகள் | v |
| விளிம்பு | v − 1 |
| நிற எண் | 2 , v > 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]
காடு
தொகு
ஒரு திசையற்ற கோட்டுருவின் எந்தவிரு கணுக்களும் அதிகபட்சம் ஒரு பாதையால் இணைக்கப்படக்கூடியவையாக இருப்பின் அந்தக் கோட்டுரு "காடு" எனப்படும். ஒரு காட்டினைத் திசையற்ற சுழலாக் கோட்டுரு எனவும், திசையற்ற கோட்டுருவொன்றின் அனைத்து இணைப்புள்ள கூறுகளும் மரங்களாக இருப்பின் அக்கோட்டுருவைக் காடு எனவும் வரையறுக்கலாம்.
கோட்டுருவியலில் "காடு" என்பது பின்வரும் மூன்று விதங்களில் வரையறுக்கப்படுகிறது:
- அதிகபட்சம் ஒரு பாதையால் இணைக்கப்பட்ட கணுக்களைக் கொண்ட திசையற்ற கோட்டுரு
- மரங்களின் பொதுவற்ற ஒன்றிப்பு
- திசையற்ற சுழலாக் கோட்டுரு.
சிறப்புவகைக் காடுகளின் எடுத்துக்காட்டுகள்:
- வரிசை-0 கோட்டுரு (மரங்களற்ற காடு)
- ஒரேயொரு மரங்கொண்ட காடு
- விளிம்புகளற்ற கோட்டுரு
ஒவ்வொரு மரத்திற்கும் அதன் கணுக்களின் (V) எண்ணிக்கையானது அதன் விளிம்புகளின் (E) எண்ணிக்கையைவிட ஒன்று அதிகமாக இருக்கும். (V − E = 1). இதன்மூலம் ஒரு காட்டிலுள்ள மரங்களின் எண்ணிக்கையை எளிதாகக் கணக்கிடலாம். காட்டின் மொத்த கணுக்களின் எண்ணிக்கைக்கும் மொத்த விளிம்புகளின் எண்ணிக்கைக்கும் உள்ள வித்தியாசமே அக்காட்டிலுள்ள மரங்களின் எண்ணிக்கை ஆகும்.
- TV − TE = ஒரு காட்டிலுள்ள மரங்களின் எண்ணிக்கை.
மரங்களின் வகைகள்
தொகு- i , i+1 (i=1,...,n−1.) ஆகிய இரு கணுக்களும் ஒரு விளிம்பால் இணைக்கப்படும்வகையில் n கணுக்களும் ஒரு கோட்டில் வரிசைப்படுத்தப்பட்டிருக்கும்.
- விண்மீனொத்த மரம்
- விண்மீனொத்த மரம் "வேர்" எனப்படும் நடுக்கணு உடையது. இந்த நடுக்கணுவோடு பல பாதைக் கோட்டுருக்கள் சேர்க்கப்பட்டிருக்கும். இந்த மரம் இரண்டிற்கும் அதிகமான படியுடையதாக ஒரேயொரு கணுவை மட்டுமே கொண்டிருக்கும்.
- ஒரேயொரு கிளைக்கணுவுடைய மரம்.
- கம்பிளிப்புழு மரம்
- நடுப்பாதை உட்கோட்டுருவிலிருந்து அனைத்து கணுக்களும் ஒரு அலகு தூரத்திற்குள் அமைந்திருக்கும் மரம்.
- கல் இறால் மரம்
- நடுப்பாதை உட்க்கோட்டுருவிலிருந்து அனைத்து கணுக்களும் இரு அலகு தூரத்திற்குள் அமைந்திருக்கும் மரம்.
-
6 கணுக்களுடைய பாதைக் கோட்டுரு -
விண்மீன் மரம் -
கம்பிளிப்புழு மரம்
குறிப்புகள்
தொகு- ↑ Bender & Williamson 2010, ப. 171.
- ↑ See (Dasgupta 1999).
- ↑ Deo 1974, ப. 206.
- ↑ See (Harary & Sumner 1980).
- ↑ See (Simion 1991).
- ↑ See (Kim & Pearl 1983).
- ↑ Bender & Williamson 2010, ப. 172.
- ↑ 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 & Prins 1959, ப. 150.
மேற்கோள்கள்
தொகு- Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability
- Dasgupta, Sanjoy (1999), "Learning polytrees", in Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999 (PDF), pp. 134–141.
- Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, பன்னாட்டுத் தரப்புத்தக எண் 0-13-363473-6
- Harary, Frank; Prins, Geert (1959), "The number of homeomorphically irreducible trees, and other species", Acta Mathematica (in ஆங்கிலம்), 101 (1–2): 141–162, எண்ணிம ஆவணச் சுட்டி:10.1007/BF02559543, பன்னாட்டுத் தர தொடர் எண் 0001-5962
- Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 0603363.
- Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines", in Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 (PDF), pp. 190–193.
- Li, Gang (1996), "Generation of Rooted Trees and Free Trees", M.S. Thesis, Dept. of Computer Science, University of Victoria, BC, Canada (PDF), p. 9.
- Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics, 88 (1): 93–104, எண்ணிம ஆவணச் சுட்டி:10.1016/0012-365X(91)90061-6, MR 1099270.
வெளியிணைப்புகள்
தொகு
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, பன்னாட்டுத் தரப்புத்தக எண் 978-3-540-26183-4.
- Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, பன்னாட்டுத் தரப்புத்தக எண் 978-0-521-89806-5
- Hazewinkel, Michiel, ed. (2001), "Tree", Encyclopedia of Mathematics, Springer, பன்னாட்டுத் தரப்புத்தக எண் 978-1556080104
- Knuth, Donald E. (November 14, 1997), The Art of Computer Programming Volume 1: Fundamental Algorithms (3rd ed.), Addison-Wesley Professional
- Jerrum, Mark (1994), "Counting trees in a graph is #P-complete", Information Processing Letters, 51 (3): 111–116, எண்ணிம ஆவணச் சுட்டி:10.1016/0020-0190(94)00085-9, பன்னாட்டுத் தர தொடர் எண் 0020-0190.
- Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series, 49 (3): 583–599, எண்ணிம ஆவணச் சுட்டி:10.2307/1969046, JSTOR 1969046.