Back شجرة (نظرية البيان) Arabic Дърво (математика) Bulgarian Arbre (teoria de grafs) Catalan Strom (graf) Czech Йывăç (графсен теорийĕ) CV Baum (Graphentheorie) German Δέντρο (θεωρία γράφων) Greek Arbo (grafeteorio) Esperanto Árbol (teoría de grafos) Spanish Puu (graafiteooria) Estonian

Tree (graph theory)

Trees
A labeled tree with 6 vertices and 5 edges.
Verticesv
Edgesv − 1
Chromatic number2 if v > 1
Table of graphs and parameters

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.[1] A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.[2]

A directed tree,[3] oriented tree,[4][5] polytree,[6] or singly connected network[7] 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 trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees. A rooted tree may be directed, called a directed rooted tree,[8][9] either making all its edges point away from the root—in which case it is called an arborescence[3][10] or out-tree[11][12]—or making all its edges point towards the root—in which case it is called an anti-arborescence[13] or in-tree.[11][14] A rooted tree itself has been defined by some authors as a directed graph.[15][16][17] 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 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 tree was coined in 1857 by the British mathematician Arthur Cayley.[18]

  1. ^ Bender & Williamson 2010, p. 171.
  2. ^ Bender & Williamson 2010, p. 172.
  3. ^ a b Deo 1974, p. 206.
  4. ^ See Harary & Sumner (1980).
  5. ^ See Simion (1991).
  6. ^ See Dasgupta (1999).
  7. ^ See Kim & Pearl (1983).
  8. ^ Stanley Gill Williamson (1985). Combinatorics for Computer Science. Courier Dover Publications. p. 288. ISBN 978-0-486-42076-9.
  9. ^ Mehran Mesbahi; Magnus Egerstedt (2010). Graph Theoretic Methods in Multiagent Networks. Princeton University Press. p. 38. ISBN 978-1-4008-3535-5.
  10. ^ Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). Design and Analysis of Approximation Algorithms. Springer Science & Business Media. p. 108. ISBN 978-1-4614-1701-9.
  11. ^ a b Deo 1974, p. 207.
  12. ^ Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 116. ISBN 978-1-4398-8018-0.
  13. ^ Bernhard Korte; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 28. ISBN 978-3-642-24488-9.
  14. ^ Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0. Archived (PDF) from the original on 2015-09-08.
  15. ^ David Makinson (2012). Sets, Logic and Maths for Computing. Springer Science & Business Media. pp. 167–168. ISBN 978-1-4471-2499-3.
  16. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5.
  17. ^ Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN 3-540-44389-4.
  18. ^ 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 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) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" Archived 2023-07-20 at the Wayback Machine (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.

Developed by StudentB