Spanning tree
In the
Applications
Several pathfinding algorithms, including Dijkstra's algorithm and the A* search algorithm, internally build a spanning tree as an intermediate step in solving the problem.
In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the minimum spanning tree.[2]
The Internet and many other
A special kind of spanning tree, the
Definitions
A tree is a
Fundamental cycles
Adding just one edge to a spanning tree will create a cycle; such a cycle is called a fundamental cycle with respect to that tree. There is a distinct fundamental cycle for each edge not in the spanning tree; thus, there is a one-to-one correspondence between fundamental cycles and edges not in the spanning tree. For a connected graph with V vertices, any spanning tree will have V − 1 edges, and thus, a graph of E edges and one of its spanning trees will have E − V + 1 fundamental cycles (The number of edges subtracted by number of edges included in a spanning tree; giving the number of edges not included in the spanning tree). For any given spanning tree the set of all E − V + 1 fundamental cycles forms a cycle basis, i.e., a basis for the cycle space.[5]
Fundamental cutsets
Dual to the notion of a fundamental cycle is the notion of a fundamental cutset with respect to a given spanning tree. By deleting just one edge of the spanning tree, the vertices are partitioned into two disjoint sets. The fundamental cutset is defined as the set of edges that must be removed from the graph G to accomplish the same partition. Thus, each spanning tree defines a set of V − 1 fundamental cutsets, one for each edge of the spanning tree.[6]
The duality between fundamental cutsets and fundamental cycles is established by noting that cycle edges not in the spanning tree can only appear in the cutsets of the other edges in the cycle; and vice versa: edges in a cutset can only appear in those cycles containing the edge corresponding to the cutset. This duality can also be expressed using the theory of matroids, according to which a spanning tree is a base of the graphic matroid, a fundamental cycle is the unique circuit within the set formed by adding one element to the base, and fundamental cutsets are defined in the same way from the dual matroid.[7]
Spanning forests
A collection of disjoint (unconnected) trees is described as a
- Almost all graph theory books and articles define a spanning forest as a forest that spans all of the vertices, meaning only that each vertex of the graph is a vertex in the forest. A connected graph may have a disconnected spanning forest, such as the forest with no edges, in which each vertex forms a single-vertex tree.[8][9]
- A few graph theory authors define a spanning forest to be a maximal acyclic subgraph of the given graph, or equivalently a subgraph consisting of a spanning tree in each connected component of the graph.[10]
To avoid confusion between these two definitions, Gross & Yellen (2005) suggest the term "full spanning forest" for a spanning forest with the same number of components as the given graph (i.e., a maximal forest), while Bondy & Murty (2008) instead call this kind of forest a "maximal spanning forest" (which is redundant, as a maximal forest necessarily contains every vertex).[11]
Counting spanning trees
The number t(G) of spanning trees of a connected graph is a well-studied invariant.
In specific graphs
In some cases, it is easy to calculate t(G) directly:
- If G is itself a tree, then t(G) = 1.
- When G is the cycle graph Cn with n vertices, then t(G) = n.
- For a complete graph with n vertices, Cayley's formula[12] gives the number of spanning trees as nn − 2.
- If G is the complete bipartite graph ,then .[8]
- For the n-dimensional hypercube graph ,[13] the number of spanning trees is .
In arbitrary graphs
More generally, for any graph G, the number t(G) can be calculated in
Specifically, to compute t(G), one constructs the Laplacian matrix of the graph, a square matrix in which the rows and columns are both indexed by the vertices of G. The entry in row i and column j is one of three values:
- The degree of vertex i, if i = j,
- −1, if vertices i and j are adjacent, or
- 0, if vertices i and j are different from each other but not adjacent.
The resulting matrix is
Deletion-contraction
If G is a graph or multigraph and e is an arbitrary edge of G, then the number t(G) of spanning trees of G satisfies the deletion-contraction recurrence t(G) = t(G − e) + t(G/e), where G − e is the multigraph obtained by deleting e and G/e is the contraction of G by e.[15] The term t(G − e) in this formula counts the spanning trees of G that do not use edge e, and the term t(G/e) counts the spanning trees of G that use e.
In this formula, if the given graph G is a multigraph, or if a contraction causes two vertices to be connected to each other by multiple edges, then the redundant edges should not be removed, as that would lead to the wrong total. For instance a bond graph connecting two vertices by k edges has k different spanning trees, each consisting of a single one of these edges.
Tutte polynomial
The Tutte polynomial of a graph can be defined as a sum, over the spanning trees of the graph, of terms computed from the "internal activity" and "external activity" of the tree. Its value at the arguments (1,1) is the number of spanning trees or, in a disconnected graph, the number of maximal spanning forests.[16]
The Tutte polynomial can also be computed using a deletion-contraction recurrence, but its
Algorithms
Construction
A single spanning tree of a graph can be found in
Spanning trees are important in parallel and distributed computing, as a way of maintaining communications between a set of processors; see for instance the Spanning Tree Protocol used by OSI link layer devices or the Shout (protocol) for distributed computing. However, the depth-first and breadth-first methods for constructing spanning trees on sequential computers are not well suited for parallel and distributed computers.[20] Instead, researchers have devised several more specialized algorithms for finding spanning trees in these models of computation.[21]
Optimization
In certain fields of graph theory it is often useful to find a
Optimal spanning tree problems have also been studied for finite sets of points in a geometric space such as the Euclidean plane. For such an input, a spanning tree is again a tree that has as its vertices the given points. The quality of the tree is measured in the same way as in a graph, using the Euclidean distance between pairs of points as the weight for each edge. Thus, for instance, a Euclidean minimum spanning tree is the same as a graph minimum spanning tree in a complete graph with Euclidean edge weights. However, it is not necessary to construct this graph in order to solve the optimization problem; the Euclidean minimum spanning tree problem, for instance, can be solved more efficiently in O(n log n) time by constructing the Delaunay triangulation and then applying a linear time planar graph minimum spanning tree algorithm to the resulting triangulation.[22]
Randomization
A spanning tree chosen
An alternative model for generating spanning trees randomly but not uniformly is the
Enumeration
Because a graph may have exponentially many spanning trees, it is not possible to list them all in
In infinite graphs
Every finite connected graph has a spanning tree. However, for infinite connected graphs, the existence of spanning trees is equivalent to the axiom of choice. An infinite graph is connected if each pair of its vertices forms the pair of endpoints of a finite path. As with finite graphs, a tree is a connected graph with no finite cycles, and a spanning tree can be defined either as a maximal acyclic set of edges or as a tree that contains every vertex.[27]
The trees within a graph may be partially ordered by their subgraph relation, and any infinite chain in this partial order has an upper bound (the union of the trees in the chain). Zorn's lemma, one of many equivalent statements to the axiom of choice, requires that a partial order in which all chains are upper bounded have a maximal element; in the partial order on the trees of the graph, this maximal element must be a spanning tree. Therefore, if Zorn's lemma is assumed, every infinite connected graph has a spanning tree.[27]
In the other direction, given a family of sets, it is possible to construct an infinite graph such that every spanning tree of the graph corresponds to a choice function of the family of sets. Therefore, if every infinite connected graph has a spanning tree, then the axiom of choice is true.[28]
In directed multigraphs
The idea of a spanning tree can be generalized to directed multigraphs.[29] Given a vertex v on a directed multigraph G, an oriented spanning tree T rooted at v is an acyclic subgraph of G in which every vertex other than v has outdegree 1. This definition is only satisfied when the "branches" of T point towards v.
See also
- Flooding algorithm
- Good spanning tree – Spanning tree for embedded planar graph
References
- ^ "Tree". NetworkX 2.6.2 documentation. Retrieved 2021-12-10.
For trees and arborescence, the adjective "spanning" may be added to designate that the graph, when considered as a forest/branching, consists of a single tree/arborescence that includes all nodes in the graph.
- ^ Graham, R. L.; Hell, Pavol (1985). "On the History of the Minimum Spanning Tree Problem" (PDF).
- ^ Borg, Anita. "Folklore of Network Protocol Design". YouTube. Microsoft Research. Retrieved 13 May 2022.
- MR 2581536
- ^ Kocay & Kreher (2004), pp. 65–67.
- ^ Kocay & Kreher (2004), pp. 67–69.
- ISBN 978-0-19-920250-8.
- ^ ISBN 978-0-486-43232-8.
- ISBN 978-0-521-45761-3.
- ISBN 978-0-521-56329-1.
- ISBN 978-1-84628-970-5.
- Springer-Verlag, pp. 141–146.
- MR 0949280.
- ISBN 978-0-203-48905-5.
- ^ Kocay & Kreher (2004), p. 109.
- ^ Bollobás (1998), p. 351.
- .
- ISBN 978-0-387-97687-7.
- MR 0671906.
- MR 0801987.
- doi:10.1016/j.jpdc.2005.03.011, archived from the original(PDF) on Sep 23, 2015.
- ^ a b Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461, archived (PDF) from the original on Aug 2, 2023.
- ISBN 1-58488-436-3.
- MR 1427525.
- MR 1611522.
- MR 0495152
- ^ a b Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23.
- MR 2432534. See in particular Theorem 2.1, pp. 192–193.
- ISSN 0097-3165.