- Spanning tree (mathematics)
In the mathematical field of
graph theory, a spanning tree "T" of a connected, undirected graph"G" is a tree composed of all the vertices and some (or perhaps all) of the edges of "G". Informally, a spanning tree of "G" is a selection of edges of "G" that form a tree "spanning" every vertex. That is, every vertex lies in the tree, but no cycles (or loops) are formed.On the otherhand, every bridge of "G" must belong to "T".
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.
In certain fields of graph theory it is often useful to find a
minimum spanning treeof 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 minimum spanning tree with at most k edges per vertex (MDST), the spanning tree with the largest number of leaves (closely related to the smallest connected dominating set), 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.
Adding just one edge to a spanning tree will create a cycle; such a cycle is called a fundamental cycle. There is a distinct fundamental cycle for each edge; thus, there is a one-to-one correspondence between fundamental cycles and edges not in the spanning tree. For a connected graph with "V" verticies, any spanning tree will have "V"-1 edges, and thus, a graph of "E" edges will have "E"-"V"+1 fundamental cycles. For any given spanning tree these cycles form a basis for the
Dual to the notion of a fundamental cycle is the notion of a fundamental cutset. By deleting just one edge of the spanning tree, the verticies 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, there are precisely "V"-1 fundamental cutsets for the graph, 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 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 not containing the edge corresponding to the cutset.
A spanning forest is a type of subgraph that generalises the concept of a spanning tree. However there are two definitions in common use. One is that a spanning forest is a subgraph that consists of a spanning tree in each connected component of a graph. (Equivalently, it is a maximal cycle-free subgraph.) This definition is common in computer science and optimisation. It is also the definition used when discussing minimum spanning forests, the generalization to disconnected graphs of minimum spanning trees. Another definition, common in
graph theory, is that a spanning forest is any subgraph that is both a forest (contains no cycles) and spanning (includes every vertex).
Counting spanning trees
The number "t(G)" of spanning trees of a connected graph is an important
invariant. In some cases, it is easy to calculate "t(G)" directly. It is also widely used in data structures in different computer languages.For example, if "G" is itself a tree, then "t(G)=1", while if "G" is the
cycle graphwith "n" vertices, then "t(G)=n".For any graph "G", the number "t(G)" can be calculated using Kirchhoff's matrix-tree theorem (follow the link for an explicit example using the theorem). Cayley's formulais a formula for the number of spanning trees in the complete graphwith "n" vertices. The formula states that . Another way of stating Cayley's formula is that there are exactly labelled trees with "n" vertices. Cayley's formula can be proved using Kirchhoff's matrix-tree theorem or via the Prüfer code.
If "G" is the
complete bipartite graph, then , while if "G" is the "n"-dimensional hypercube graph, then .These formulae are also consequences of the matrix-tree theorem.
If "G" is a multigraph and "e" is an 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", where multiple edges arising from this contraction are not deleted.
Uniform spanning trees
A spanning tree chosen
randomly from among all the spanning trees with equal probability is called a uniform spanning tree(UST). This model has been extensively researched in probabilityand mathematical physics.
The classic spanning tree algorithm,
depth-first search(DFS), is due to Robert Tarjan. Another important algorithm is based on breadth-first search(BFS).
Parallel algorithms typically take different approaches than BFS or DFS. Halperin and Zwick designed an optimal randomized parallel algorithm that runs in O(log n) time with high probability on EREW PRAM. [http://citeseer.ist.psu.edu/652374.html] The Shiloach-Vishkin algorithm is the basis for many parallel implementations. [http://citeseer.ist.psu.edu/context/74288/0] Bader and Cong's algorithm is shown to run fast in practice on a variety of graphs. [http://portal.acm.org/citation.cfm?id=1196220]
*cite conference | author = Eppstein, David | authorlink = David Eppstein | title = Spanning trees and spanners | booktitle = Handbook of Computational Geometry | publisher = Elsevier | year = 1999 | pages = 425–461 | url = http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf
*cite book|author = Garey, Michael R.; Johnson, David S. | year = 1979 | title = | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5 A2.1: ND2, pg.206.
*cite book | author = Wu, Bang Ye; Chao, Kun-Mao | title = Spanning Trees and Optimization Problems | year = 2004 | publisher = CRC Press | id = ISBN 1584884363
Wikimedia Foundation. 2010.
См. также в других словарях:
Spanning tree — can refer to:* Spanning tree (mathematics), a tree which contains every vertex of a more general graph * Spanning tree protocol, a protocol for finding spanning trees in bridged networks … Wikipedia
Spanning Tree — Ein Graph mit einem minimalen Spannbaum. Ein Spannbaum (auch aufspannender Baum oder manchmal spannender Baum genannt; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten… … Deutsch Wikipedia
Minimum spanning tree — The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all… … Wikipedia
Random minimal spanning tree — In mathematics, random minimal spanning tree, or random MST, is a model (actually two related models) for a random tree (see also minimal spanning tree). It might be compared against the uniform spanning tree, a different model for a random tree… … Wikipedia
K-minimum spanning tree — In mathematics, the K minimum spanning tree is a graph G that spans some K of N vertices in the input set S with the minimum total length. K is less than or equal to N. The K MST does not have to be a subgraph of the minimum spanning tree (MST).… … Wikipedia
Spanning — may refer to:* Spanning tree (mathematics) * Spanning tree protocol * Spanning set * Spanning forest * Span (architecture) … Wikipedia
Tree (graph theory) — Trees A labeled tree with 6 vertices and 5 edges Vertices v Edges v 1 Chromatic number … Wikipedia
List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… … Wikipedia
Steiner tree problem — Steiner tree for three points A, B, and C (note there are no direct connections between A, B, C). The Steiner point S is located at the Fermat point of the triangle ABC … Wikipedia
Steiner tree — The Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization.The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a… … Wikipedia