networks(deprecated)/spantree - Maple Help

networks

 spantree
 finds a minimum weight spanning tree

 Calling Sequence spantree(G) spantree(G, s) spantree(G, s, w)

Parameters

 G - graph or network s - starting or root vertex for the tree w - name for returning the sum of the edge weights in the tree

Description

 • Important: The networks package has been deprecated.Use the superseding command GraphTheory[MinimalSpanningTree] instead.
 • This routine constructs a spanning tree for the graph G.  The result is returned as a new graph derived from G and consisting of that spanning tree.
 • The chosen tree has edges which minimize the total edge weight of the tree.
 • The routine uses Prim's algorithm, which fails if G is not strongly connected.
 • The routine is normally loaded via the command with(networks) but may also be referenced using the full name networks[spantree](...).

Examples

Important:The networks package has been deprecated.Use the superseding command GraphTheory[MinimalSpanningTree] instead.

 > $\mathrm{with}\left(\mathrm{networks}\right):$
 > $G≔\mathrm{petersen}\left(\right):$
 > $\mathrm{ends}\left(G\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{5}\right\}{,}\left\{{1}{,}{6}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{2}{,}{8}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{3}{,}{10}\right\}{,}\left\{{4}{,}{5}\right\}{,}\left\{{4}{,}{7}\right\}{,}\left\{{5}{,}{9}\right\}{,}\left\{{6}{,}{7}\right\}{,}\left\{{6}{,}{10}\right\}{,}\left\{{7}{,}{8}\right\}{,}\left\{{8}{,}{9}\right\}{,}\left\{{9}{,}{10}\right\}\right\}$ (1)
 > $\mathrm{spantree}\left(G,1,w\right)$
 ${\mathbf{proc}}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{option}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{GRAPH}}{,}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{if}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Edges}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Edges}}\right){≔}\left\{{}\right\}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_EdgeIndex}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_EdgeIndex}}\right){≔}{\mathrm{table}}{}\left({\mathrm{symmetric}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Head}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Head}}\right){≔}{\mathrm{table}}{}\left({}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Tail}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Tail}}\right){≔}{\mathrm{table}}{}\left({}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Eweight}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Eweight}}\right){≔}{\mathrm{table}}{}\left({}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Ends}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Ends}}\right){≔}{\mathrm{table}}{}\left({}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Vertices}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Vertices}}\right){≔}\left\{{}\right\}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Vweight}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Vweight}}\right){≔}{\mathrm{table}}{}\left({\mathrm{sparse}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Ancestor}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Ancestor}}\right){≔}{\mathrm{table}}{}\left({}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Daughter}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Daughter}}\right){≔}{\mathrm{table}}{}\left({}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Neighbors}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Neighbors}}\right){≔}{\mathrm{table}}{}\left({}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Status}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Status}}\right){≔}\left\{{'}{\mathrm{SIMPLE}}{'}\right\}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{elif}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{=}{\mathrm{_Emaxname}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{thisproc}}{}\left({\mathrm{_Emaxname}}\right){≔}{0}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{else}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{'}{\mathrm{procname}}{}\left({\mathrm{args}}\right){'}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end if}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (2)
 > $\mathrm{ends}\left(\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{6}\right\}{,}\left\{{2}{,}{8}\right\}{,}\left\{{3}{,}{10}\right\}{,}\left\{{4}{,}{5}\right\}{,}\left\{{4}{,}{7}\right\}{,}\left\{{5}{,}{9}\right\}{,}\left\{{6}{,}{10}\right\}{,}\left\{{8}{,}{9}\right\}\right\}$ (3)
 > $w$
 ${9}$ (4)