A Tremo tree of an undirected graph G is a spanning tree of the graph G with a distinguished root with the property that any two adjacent vertices in the graph G are related to each other by ancestor / descendant relation. All depth search trees and all Hamiltonian paths are Tremo trees. Tremo Trees are named after Charles Pierre Tremo, a 19th-century French author who used the depth-first search option as a [1] [2] . Tremo trees are also called normal spanning trees , especially in the context of infinite graphs [3] .
In finite graphs, although the depth-first search itself is initially sequential, Tremo trees can be constructed by a randomized parallel algorithm with complexity class . Tremo trees can be used to determine the depth of a graph tree and as part of a to check whether a graph is planar . The description of Tremo trees by the single-seater second-order makes it possible to recognize the orientation- dependent properties of a graph for graphs with a limited tree width when using the Kursell theorem .
Not every infinite graph has a Tremo tree and graphs that do not have such a tree can be described by forbidden minors . A Tremo tree exists in any graph with a countable number of vertices, even if the infinite depth search option cannot successfully check all the vertices of the graph. In an infinite graph, the Tremo tree must have exactly one infinite path for each graph and the existence of the Tremo tree is characterized by graphs whose topological completions, formed by adding an infinitely distant point for each ray, are metric spaces .
Content
Example
In the graph shown below, a tree with edges 1–3, 2–3 and 3–4 is a Tremo tree, if you assign vertex 1 or vertex 2 as its root - any edge of the graph belongs to the tree, except for edge 1–2, which (for selecting the specified root) connects a pair of ancestor-child.
However, if we select vertex 3 or vertex 4 as the root for the same tree, we obtain a root tree that is not a Tremo tree, since with these roots vertices 1 and 2 will no longer be ancestors / descendants.
In the final graphs
Existence
Any finite connected undirected graph has at least one Tremo tree. You can build such a tree with the help of a depth search and a junction of each vertex (different from the initial vertex of the search) with an earlier vertex from which access was made to the current vertex. A tree constructed in this way is known as a depth-first search tree. If uv is an arbitrary edge in the graph and u is the earlier of the two vertices reached as a result of the search, then v must belong to the subtree of descendants u in the depth tree, because the search will detect the vertex v , looking at this tree or from one of the vertices subtree, either directly from the vertex u . Any final Tremo tree can be formed as a depth-first search tree — if T is a Tremo tree of a finite graph and depth-by-depth examines the descendants T of each vertex before considering any other vertex, it necessarily generates T as a tree of depth-first search.
Parallel construction
The Tremo tree search task is if it is searched using a sequential depth search algorithm in which the neighbors of each vertex are viewed in the order of their numbers [4] . However, it is possible to find another Tremo tree using the randomized parallel algorithm , which shows that the Tremo tree building class belongs to the complexity class [5] . It remains unclear whether the Tremo tree can be constructed by a deterministic parallel algorithm belonging to the class [6] .
Boolean expression
It is possible to express the property that the set T of edges with the selected root vertex r forms a Tremo tree, in the single-seater second order, and this expression is called MSO 2 . This property can be expressed as a combination of the following properties:
- The graph is connected by the edges of T. This can be expressed logically as a statement that for any non-empty proper subset of the vertices of the graph there is an edge in T that has exactly one end point in this subset.
- T acyclic. This can be expressed logically as a statement that there is no non-empty subset C of the set T for which each vertex is incident either to zero or to two edges from C.
- Any edge e not belonging to T joins a pair of ancestors / descendants of vertices in T. This is true when both ends of the edge e belong to the path in T. This can be expressed logically as a statement that for all edges e there exists a subset P of T , such that exactly two vertices, one of which r , are incident to one edge in P , and both ends of the arc e are incident to at least one edge in P .
Once the Tremo tree is identified in this way, one can describe the orientation of this graph in second-order single-seater logic by specifying a set of edges that are oriented from ancestor to descendant. Not included in this set of edges must be oriented in the opposite direction. This technique allows one to describe properties of a graph using orientation in second-order single-seater logic, which allows one to verify these properties effectively on graphs with bounded tree width using the Kursell theorem [7] .
Related Properties
If the graph has a Hamiltonian path , then this path (with the root as one of its ends) is also a Tremo tree. The set of non-oriented graphs, for which any Tremo tree has this form, consists of cycles , complete graphs and balanced full bipartite graphs [8] .
Tremo trees are closely related to the concept of tree depth . The tree depth of a graph G can be defined as the smallest number d , such that G can be nested as a subgraph of graph H , which has a Tremo T tree of depth d . The limited depth of a tree in a family of graphs is equivalent to the existence of a path that cannot appear as a minor of a graph in a family. Many complex computational problems on graphs have algorithms, if parameterized by the depth of the tree [9] .
Tremo trees also play a key role in the to check whether the graph is planar . According to this criterion, the graph G is planar if for any Tremo T tree of the graph G the remaining edges can be placed to the left and right of the tree, which prevents the edges from intersecting (for this reason, the name “LP algorithm” is sometimes abbreviated as Left / Right) [10 ] [11] .
In endless graphs
Existence
Not every infinite graph has a normal spanning tree. For example, a complete graph on an uncountable set of vertices does not have a normal spanning tree — such a tree in a complete graph can only be a path, but only a countable number of vertices has a path. However, any graph on a countable set of vertices has a normal spanning tree [3] .
Even in countable graphs, a depth search may fail when viewing the entire graph [3] , and not any normal spanning tree can be formed by depth search — to be a depth search tree, a countable normal spanning tree must have only one infinite path or one a node with an infinite number of neighbors (but not both cases at the same time).
Minors
If the infinite graph G has a normal spanning tree, then any connected minor of the graph G has one as well . It follows that graphs with normal spanning trees can be described by forbidden minors . One of the two classes of forbidden minors consists of bipartite graphs , in which one fraction is countable, and the other is uncountable, and every vertex has infinite degree. Another class of forbidden minors consists of certain graphs obtained from [12] .
The details of this description depend on the choice of axiomatics of set theory used in the formalization of mathematics. In particular, in models of set theory, in which Martin's axiom is true, but the continuum hypothesis is not true, the class of bipartite graphs can be replaced by one forbidden minor. However, for models in which the continuum hypothesis is true, this class contains graphs that are incomparable in the ordering of the minors [13] .
Rays and Metrizability
Normal spanning trees are closely related to the infinite graph, the equivalence classes of infinite paths that go in the same direction. If the graph has a normal spanning tree, this tree must have exactly one infinite path for each ray of the graph [14] .
An infinite graph can be used to form a topological space if we consider the graph itself as a simplicial complex and add an infinitely distant point for each ray of the graph. With such a topology, a graph has a normal spanning tree if and only if its set of vertices can be divided into a countable union of closed sets . In addition, this topological space can be represented by a metric space if and only if the graph has a normal spanning tree [14] .
Notes
- ↑ Even, 2011 , p. 46–48.
- ↑ Sedgewick, 2002 , p. 149–157.
- ↑ 1 2 3 Soukup, 2008 , p. 193 Theorem 3.
- ↑ Reif, 1985 , p. 229–234.
- ↑ Aggarwal, Anderson, 1988 , p. 1–12.
- ↑ Karger, Motwani, 1997 , p. 255-272.
- ↑ Courcelle, 1996 , p. 33–62.
- ↑ Chartrand, Kronk, 1968 , p. 696–700.
- ↑ Nešetřil, Ossona de Mendez, 2012 , p. 115–144.
- ↑ de Fraysseix, Rosenstiehl, 1982 , p. 75–80.
- ↑ de Fraysseix, Ossona de Mendez, Rosenstiehl, 2006 , p. 1017-1029.
- ↑ Diestel, Leader, 2001 , p. 16–32.
- ↑ Bowler, Geschke, Pitz, 2016 .
- ↑ 1 2 Diestel, 2006 , p. 846–854.
Literature
- Shimon Even. Graph Algorithms . - 2nd. - Cambridge University Press, 2011. - p. 46–48. - ISBN 978-0-521-73653-4 .
- Robert Sedgewick. Algorithms in C ++: Graph Algorithms . - 3rd. - Pearson Education, 2002. - p. 149–157. - ISBN 978-0-201-36118-6 .
- Robert Sedgwick. Part 5. Algorithms on graphs // Fundamental algorithms in C. - Moscow, St. Petersburg, Kiev: DiaSoft, 2003. - ISBN 5-93772-083-0 .
- John H.Reif. Depth-first search is inherently sequential. - Information Processing Letters . - 1985. - T. 20. - p. 229–234. - DOI : 10.1016 / 0020-0190 (85) 90024-9 .
- Aggarwal A., Anderson RJ A random NC algorithm for depth first search // Combinatorica . - 1988. - Vol. 8 , no. 1 . - P. 1–12 . - DOI : 10.1007 / BF02122548 .
- David R. Karger, Rajeev Motwani. An NC algorithm for minimum cuts. - SIAM Journal on Computing . - 1997. - V. 26. - P. 255-272. - DOI : 10.1137 / S0097539794273083 .
- Bruno Courcelle. Fragments of the monadic second-order logic // Proc. Descr. Complex. Finite Models / Neil Immerman, Phokion G. Kolaitis. - Amer. Math Soc., 1996. - T. 31. - p. 33–62. - (DIMACS).
- Gary Chartrand, Hudson V. Kronk. Randomly traceable graphs // SIAM Journal on Applied Mathematics . - 1968. - V. 16 . - p . 696–700 .
- Jaroslav Nešetřil, Patrice Ossona de Mendez. Chapter 6. Bounded height trees and tree-depth // Sparsity: Graphs, Structures, and Algorithms. - Heidelberg: Springer, 2012. - T. 28. - p. 115–144. - (Algorithms and Combinatorics). - ISBN 978-3-642-27874-7 . - DOI : 10.1007 / 978-3-642-27875-4 .
- Hubert de Fraysseix, Pierre Rosenstiehl. A depth-first-search characterization of planarity // Graph theory (Cambridge, 1981). - Amsterdam: North-Holland, 1982. - Vol. 13. - p. 75–80. - (Ann. Discrete Math.).
- Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Trémaux trees and planarity // International Journal of Foundations of Computer Science. - 2006. - V. 17 , no. 5 - pp . 1017-1029 . - DOI : 10.1142 / S0129054106004248 .
- Lajos Soukup. Infinite combinatorics: from finite to infinite // Horizons of combinatorics . - Berlin: Springer, 2008. - V. 17. - P. 189–213. - (Bolyai Soc. Math. Stud.). - ISBN 978-3-540-77199-9 . - DOI : 10.1007 / 978-3-540-77200-2_10 .
- Reinhard Diestel, Imre Leader. Normal spanning trees, Aronszajn trees and excluded minors // Journal of the London Mathematical Society. - 2001. - V. 63 , no. 1 . - p . 16–32 . - DOI : 10.1112 / S0024610700001708 .
- Nathan Bowler, Stefan Geschke, Max Pitz. Minimal obstructions for normal spanning trees. - 2016. - arXiv : 1609.01042 .
- Reinhard Diestel. End spaces and spanning trees // Journal of Combinatorial Theory . - 2006. - Vol. 96 , no. 6 - p . 846–854 . - DOI : 10.1016 / j.jctb.2006.02.010 .