Ask Your Question
0

Implementation of BEST theorem

asked 2024-02-17 03:40:01 +0100

Max Alekseyev gravatar image

updated 2024-02-17 03:41:07 +0100

BEST theorem provides a polynomial-time algorithm for enumeration of Eulerian circuits in a given directed graph. Is there is a readily available implementation of it in Sage?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2024-02-17 05:47:53 +0100

Max Alekseyev gravatar image

Apparently, BEST formula can be implemented as

def BEST_count(G):
    return G.spanning_trees_count() * prod(factorial(G.in_degree(v)-1) for v in G.vertices())
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

1 follower

Stats

Asked: 2024-02-17 03:40:01 +0100

Seen: 112 times

Last updated: Feb 17