Difference between revisions of "Spanning tree"
(Start article: Spanning tree) |
(Cf Matrix tree theorem) |
||
| Line 4: | Line 4: | ||
A subgraph of the given graph $G$ which contains all its vertices and which is a [[tree]]: connected and without cycles. More generally, a ''spanning forest'' of a graph is a subgraph which is a spanning tree for each of the connected components. A spanning forest for a graph with $n$ vertices and $k$ components has $n-k$ edges. | A subgraph of the given graph $G$ which contains all its vertices and which is a [[tree]]: connected and without cycles. More generally, a ''spanning forest'' of a graph is a subgraph which is a spanning tree for each of the connected components. A spanning forest for a graph with $n$ vertices and $k$ components has $n-k$ edges. | ||
| − | The number of spanning trees of any given connected graph $G$ without loops and without multiple edges can be computed as follows. Let $L$ be the matrix obtained from the [[adjacency matrix]] of $G$ by replacing all the signs of the elements by the opposite signs and by replacing the $i$-th entry on the principal diagonal by the valency of the vertex $v_i$. The cofactors of all entries on the principal diagonal of $L$ will then all be equal, and their common value is the number of spanning trees of $G$. Spanning trees are employed, for example, to find independent cycles in an electric circuit. | + | The number of spanning trees of any given connected graph $G$ without loops and without multiple edges can be computed as follows. Let $L$ be the matrix obtained from the [[adjacency matrix]] of $G$ by replacing all the signs of the elements by the opposite signs and by replacing the $i$-th entry on the principal diagonal by the valency of the vertex $v_i$. The cofactors of all entries on the principal diagonal of $L$ will then all be equal, and their common value is the number of spanning trees of $G$. Spanning trees are employed, for example, to find independent cycles in an electric circuit. See [[Matrix tree theorem]]. |
The number of spanning trees is a special value of the [[Tutte polynomial]] of the graph, $T_G(1,1)$. | The number of spanning trees is a special value of the [[Tutte polynomial]] of the graph, $T_G(1,1)$. | ||
See [[Tree]] for references. | See [[Tree]] for references. | ||
Latest revision as of 12:59, 29 December 2014
of a graph $G$
A subgraph of the given graph $G$ which contains all its vertices and which is a tree: connected and without cycles. More generally, a spanning forest of a graph is a subgraph which is a spanning tree for each of the connected components. A spanning forest for a graph with $n$ vertices and $k$ components has $n-k$ edges.
The number of spanning trees of any given connected graph $G$ without loops and without multiple edges can be computed as follows. Let $L$ be the matrix obtained from the adjacency matrix of $G$ by replacing all the signs of the elements by the opposite signs and by replacing the $i$-th entry on the principal diagonal by the valency of the vertex $v_i$. The cofactors of all entries on the principal diagonal of $L$ will then all be equal, and their common value is the number of spanning trees of $G$. Spanning trees are employed, for example, to find independent cycles in an electric circuit. See Matrix tree theorem.
The number of spanning trees is a special value of the Tutte polynomial of the graph, $T_G(1,1)$.
See Tree for references.
Spanning tree. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Spanning_tree&oldid=35941