HOME

TheInfoList



OR:

In the mathematical field of
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). If all of the edges of ''G'' are also edges of a spanning tree ''T'' of ''G'', then ''G'' is a tree and is identical to ''T'' (that is, a tree has a unique spanning tree and it is itself).


Applications

Several
pathfinding Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the s ...
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 A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...
. The Internet and many other telecommunications networks have transmission links that connect nodes together in a
mesh topology A mesh network is a local area network topology in which the infrastructure nodes (i.e. bridges, switches, and other infrastructure devices) connect directly, dynamically and non-hierarchically to as many other nodes as possible and cooperate wit ...
that includes some loops. In order to avoid
bridge loop A switching loop or bridge loop occurs in computer networks when there is more than one layer 2 path between two endpoints (e.g. multiple connections between two network switches or two ports on the same switch connected to each other). The loo ...
s and
routing loop A routing loop is a common problem with various types of networks, particularly computer networks. They are formed when an error occurs in the operation of the routing algorithm, and as a result, in a group of nodes, the path to a particular des ...
s, many routing protocols designed for such networks—including the Spanning Tree Protocol, Open Shortest Path First,
Link-state routing protocol Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols includ ...
, Augmented tree-based routing, etc.—require each router to remember a spanning tree. A special kind of spanning tree, the
Xuong tree In graph theory, a Xuong tree is a spanning tree T of a given graph G with the property that, in the remaining graph G-T, the number of connected components with an odd number of edges is as small as possible. They are named after Nguyen Huy Xuong ...
, is used in topological graph theory to find graph embeddings with maximum
genus Genus ( plural genera ) is a taxonomic rank used in the biological classification of living and fossil organisms as well as viruses. In the hierarchy of biological classification, genus comes above species and below family. In binomial nom ...
. A Xuong tree is a spanning tree such that, in the remaining graph, the number of connected components with an odd number of edges is as small as possible. A Xuong tree and an associated maximum-genus embedding can be found in polynomial time.


Definitions

A tree is a connected undirected graph with no cycles. It is a spanning tree of a graph ''G'' if it spans ''G'' (that is, it includes every vertex of ''G'') and is a subgraph of ''G'' (every edge in the tree belongs to ''G''). A spanning tree of a connected graph ''G'' can also be defined as a maximal set of edges of ''G'' that contains no cycle, or as a minimal set of edges that connect all vertices.


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.


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. 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.


Spanning forests

A spanning forest in a graph is a subgraph that is a forest with an additional requirement. There are two incompatible requirements in use, of which one is relatively rare. * 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.. * 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. To avoid confusion between these two definitions, 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 instead call this kind of forest a "maximal spanning forest" (which is redundant, as a maximal forest necessarily contains every vertex).


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 . * When ''G'' is the cycle graph ''Cn'' with ''n'' vertices, then . * For a complete graph with ''n'' vertices,
Cayley's formula In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^. The formula equivalently counts the number of spanning tre ...
gives the number of spanning trees as . * If ''G'' is the complete bipartite graph K_,then t(G)=p^q^. * For the ''n''-dimensional hypercube graph Q_n, the number of spanning trees is t(G)=2^\prod_^n k^.


In arbitrary graphs

More generally, for any graph ''G'', the number ''t''(''G'') can be calculated in polynomial time as the
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
of a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
derived from the graph, using Kirchhoff's matrix-tree theorem. Specifically, to compute ''t''(''G''), one constructs the
Laplacian matrix In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph La ...
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
singular Singular may refer to: * Singular, the grammatical number that denotes a unit quantity, as opposed to the plural and other forms * Singular homology * SINGULAR, an open source Computer Algebra System (CAS) * Singular or sounder, a group of boar ...
, so its determinant is zero. However, deleting the row and column for an arbitrarily chosen vertex leads to a smaller matrix whose determinant is exactly ''t''(''G'').


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 Contraction may refer to: Linguistics * Contraction (grammar), a shortened word * Poetic contraction, omission of letters for poetic reasons * Elision, omission of sounds ** Syncope (phonology), omission of sounds in a word * Synalepha, merged ...
of ''G'' by ''e''. 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. The Tutte polynomial can also be computed using a deletion-contraction recurrence, but its computational complexity is high: for many values of its arguments, computing it exactly is #P-complete, and it is also hard to approximate with a guaranteed approximation ratio. The point (1,1), at which it can be evaluated using Kirchhoff's theorem, is one of the few exceptions.


Algorithms


Construction

A single spanning tree of a graph can be found in linear time by either
depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible a ...
or breadth-first search. Both of these algorithms explore the given graph, starting from an arbitrary vertex ''v'', by looping through the neighbors of the vertices they discover and adding each unexplored neighbor to a data structure to be explored later. They differ in whether this data structure is a
stack Stack may refer to: Places * Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group * Blue Stack Mountains, in Co. Donegal, Ireland People * Stack (surname) (including a list of people ...
(in the case of depth-first search) or a queue (in the case of breadth-first search). In either case, one can form a spanning tree by connecting each vertex, other than the root vertex ''v'', to the vertex from which it was discovered. This tree is known as a depth-first search tree or a breadth-first search tree according to the graph exploration algorithm used to construct it. Depth-first search trees are a special case of a class of spanning trees called Trémaux trees, named after the 19th-century discoverer of depth-first search. 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. Instead, researchers have devised several more specialized algorithms for finding spanning trees in these models of computation.


Optimization

In certain fields of graph theory it is often useful to find a
minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...
of a weighted graph. Other optimization problems on spanning trees have also been studied, including the maximum spanning tree, the minimum tree that spans at least k vertices, the spanning tree with the fewest edges per vertex, the spanning tree with the largest number of leaves, the spanning tree with the fewest leaves (closely related to the Hamiltonian path problem), the minimum diameter spanning tree, and the minimum dilation spanning tree.. Optimal spanning tree problems have also been studied for finite sets of points in a geometric space such as the
Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...
. 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.


Randomization

A spanning tree chosen
random In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual ran ...
ly from among all the spanning trees with equal probability is called a uniform spanning tree. Wilson's algorithm can be used to generate uniform spanning trees in polynomial time by a process of taking a random walk on the given graph and erasing the cycles created by this walk. An alternative model for generating spanning trees randomly but not uniformly is the
random minimal spanning tree In mathematics, a random minimum spanning tree may be formed by assigning random weights from some distribution to the edges of an undirected graph, and then constructing the minimum spanning tree of the graph. When the given graph is a complete ...
. In this model, the edges of the graph are assigned random weights and then the
minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...
of the weighted graph is constructed.


Enumeration

Because a graph may have exponentially many spanning trees, it is not possible to list them all in polynomial time. However, algorithms are known for listing all spanning trees in polynomial time per tree.


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 In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
. 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. 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.. 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 A choice function (selector, selection) is a mathematical function ''f'' that is defined on some collection ''X'' of nonempty sets and assigns some element of each set ''S'' in that collection to ''S'' by ''f''(''S''); ''f''(''S'') maps ''S'' to ...
of the family of sets. Therefore, if every infinite connected graph has a spanning tree, then the axiom of choice is true.. See in particular Theorem 2.1
pp. 192–193


In directed multigraphs

The idea of a spanning tree can be generalized to directed multigraphs. 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 In the mathematical field of graph theory, a good spanning tree T of an embedded planar graph G is a rooted spanning tree of ''G'' whose non-tree edges satisfy the following conditions. *there is no non-tree edge (u,v) where u and v lie on a pat ...
– Spanning tree for embedded planar graph


References

{{Authority control Axiom of choice Computational problems in graph theory