Trémaux tree
Encyclopedia
In graph theory
a Trémaux tree of a graph G is a spanning tree
of G, rooted at one of its vertices, with the property that every edge in G connects a pair of vertices that are related as ancestor and descendant in the tree. In a depth-first search
of a graph, the tree of edges by which each vertex was first reached (also called a depth-first search tree) is necessarily a Trémaux tree.
Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French mathematician who used a form of depth-first search as a strategy for solving mazes
.
If a graph has a Hamiltonian path
, then that path (rooted at one of its endpoints) is a Trémaux tree. For an example of a spanning tree that is not a Tremaux tree, let G be the triangle graph with root u. The tree consisting of the edges uv and uw is not a Tremaux tree, because the edge vw is not in the tree, but v and w are equally far from the root.
Trémaux trees play a key role in Fraysseix–Rosenstiehl's planarity criterion for testing whether a given graph is planar
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
a Trémaux tree of a graph G is a spanning tree
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
of G, rooted at one of its vertices, with the property that every edge in G connects a pair of vertices that are related as ancestor and descendant in the tree. In a depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
of a graph, the tree of edges by which each vertex was first reached (also called a depth-first search tree) is necessarily a Trémaux tree.
Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French mathematician who used a form of depth-first search as a strategy for solving mazes
Maze solving algorithm
There are a number of different maze solving algorithms, that is, automated methods for the solving of mazes. A few important maze solving algorithms are explained below...
.
If a graph has a Hamiltonian path
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
, then that path (rooted at one of its endpoints) is a Trémaux tree. For an example of a spanning tree that is not a Tremaux tree, let G be the triangle graph with root u. The tree consisting of the edges uv and uw is not a Tremaux tree, because the edge vw is not in the tree, but v and w are equally far from the root.
Trémaux trees play a key role in Fraysseix–Rosenstiehl's planarity criterion for testing whether a given graph is planar
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
.