Editing Tree (graph theory) (section)

{{Short description|Undirected, connected and acyclic graph}}
{{For|abstract data type|Tree (abstract data type)}}{{Distinguish|text=[[Trie]], a specific type of tree data structure}}
{{Infobox graph
 | name = Trees
 | image = [[File:Tree graph.svg|180px]]
 | image_caption = A labeled tree with 6 vertices and 5 edges.
 | vertices = ''v''
 | edges = ''v''&nbsp;−&nbsp;1
 | radius = 
 | diameter = 
 | girth = 
 | chromatic_number = 2 if ''v'' > 1
 | chromatic_index = 
 | properties = 
}}

In [[graph theory]], a '''tree''' is an [[undirected graph]] in which any two [[Vertex (graph theory)|vertices]] are connected by {{em|exactly one}} [[Path (graph theory)|path]], or equivalently a [[Connected graph|connected]] [[Cycle (graph theory)|acyclic]] undirected graph.{{sfn|Bender|Williamson|2010|p=171}} A '''forest''' is an undirected graph in which any two vertices are connected by {{em|at most one}} path, or equivalently an acyclic undirected graph, or equivalently a [[Disjoint union of graphs|disjoint union]] of trees.{{sfn|Bender|Williamson|2010|p=172}}

A directed tree,{{sfn|Deo|1974|p=206}} oriented tree,<ref name="Harary 1980">See {{harvtxt|Harary|Sumner|1980}}.</ref><ref name="s91">See {{harvtxt|Simion|1991}}.</ref> [[polytree]],<ref name="d99">See {{harvtxt|Dasgupta|1999}}.</ref> or singly connected network<ref name="kp83">See {{harvtxt|Kim|Pearl|1983}}.</ref> is a [[directed acyclic graph]] (DAG) whose underlying undirected graph is a tree. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest.

The various kinds of [[data structures]] referred to as [[Tree (data structure)|trees]] in [[computer science]] have [[underlying graph]]s that are trees in graph theory, although such data structures are generally [[Tree (graph theory)#Rooted tree|rooted trees]]. A rooted tree may be directed, called a directed rooted tree,<ref name="Williamson1985">{{cite book|author=Stanley Gill Williamson|title=Combinatorics for Computer Science|year=1985|publisher=Courier Dover Publications|isbn=978-0-486-42076-9|page=288}}</ref><ref name="multi">{{cite book|author1=Mehran Mesbahi|author2=Magnus Egerstedt|title=Graph Theoretic Methods in Multiagent Networks|year=2010|publisher=Princeton University Press|isbn=978-1-4008-3535-5|page=38}}</ref> either making all its edges point away from the root—in which case it is called an [[Arborescence (graph theory)|arborescence]]{{sfn|Deo|1974|p=206}}<ref name="DuKo2011">{{cite book|author1=Ding-Zhu Du|author2=Ker-I Ko|author3=Xiaodong Hu|title=Design and Analysis of Approximation Algorithms|year=2011|publisher=Springer Science & Business Media|isbn=978-1-4614-1701-9|page=108}}</ref> or out-tree{{sfn|Deo|1974|p=207}}<ref name="GrossYellen2013">{{cite book|author1=Jonathan L. Gross|author2=Jay Yellen|author3=Ping Zhang|author3-link=Ping Zhang (graph theorist)|title=Handbook of Graph Theory, Second Edition|year=2013|publisher=CRC Press|isbn=978-1-4398-8018-0|page=116}}</ref>—or making all its edges point towards the root—in which case it is called an anti-arborescence<ref name="KorteVygen2012b">{{cite book|author1=Bernhard Korte|authorlink1=Bernhard Korte|author2=Jens Vygen|title=Combinatorial Optimization: Theory and Algorithms|year=2012|publisher=Springer Science & Business Media|isbn=978-3-642-24488-9|page=28|edition=5th}}</ref> or in-tree.{{sfn|Deo|1974|p=207}}<ref name="MehlhornSanders2008">{{cite book|author1=Kurt Mehlhorn|author-link=Kurt Mehlhorn|author2=Peter Sanders|author2-link=Peter Sanders (computer scientist)|title=Algorithms and Data Structures: The Basic Toolbox|date=2008|publisher=Springer Science & Business Media|isbn=978-3-540-77978-0|pages=52 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Introduction.pdf |archive-url=https://web.archive.org/web/20150908084811/http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Introduction.pdf |archive-date=2015-09-08 |url-status=live}}</ref> A rooted tree itself has been defined by some authors as a directed graph.<ref name="Makinson2012">{{cite book|author=David Makinson|author-link=David Makinson|title=Sets, Logic and Maths for Computing|year=2012|publisher=Springer Science & Business Media|isbn=978-1-4471-2499-3|pages=167–168}}</ref><ref>{{cite book|author=Kenneth Rosen|title=Discrete Mathematics and Its Applications, 7th edition|year=2011|publisher=McGraw-Hill Science|page=747|isbn=978-0-07-338309-5}}</ref><ref name="Schrijver2003">{{cite book|author=Alexander Schrijver|title=Combinatorial Optimization: Polyhedra and Efficiency|year=2003|publisher=Springer|isbn=3-540-44389-4|page=34}}</ref> A rooted forest is a disjoint union of rooted trees. A rooted forest may be directed, called a directed rooted forest, either making all its edges point away from the root in each rooted tree—in which case it is called a [[Arborescence (graph theory)|branching]] or out-forest—or making all its edges point towards the root in each rooted tree—in which case it is called an anti-branching or in-forest.

The term {{em|tree}} was coined in 1857 by the British mathematician [[Arthur Cayley]].<ref>Cayley (1857) [https://books.google.com/books?id=MlEEAAAAYAAJ&pg=PA172 "On the theory of the analytical forms called trees,"] ''Philosophical Magazine'', 4th series, '''13''' : 172–176.<br>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&pg=PA20 pages 20–21]. Also in 1847, the German physicist [[Gustav Kirchhoff]] 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&q=Kirchoff&pg=PA497 "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird"] {{Webarchive|url=https://web.archive.org/web/20230720150251/https://books.google.com/books?id=gx4AAAAAMAAJ&q=Kirchoff&pg=PA497 |date=2023-07-20 }} (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.</ref>