Graph Tree
A Graph Tree is an connected graph that is an acyclic graph (in which any two nodes are connected by exactly one graph path).
- AKA: Connected Acyclic Graph.
- Context:
- It can range from being a Rooted Tree to being an Unrooted Tree (with a tree root).
- It can range from being a Directed Tree Graph to being an Undirected Tree Graph.
- It can range from being an Ordered Tree to being an Unordered Tree (in which the child nodes of every node are ordered in according to some relation).
- It can range from being a Non-Empty Tree to being an Empty Tree.
- It can range from being an Unlabeled Tree to being a Labeled Tree (a tree where each node v contains a label label(v) in A).
- It can be represented by a Tree Dataset.
- …
- Example(s):
- a Taxonomy.
- a Sequence, a very unbalanced tree.
- a Decision Tree.
- an AVL Tree.
- …
- Counter-Example(s):
- a Partial Order Tree.
- a Lattice.
- See: Tree Operation, Hierarchical HMM, Path (Graph Theory), Graph Forest, Disjoint Union.
References
2016
- (Wikipedia, 2016) ⇒ http://en.wikipedia.org/wiki/Tree_(graph_theory) Retrieved:2016-1-21.
- In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree. A forest is a disjoint union of trees.
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, thus in fact being directed graphs, and may also have additional ordering of branches.
Rooted trees in their directed graph form may be called directed rooted trees. Other terms for this include[1] arborescence, out-arborescence, out-tree, and even branching.
The term "tree" was coined in 1857 by the British mathematician Arthur Cayley. [2]
- In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree. A forest is a disjoint union of trees.
- ↑ In particular, some authors consider that directed rooted trees are not descriptive enough as to the direction of the arcs, for instance
- ↑ 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" (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.
2009
- (Weisstein, 2009) ⇒ Eric W. Weisstein. (2009). “Tree.” In: MathWorld -- A Wolfram Web Resource. http://mathworld.wolfram.com/Tree.html
- QUOTE: A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.
Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.
A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with n nodes has n-1 graph edges. Conversely, a connected graph with n nodes and n-1 edges is a tree. All trees are bipartite graphs (Skiena 1990, p. 213). Trees with no particular node singled out are sometimes called free trees (or unrooted tree), by way of distinguishing them from rooted trees (Skiena 1990, Knuth 1997).
- QUOTE: A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.
1891
- (Cayley, 1891) ⇒ A. Cayley. (1891). “On the Theory of Analytic Forms Called Trees.” Philos. Mag. 13, 19-30, 1857. Reprinted in Mathematical Papers, Vol. 3.