tree (graph theory)

tree (graph theory)
Unknown authorUnknown author · Public domain · source
Name	Tree (graph theory)
Properties	Acyclic, connected, minimally connected

tree (graph theory) is a connected acyclic undirected graph that appears throughout Leonhard Euler's work and in later developments by Arthur Cayley, Gustav Kirchhoff, James Joseph Sylvester, and George Pólya. Trees model hierarchical structures in applications linked to Alan Turing, Claude Shannon, John von Neumann, Donald Knuth, and Edsger W. Dijkstra and are foundational in results by Paul Erdős, Alfréd Rényi, László Lovász, Nikolai Lobachevsky, and Andrey Kolmogorov.

Definitions and basic properties

A tree is commonly defined as a finite undirected graph that is connected and contains no cycles; this definition is equivalent to several alternative formulations developed in the work of Arthur Cayley and formalized in texts by Richard M. Karp and Harold N. Gabow. Basic quantitative properties include |E| = |V| − 1 for a tree with vertex set V and edge set E, and every finite tree has at least two leaves, a fact used in proofs by Paul Erdős and Alfred Rényi. Trees admit unique simple paths between any two vertices, a property leveraged in algorithms by Donald Knuth and Edsger W. Dijkstra. The concept of rooted trees, introduced in computer science by Alan Perlis and institutionalized by John McCarthy, orients one vertex as a root and defines parent–child relations central to work by Tony Hoare and Niklaus Wirth.

Characterizations and equivalent conditions

Multiple equivalent characterizations trace to combinatorial and algebraic formulations by Arthur Cayley, Gustav Kirchhoff, Kirillov, and modern expositions by William Tutte. For a finite graph G with n vertices, the following are equivalent: G is connected and acyclic; G is acyclic with n − 1 edges; G is connected with n − 1 edges; any two vertices are joined by exactly one simple path; every edge is a bridge. The Matrix-Tree Theorem of Gustav Kirchhoff and extensions by William Tutte characterize the number of spanning trees in a graph via determinants of Laplacian minors, a result used by Kazimierz Kuratowski and Paul Erdős in counting arguments. Characterizations via forbidden minors relate to the work of Neil Robertson and P. D. Seymour in graph minor theory, while connections to matroid theory originate from studies by H. H. Crapo and Gian-Carlo Rota.

Types and special classes of trees

Numerous specialized trees arise in combinatorics and computer science. Rooted trees, binary trees, and ordered trees are central in algorithms by Donald Knuth and Robert Sedgewick; full binary trees and complete binary trees underpin designs by Edsger W. Dijkstra and Tony Hoare. Spanning trees and minimum spanning trees (MSTs) are core objects in work by Kruskal and Prim, with algorithmic refinements by Edmonds and Tarjan. Steiner trees relate to optimization problems studied by H. W. Lenstra and Jack Edmonds. Cayley trees and labeled trees were enumerated in classical results by Arthur Cayley; Prüfer sequences give bijections used by G. Pólya and R. C. Read. Phylogenetic trees appear in studies by Charles Darwin and later algorithmic treatments by Joseph Felsenstein, while suffix trees, suffix arrays, and tries are tools refined by Weiner, Udi Manber, and Gene Myers.

Algorithms and computational problems

Fundamental algorithms operate on trees or find trees within graphs. Depth-first search and breadth-first search, attributed to C. A. R. Hoare and popularized via texts by Donald Knuth and Robert Tarjan, compute spanning trees and components. Minimum spanning tree algorithms by Robert C. Prim, Joseph Kruskal, and Edmonds solve optimization problems; improvements by Tarjan and Fredman reduce complexity bounds. Dynamic tree data structures such as link/cut trees were introduced by Sleator and Tarjan to support online tree manipulation. Computational complexity results, including NP-completeness of variants like the Steiner tree problem, stem from proofs by Richard Karp and David Johnson. Random tree generation and enumeration leverage probabilistic methods from Paul Erdős and Alfréd Rényi and sampling techniques refined by Mark Jerrum.

Applications and examples

Trees model hierarchical and networked systems in domains associated with Alan Turing, Claude Shannon, John von Neumann, and Norbert Wiener. In phylogenetics, reconstruction algorithms by Joseph Felsenstein and David Sankoff infer evolutionary trees; in linguistics, parse trees follow frameworks by Noam Chomsky. Routing and broadcasting in communication networks draw on spanning tree protocols developed in standards bodies and industry players such as IEEE and Internet Engineering Task Force. Database indexing and file systems employ B-trees and variants studied by Rudolf Bayer and Edward M. McCreight, while compiler design uses abstract syntax trees influenced by work at Bell Labs. Electrical circuit analysis uses tree/cotree decompositions elaborated by Gustav Kirchhoff and applied in modern circuit simulation by groups at Bell Laboratories and IBM Research.

Algebraic and spectral properties

Algebraic graph theory connects trees to results by Gustav Kirchhoff, Issai Schur, Alfred Young, and William Tutte. The Laplacian spectrum of a tree has well-studied properties: zero is a simple eigenvalue for connected graphs, and eigenvalues reflect structural features analyzed by Miroslav Fiedler and László Lovász. The characteristic polynomial and matching polynomial of trees were investigated by Haruo Hosoya and Gutman, while results on spectral radius and eigenvector localization trace to studies by Fan Chung and Bollobás. Kirchhoff's Matrix-Tree Theorem relates cofactors of the Laplacian to spanning tree counts, a bridge between algebraic invariants and combinatorial enumeration explored by Gustav Kirchhoff and later authors at Princeton University and Cambridge University.

Category:Graph theory