PlanetMath (more info)
 Math for the people, by the people.
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.

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ \bullet \ar@{.}[dddd] \ar@{-}[dd... ...]\ar@{.}[rr]&&\bullet\ar@{.}[dl] \ \bullet\ar@{.}[rrr]&&&\bullet } } \end{xy}$

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)

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 3136 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)