SpanningForest - Maple Help

GraphTheory

 SpanningTree
 construct spanning tree
 SpanningForest
 construct spanning forest

 Calling Sequence SpanningTree(G) SpanningTree(G, r) SpanningForest(G)

Parameters

 G - undirected graph r - vertex of the graph

Description

 • SpanningTree(G) returns a spanning tree of a connected graph G.
 • SpanningTree(G, r) returns a spanning tree of the connected component of G which contains vertex r.
 • SpanningForest(G) returns a spanning forest of the graph G.
 • By default, edge weights on G are ignored. To compute a minimal-weight spanning tree for a weighted graph, use MinimalSpanningTree.

Definitions

 • A spanning tree for a graph G is a subgraph of G which contains all the vertices of G and is a tree.
 • A spanning forest for a graph G is a subgraph of G which contains all the vertices of G and is a forest.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (1)
 > $\mathrm{T1}≔\mathrm{SpanningTree}\left(P\right)$
 ${\mathrm{T1}}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 10 vertices and 9 edge\left(s\right)}}$ (2)
 > $\mathrm{IsTree}\left(\mathrm{T1}\right)$
 ${\mathrm{true}}$ (3)
 > $\mathrm{DrawGraph}\left(P\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{T1}\right)$
 > $\mathrm{T2}≔\mathrm{SpanningTree}\left(P,5\right):$
 > $\mathrm{Edges}\left(\mathrm{T1}\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{5}\right\}{,}\left\{{1}{,}{6}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{2}{,}{9}\right\}{,}\left\{{4}{,}{5}\right\}{,}\left\{{5}{,}{8}\right\}{,}\left\{{6}{,}{7}\right\}{,}\left\{{6}{,}{10}\right\}\right\}$ (4)
 > $\mathrm{Edges}\left(\mathrm{T2}\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{5}\right\}{,}\left\{{1}{,}{6}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{4}{,}{5}\right\}{,}\left\{{4}{,}{10}\right\}{,}\left\{{5}{,}{8}\right\}{,}\left\{{7}{,}{8}\right\}{,}\left\{{8}{,}{9}\right\}\right\}$ (5)
 > $G≔\mathrm{GraphUnion}\left(\mathrm{CycleGraph}\left(\left[1,2,3\right]\right),\mathrm{CycleGraph}\left(\left[4,5,6\right]\right)\right)$
 ${G}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 6 vertices and 6 edge\left(s\right)}}$ (6)
 > $\mathrm{IsConnected}\left(G\right)$
 ${\mathrm{false}}$ (7)
 > $\mathrm{SpanningTree}\left(G,1\right)$
 ${\mathrm{Graph 4: an undirected unweighted graph with 6 vertices and 2 edge\left(s\right)}}$ (8)
 > $\mathrm{SpanningForest}\left(G\right)$
 ${\mathrm{Graph 5: an undirected unweighted graph with 6 vertices and 4 edge\left(s\right)}}$ (9)

Compatibility

 • The GraphTheory[SpanningForest] command was introduced in Maple 2021.