A spanning tree (blue heavy edges) of a grid graph.

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 other hand, every bridge of G must belong to T. Image File history File links 4x4_grid_spanning_tree. ... Image File history File links 4x4_grid_spanning_tree. ... In graph theory, a grid graph is a graph corresponding to the square lattice, so that it is isomorphic to the graph having a vertex corresponding to every pair of integers (a, b), and an edge connecting (a, b) to (a+1, b) and (a, b+1). ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... A drawing of a graph. ... In mathematics and computer science, graph theory studies the properties of graphs. ... This article just presents the basic definitions. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... Cycle in graph theory and computer science has several meanings: A closed walk, with repeated vertices allowed. ... One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ...

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 tree 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 minimum spanning tree with at most k edges per vertex, 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. The minimum spanning tree of a planar graph. ... One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ... In graph theory, a dominating set for a graph G = (V, E) is a subset V′ of V such that every vertex not in V′ is joined to at least one member of V′ by some edge. ... In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). ...

Spanning forests

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). In an undirected graph, a connected component or component is a maximal connected subgraph. ... A drawing of a graph. ... A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

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 graph C_n with 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). In mathematics, an invariant is something that does not change under a set of transformations. ... This article is about connected, 2-regular graphs. ... In the mathematical field of graph theory Kirchhoffs theorem or Kirchhoffs matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph. ...

Cayley's formula is a formula for the number of spanning trees in the complete graph K_n with n vertices. The formula states that t(K_n) = n^{n − 2}. Another way of stating Cayley's formula is that there are exactly n^{n − 2} labelled trees with n vertices. Cayley's formula can be proved using Kirchhoff's matrix-tree theorem or via the Prüfer code. In mathematics, Cayleys formula is a result in graph theory. ... In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. ... In combinatorial mathematics, the Prüfer sequence (or Prüfer code) of a labeled tree is a unique sequence associated with the tree. ...

If G is the complete bipartite graph K_p,q, then t(G) = p^{q − 1}q^{p − 1}, while if G is the n-dimensional hypercube graph Q_n, then . These formulas are also consequences of the matrix-tree theorem. In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ... The hypercube graph Q4. ...

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. A multigraph is a graph with multiple edges, i. ... In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it used to connect. ...

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 probability and mathematical physics. Random redirects here. ... In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics and, in physics, quantum field theory. ... Probability is the likelihood that something is the case or will happen. ... Mathematical physics is the scientific discipline concerned with the application of mathematics to problems in physics and the development of mathematical methods suitable for such applications and for the formulation of physical theories. ...

References

• Eppstein, David (1999). "Spanning trees and spanners". Handbook of Computational Geometry: 425–461, Elsevier. 

• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A2.1: ND2, pg.206.

• Wu, Bang Ye; Chao, Kun-Mao (2004). Spanning Trees and Optimization Problems. CRC Press. ISBN 1584884363.