Macaulay2 » Documentation
Packages » ThinSincereQuivers » allSpanningTrees
next | previous | forward | backward | up | index | toc

allSpanningTrees -- find the spanning trees of the underlying graph

Description

This method returns all of the spanning trees of the underlying graph of the quiver Q. Trees are represented as lists of arrow indices.

The algorithm performs a depth-first search on each vertex and checks if the result is a connected graph.

i1 : Q = bipartiteQuiver(2, 3)

o1 = ToricQuiver{flow => {1, 1, 1, 1, 1, 1}                            }
                 IncidenceMatrix => | -1 -1 -1 0  0  0  |
                                    | 0  0  0  -1 -1 -1 |
                                    | 1  0  0  1  0  0  |
                                    | 0  1  0  0  1  0  |
                                    | 0  0  1  0  0  1  |
                 Q0 => {0, 1, 2, 3, 4}
                 Q1 => {{0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}}
                 weights => {-3, -3, 2, 2, 2}

o1 : ToricQuiver
 
i2 : allSpanningTrees(Q)

o2 = {{2, 3, 4, 5}, {1, 3, 4, 5}, {0, 3, 4, 5}, {0, 2, 4, 5}, {0, 1, 4, 5},
     ------------------------------------------------------------------------
     {1, 2, 3, 5}, {0, 1, 3, 5}, {0, 1, 2, 5}, {1, 2, 3, 4}, {0, 2, 3, 4},
     ------------------------------------------------------------------------
     {0, 1, 2, 4}, {0, 1, 2, 3}}

o2 : List

See also

For the programmer

The object allSpanningTrees is a function closure.

The source of this document is in ThinSincereQuivers.m2:3279:0.