மரம் (கோட்டுருவியல்)
{{infobox graph
  | name = மரங்கள்
  | image = [[File:Tree graph.svg|180px]]
  | image_caption = 6 உச்சிகள், 5 விளிம்புகள் கொண்ட பெயரிடப்பட்ட மரம்
  | vertices = ''v''
  | edges = ''v''&amp;nbsp;−&amp;nbsp;1
  | radius = 
  | diameter = 
  | girth = 
  | chromatic_number = 2 , ''v'' &gt; 1
  | chromatic_index = 
  | properties = 
 }}
 
 ஒரு [[கோட்டுரு (கணிதம்)|திசையற்ற கோட்டுருவின்]]  எந்த இரு [[கணு (கோட்டுருவியல்)|கணுக்களும்]] &quot;ஒரேயொரு&quot; [[பாதை (கோட்டுருவியல்)|பாதையால்]] மட்டுமே இணைக்கப்பட்டிருந்தால் அந்த திசையற்ற கோட்டுருவானது '''மரம்''' (''tree'') எனப்படும். &quot;இணைப்புள்ள சுழலாத் திசையற்ற கோட்டுரு&quot; எனவும் மரம் வரையறுக்கப்படுகிறது{{sfn|Bender|Williamson|2010|p=171}}. 
 
 [[பன்மரம்]]&lt;ref name=&quot;d99&quot;&gt;See {{harvtxt|Dasgupta|1999}}.&lt;/ref&gt; (''திசையுறு மரம்''{{sfn|Deo|1974|p=206}}, ''திசைசார் மரம்''&lt;ref name=&quot;Harary 1980&quot;&gt;See {{harvtxt|Harary|Sumner|1980}}.&lt;/ref&gt;&lt;ref name=&quot;s91&quot;&gt;See {{harvtxt|Simion|1991}}.&lt;/ref&gt;, ''ஒற்றை இணைப்பு வலையமைப்பு''&lt;ref name=&quot;kp83&quot;&gt;See {{harvtxt|Kim|Pearl|1983}}.&lt;/ref&gt;) என்பது ஒரு திசையுள்ள சுழலாக் கோட்டுரு ஆகும். இதிலுள்ள திசையற்ற கோட்டுவானது ஒரு மர அமைப்பாக இருக்கும்.
 
 மரங்களின்  [[கோட்டுருக்களின் பொதுவற்ற ஒன்றிப்பு|பொதுவற்ற ஒன்றிப்பு]] &quot;காடு&quot; எனப்படுகிறது. மேலும் &quot;அதிகபட்சம்&quot; ஒரு [[பாதை (கோட்டுருவியல்)|பாதையால்]] இணைக்கப்பட்ட முனைகளைக் கொண்ட திசையற்ற கோட்டுரு அல்லது  திசையற்ற சுழலாக் கோட்டுரு எனவும் காடு வரையறுக்கப்படுகிறது.{{sfn|Bender|Williamson|2010|p=172}}
  
 ''பல்காடு'' (''திசையுறு காடு'', ''திசைசார் காடு'') என்பது ஒரு திசையுள்ள சுழலாக் கோட்டுருவாக இருக்கும். இந்தக் கோட்டுருவிலுள்ள திசையற்ற கோட்டுருவானது ஒரு காடாக இருக்கும்.
 
 மரம் என்பதற்கு இணையான ஆங்கிலப் பெயரான &quot;tree&quot; என்பது 1857 இல் பிரித்தானியக் கணிதவியலாளர் [[ஆர்தர் கெய்லி]]யால் உருவாக்கப்பட்டது.&lt;ref&gt;Cayley (1857) [https://books.google.com/books?id=MlEEAAAAYAAJ&amp;pg=PA172#v=onepage&amp;q&amp;f=false &quot;On the theory of the analytical forms called trees,&quot;] ''Philosophical Magazine'', 4th series, '''13''' : 172–176.&lt;br&gt;However it should be mentioned that in 1847, [[Karl Georg Christian von Staudt|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 [https://books.google.com/books?id=MzQAAAAAQAAJ&amp;pg=PA20#v=onepage&amp;q&amp;f=false 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) [https://books.google.com/books?id=gx4AAAAAMAAJ&amp;vq=Kirchoff&amp;pg=PA497#v=onepage&amp;q&amp;f=false &quot;Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird&quot;] (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.&lt;/ref&gt;
 
 == வரையறைகள் ==
 === மரம் ===
 திசையற்ற கோட்டுருவான ''G'' என்பது ஒரு மரமாக இருக்கவேண்டுமானால் பின்வரும் கட்டுப்பாடுகளில் எதேனும் ஒன்றை நிறைவு செய்ய வேண்டும்:
 * ''G'' - இணைப்புள்ள சுழலாக் கோட்டுரு .
 * ''G'' - சுழலாக் கோட்டுரு; மற்றும் ''G'' இல் ஏதேனுமொரு [[விளிம்பு (கோட்டுருவியல்)|விளிம்பு]] சேர்க்கப்படும்பொழுது எளிய சுழல் கோட்டுருவாதல்.
 * ''G'' இணைப்புள்ள கோட்டுரு; ஆனால் ''G'' இலிருந்து ஏதேனுமொரு விளிம்பு நீக்கப்படும்போது இணைப்பற்ற கோட்டுருவாதல்.
 * ''G'' இன் எந்த இரு கணுக்களும் தனித்ததொரு பாதையால் இணைக்கப்படக்கூடியதாக இருக்க வேண்டும்.
 
 ''G'' இல் முடிவறு எண்ணிக்கையில்  கணுக்கள் இருக்குமானால் மேலே தரப்பட்ட கூற்றுகளுக்குச் சமானமானவையாக பின்வருபவை அமையும். 
 கணுக்களின் எண்ணிக்கை ''n'' எனில்:
 * ''G'' இணைப்புள்ளது மற்றும் {{nowrap|''n'' − 1}} விளிம்புகளுடையது.
 * ''G'' இணைப்புள்ளது மற்றும் அதன் ஒவ்வொரு உட்கோட்டுருவும் குறைந்தபட்சம், &quot;0&quot; அல்லது &quot;1&quot; படுகை விளிம்புகொண்ட ஒரு கணுவையாவது கொண்டிருக்கும்.
 * ''G'' க்கு எளிய சுழல்களே கிடையாது மற்றும்  {{nowrap|''n'' − 1}} விளிம்புகள் இருக்கும்.
 
 ஒரு மரத்தின் &quot;உள்முனை&quot; (&quot;உட்கணு&quot;, &quot;கிளைமுனை&quot;, &quot;கிளைக்கணு&quot;) என்பது குறைந்தபட்சம் இரு [[படி (கோட்டுருவியல்)|படியுடைய]] கணுக்கள்; &quot;வெளிமுனை&quot; (&quot;வெளிக்கணு&quot;, இறுதிக்கணு, இலை) என்பது ஒரு படியுடைய கணுக்கள்.
 
 இரண்டு படிகொண்ட கணுக்கள் இல்லாத மரங்கள் &quot;குறைக்கவியலா மரம்&quot; எனப்படுகின்றன.{{sfn|Harary|Prins|1959|p=150}}
 
 === காடு ===
 [[File:Arbres plans.png|thumb|200px|காடு]]
 ஒரு திசையற்ற கோட்டுருவின் எந்தவிரு கணுக்களும் அதிகபட்சம் ஒரு பாதையால் இணைக்கப்படக்கூடியவையாக இருப்பின் அந்தக் கோட்டுரு &quot;காடு&quot; எனப்படும். ஒரு காட்டினைத் திசையற்ற சுழலாக் கோட்டுரு எனவும், திசையற்ற கோட்டுருவொன்றின் அனைத்து இணைப்புள்ள கூறுகளும் மரங்களாக இருப்பின் அக்கோட்டுருவைக் காடு எனவும் வரையறுக்கலாம்.
 
 கோட்டுருவியலில் &quot;காடு&quot; என்பது பின்வரும் மூன்று விதங்களில் வரையறுக்கப்படுகிறது:
 *அதிகபட்சம் ஒரு [[பாதை (கோட்டுருவியல்)|பாதையால்]] இணைக்கப்பட்ட கணுக்களைக் கொண்ட திசையற்ற கோட்டுரு
 *மரங்களின்  [[கோட்டுருக்களின் பொதுவற்ற ஒன்றிப்பு|பொதுவற்ற ஒன்றிப்பு]]
 *திசையற்ற சுழலாக் கோட்டுரு.
 
 சிறப்புவகைக் காடுகளின் எடுத்துக்காட்டுகள்:
 *வரிசை-0  கோட்டுரு (மரங்களற்ற காடு)
 *ஒரேயொரு மரங்கொண்ட காடு
 *விளிம்புகளற்ற கோட்டுரு 
 
 ஒவ்வொரு மரத்திற்கும் அதன் கணுக்களின் (''V'') எண்ணிக்கையானது அதன் விளிம்புகளின் (''E'') எண்ணிக்கையைவிட ஒன்று அதிகமாக இருக்கும். ({{nowrap|1=''V'' − ''E'' = 1}}). இதன்மூலம் ஒரு காட்டிலுள்ள மரங்களின் எண்ணிக்கையை எளிதாகக் கணக்கிடலாம். காட்டின் மொத்த கணுக்களின் எண்ணிக்கைக்கும் மொத்த விளிம்புகளின் எண்ணிக்கைக்கும் உள்ள வித்தியாசமே அக்காட்டிலுள்ள மரங்களின் எண்ணிக்கை ஆகும்.
 :{{nowrap|1=''TV'' − ''TE'' = ஒரு காட்டிலுள்ள மரங்களின் எண்ணிக்கை}}.
 
 ==மரங்களின் வகைகள் ==
 * ''[[பாதை கோட்டுரு]]''
 :''i'' , ''i''+1 (''i''=1,...,''n''&amp;minus;1.) ஆகிய இரு கணுக்களும் ஒரு விளிம்பால் இணைக்கப்படும்வகையில் ''n'' கணுக்களும் ஒரு கோட்டில் வரிசைப்படுத்தப்பட்டிருக்கும்.
 
 * ''விண்மீனொத்த மரம்'' 
 :விண்மீனொத்த மரம் &quot;வேர்&quot; எனப்படும் நடுக்கணு உடையது. இந்த நடுக்கணுவோடு பல பாதைக் கோட்டுருக்கள் சேர்க்கப்பட்டிருக்கும். இந்த மரம் இரண்டிற்கும் அதிகமான படியுடையதாக  ஒரேயொரு கணுவை மட்டுமே கொண்டிருக்கும்.
 
 * ''[[விண்மீன் கோட்டுரு|விண்மீன் மரம்]]''
 :ஒரேயொரு கிளைக்கணுவுடைய மரம்.
 
 * ''கம்பிளிப்புழு மரம்''
 :நடுப்பாதை உட்கோட்டுருவிலிருந்து அனைத்து கணுக்களும் ஒரு அலகு தூரத்திற்குள் அமைந்திருக்கும் மரம். 
 
 * ''கல் இறால் மரம்''
 :நடுப்பாதை உட்க்கோட்டுருவிலிருந்து அனைத்து கணுக்களும் இரு அலகு தூரத்திற்குள் அமைந்திருக்கும் மரம்.
 &lt;gallery&gt;
 Image:Path-graph.svg|150px|6 கணுக்களுடைய பாதைக் கோட்டுரு
 Image:Star network 7.svg|150px|விண்மீன் மரம்
 File:Caterpillar tree.svg|150px|கம்பிளிப்புழு மரம்
 &lt;/gallery&gt;
 
 == குறிப்புகள் ==
 {{reflist|30em}}
 
 == மேற்கோள்கள் ==
 * {{citation |last1=Bender |first1=Edward A. |last2=Williamson |first2=S. Gill |date=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.fr/books?id=vaXv_yhefG8C |location= |publisher= |page= |isbn= |author-link= }}
 * {{citation
  | last1 = Dasgupta| first1 = Sanjoy
  | contribution = Learning polytrees
  | pages = 134–141
  | title = in Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999
  | url = http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf
  | year = 1999}}.
 * {{citation |last=Deo |first=Narsingh |date=1974 |title=Graph Theory with Applications to Engineering and Computer Science |url=https://www.edutechlearners.com/download/Graphtheory.pdf |location=Englewood, New Jersey |publisher=Prentice-Hall |page= |isbn=0-13-363473-6 |author-link= }}
 *{{citation |last1=Harary |first1=Frank |author1-link=Frank Harary|last2=Prins |first2=Geert |title=The number of homeomorphically irreducible trees, and other species |journal=[[Acta Mathematica]] |date=1959 |volume=101 |issue=1-2 |pages=141–162 |doi=10.1007/BF02559543 |url=https://projecteuclid.org/euclid.acta/1485889061 |language=EN |issn=0001-5962|doi-access=free }}
 * {{citation
  | last1 = Harary | first1 = Frank | author1-link = Frank Harary
  | last2 = Sumner | first2 = David
  | mr = 603363
  | issue = 3
  | journal = Journal of Combinatorics, Information &amp; System Sciences
  | pages = 184–187
  | title = The dichromatic number of an oriented tree
  | volume = 5
  | year = 1980}}.
 * {{citation
  | last1 = Kim | first1 = Jin H.
  | last2 = Pearl | first2 = Judea
  | contribution = A computational model for causal and diagnostic reasoning in inference engines
  | pages = 190–193
  | title = in Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983
  | url = https://www.ijcai.org/Proceedings/83-1/Papers/041.pdf
  | year = 1983}}.
 * {{citation
  | last1 = Li | first1 = Gang
  | contribution = Generation of Rooted Trees and Free Trees
  | page = 9
  | title = M.S. Thesis, Dept. of Computer Science, University of Victoria, BC, Canada
  | url = http://webhome.cs.uvic.ca/~ruskey/Theses/GangLiMScThesis.pdf
  | year = 1996}}.
 * {{citation
  | last = Simion | first = Rodica | authorlink = Rodica Simion
  | doi = 10.1016/0012-365X(91)90061-6
  | mr = 1099270
  | issue = 1
  | journal = Discrete Mathematics
  | pages = 93–104
  | title = Trees with 1-factors and oriented trees
  | volume = 88
  | year = 1991}}.
 
 == வெளியிணைப்புகள் ==
 {{commons category|Tree (graph theory)}}
 * {{Citation | last1=Diestel | first1=Reinhard | title=Graph Theory | url=http://diestel-graph-theory.com/index.html | publisher=Springer-Verlag | location=Berlin, New York | edition=3rd | isbn=978-3-540-26183-4 | year=2005 }}.
 * {{citation | last1=Flajolet | first1= Philippe |last2=Sedgewick|first2=Robert| authorlink2=Robert_Sedgewick_(computer_scientist)| title=Analytic Combinatorics|title-link= Analytic Combinatorics | isbn=978-0-521-89806-5|year=2009|publisher=Cambridge University Press}}
 * {{springer|title=Tree|id=p/t094060|ref=none}}
 * {{citation | last=Knuth | first=Donald E. | authorlink=Donald_E._Knuth | title=The Art of Computer Programming Volume 1: Fundamental Algorithms | date=November 14, 1997 | publisher=Addison-Wesley Professional | edition=3rd}}
 * {{citation | doi=10.1016/0020-0190(94)00085-9 | last=Jerrum | first = Mark | year=1994 | title=Counting trees in a graph is #P-complete | journal=Information Processing Letters | volume=51 | issue=3 | pages=111–116 | issn=0020-0190 }}.
 * {{citation | first1=Richard | last1=Otter | year=1948 | title=The Number of Trees | journal=Annals of Mathematics |series=Second Series | volume=49 | issue=3 | pages=583–599 | doi=10.2307/1969046 | jstor=1969046 }}.