|
|
|
|
spanning tree
|
(Definition)
|
|
|
A spanning tree of a (connected) graph $G$ is a connected, acyclic subgraph of $G$ that contains all of the vertices of $G$ Below is an example of a spanning tree $T$ where the edges in
$T$ are drawn as solid lines and the edges in $G$ but not in $T$ are drawn as dotted lines.
$$ \xymatrix{ \bullet \ar@{.}[dddd] \ar@{-}[ddr] \ar@{.}[rrr] &&& \bullet \ar@{.}[ddll] \ar@{-}[dd] \ar@{.}[drr] \\ &&&&&\bullet \ar@{-}[dll] \ar@{.}[d] \\ &\bullet\ar@{-}[ddl]\ar@{-}[dr]\ar@{.}[rr] && \bullet\ar@{-}[dl]\ar@{.}[dr]\ar@{-}[rr] &&\bullet\ar@{-}[dl] \\ &&\bullet\ar@{.}[dll]\ar@{-}[dr]\ar@{.}[rr]&&\bullet\ar@{.}[dl] \\ \bullet\ar@{.}[rrr]&&&\bullet } $$
For any tree there is exactly one spanning tree: the tree itself.
|
"spanning tree" is owned by mathcam. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
Cross-references: tree, lines, solid, edges, vertices, contains, subgraph, acyclic, graph, connected
There are 4 references to this entry.
This is version 3 of spanning tree, born on 2002-02-25, modified 2004-03-26.
Object id is 2709, canonical name is SpanningTree.
Accessed 3720 times total.
Classification:
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|