In graph theory, a Trémaux tree of an undirected graph G {\displaystyle G} is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of G {\displaystyle G} connects an ancestor–descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs. All depth-first search trees and all Hamiltonian paths are Trémaux trees. In finite graphs, every Trémaux tree is a depth-first search tree, but although depth-first search itself is inherently sequential, Trémaux trees can be constructed by a randomized parallel algorithm in the complexity class RNC. They can be used to define the tree-depth of a graph, and as part of the left-right planarity test for testing whether a graph is a planar graph. A characterization of Trémaux trees in the monadic second-order logic of graphs allows graph properties involving orientations to be recognized efficiently for graphs of bounded treewidth using Courcelle's theorem. Not every infinite connected graph has a Trémaux tree, and not every infinite Trémaux tree is a depth-first search tree. The graphs that have Trémaux trees can be characterized by forbidden minors. An infinite Trémaux tree must have exactly one infinite path for each end of the graph, and the existence of a Trémaux tree characterizes the graphs whose topological completions, formed by adding a point at infinity for each end, are metric spaces.
Definition and examples A Trémaux tree, for an undirected graph G {\displaystyle G} , is a spanning tree T {\displaystyle T} with the property that, for every edge u v {\displaystyle uv} in G {\displaystyle G} , one of the two endpoints u {\displaystyle u} and v {\displaystyle v} is an ancestor of the other. To be a spanning tree, it must only use edges of G {\displaystyle G} , and include every vertex, with a unique finite path between every pair of vertices. Additionally, to define the ancestor–descendant relation in this tree, one of its vertices must be designated as its root. If a finite graph has a Hamiltonian path, then rooting that path at one of its two endpoints produces a Trémaux tree. For such a path, every pair of vertices is an ancestor–descendant pair. In the graph shown below, the tree with edges 1–3, 2–3, and 3–4 is a Trémaux tree when it is rooted at vertex 1 or vertex 2: every edge of the graph belongs to the tree except for the edge 1–2, which (for these choices of root) connects an ancestor-descendant pair.
However, rooting the same tree at vertex 3 or vertex 4 produces a rooted tree that is not a Trémaux tree, because with this root 1 and 2 are no longer an ancestor and descendant of each other.
In finite graphs
Existence Every finite connected undirected graph has at least one Trémaux tree. One can construct such a tree by performing a depth-first search and connecting each vertex (other than the starting vertex of the search) to the earlier vertex from which it was discovered. The tree constructed in this way is known as a depth-first search tree. If u v {\displaystyle uv} is an arbitrary edge in the graph, and u {\displaystyle u} is the earlier of the two vertices to be reached by the search, then v {\displaystyle v} must belong to the subtree descending from u {\displaystyle u} in the depth-first search tree, because the search will necessarily discover v {\displaystyle v} while it is exploring this subtree, either from one of the other vertices in the subtree or, failing that, from u {\displaystyle u} directly. Every finite Trémaux tree can be generated as a depth-first search tree: If T {\displaystyle T} is a Trémaux tree of a finite graph, and a depth-first search explores the children in T {\displaystyle T} of each vertex prior to exploring any other vertices, it will necessarily generate T {\displaystyle T} as its depth-first search tree.
Parallel construction
It is P-complete to find the Trémaux tree that would be found by a sequential depth-first search algorithm, in which the neighbors of each vertex are searched in order by their identities. Nevertheless, it is possible to find a different Trémaux tree by a randomized parallel algorithm, showing that the construction of Trémaux trees belongs to the complexity class RNC. The algorithm is based on another randomized parallel algorithm, for finding minimum-weight perfect matchings in 0-1-weighted graphs. As of 1997, it remained unknown whether Trémaux tree construction could be performed by a deterministic parallel algorithm, in the complexity class NC. If matchings can be found in NC, then so can Trémaux trees.
Logical expression It is possible to express the property that a set T {\displaystyle T} of edges with a choice of root vertex r {\displaystyle r} forms a Trémaux tree, in the monadic second-order logic of graphs, and more specifically in the form of this logic called MSO2, which allows quantification over both vertex and edge sets. This property can be expressed as the conjunction of the following properties:
The graph is connected by the edges in T {\displaystyle T} . This can be expressed logically as the statement that, for every non-empty proper subset of the graph's vertices, there exists an edge in T {\displaystyle T} with exactly one endpoint in the given subset.
… excerpt ends here. Continue reading the full article.
