Ask Your Question
1

Is there a way to compute the list of rooted spanning trees or arborescences in a directed graph ?

asked 2017-04-13 03:12:24 -0500

David Auger gravatar image

Given a directed graph $D$ and a specified vertex $r$, I would like the list of all directed spanning trees, or arborescences, rooted in $r$. This can be computed by induction as is done for spanning trees in undirected graphs with the spanning_trees method of the class Graph, but it seems like this has not been implemented for directed graphs.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2017-04-14 14:04:37 -0500

tmonteil gravatar image

Indeed, it seems there is no method for enumerating spanning trees on digraphs (though there is a spanning_trees_countmethod for counting them based on the Kirchhoff matrix). If you have an implementation, let me suggest to add it into Sage itself, see http://www.sagemath.org/development.html

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2017-04-13 03:12:24 -0500

Seen: 132 times

Last updated: Apr 14