PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
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)

View style:

See Also: tree, graph, minimum spanning tree, depth first search

Log in to rate this entry.
(view current ratings)

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:
AMS MSC05C05 (Combinatorics :: Graph theory :: Trees)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)