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

allSpanningTrees -- find the spanning trees of the underlying graph

Synopsis

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 is a brute force one, which takes all size N - 1 subsets of the quiver arrows, where N is the number of vertices in the quiver, 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}}
                 synonym => toric quiver
                 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.