next | previous | forward | backward | up | index | toc

# spanningTree -- returns a spanning tree of a graph

## Synopsis

• Usage:
T = spanningTree(G)
• Inputs:
• G, ,
• Outputs:
• T, , the spanning tree of G

## Description

This function returns a breadth first spanning tree of a graph.

 i1 : R = QQ[x_1..x_6]; i2 : C = cycle R; -- a 6-cycle i3 : spanningTree C o3 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }}} 1 2 2 3 3 4 4 5 5 6 "ring" => R "vertices" => {x , x , x , x , x , x } 1 2 3 4 5 6 o3 : Graph i4 : T = graph {x_1*x_2,x_2*x_3, x_1*x_4,x_1*x_5,x_5*x_6}; -- a tree (no cycles) i5 : T == spanningTree T o5 = true i6 : G = graph {x_1*x_2,x_2*x_3,x_3*x_1,x_4*x_5,x_5*x_6,x_6*x_4}; -- two three cycles i7 : spanningTree G o7 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }}} 1 2 1 3 4 5 4 6 "ring" => R "vertices" => {x , x , x , x , x , x } 1 2 3 4 5 6 o7 : Graph

## Ways to use spanningTree :

• spanningTree(Graph)

## For the programmer

The object spanningTree is .