[Maxima] Suggestions For Improvements To hamilton_path() Function In Graphs Package
tow_force at hotmail.com
Sat Aug 30 06:00:43 CDT 2008
Firstly on my wish list: it should know that any vertex with only 1 edge must be either a start or a finish point. Here's a 6x6 grid:
(%i4) mg: graph_product(path_graph(6), path_graph(6))$
(%i5) draw_graph(mg, show_id=true)$
Instantaneous result - excellent! Now add two vertices and connect them to the grid to force a particular starting and ending position for the path:
(%i21) add_vertices([36, 37], mg);
(%i22) connect_vertices(36, 0, mg);
(%i23) connect_vertices(37, 34, mg);
Maxima now goes into a deep think. I left it for at least an hour - but no result was forthcoming (the above works fine on a 4x4 grid btw).
My other wish is for another function (e.g. hamilton_path_count()) which simply finds out how many unique hamiltonian paths exist on a given graph. I am aware that there is no way to calculate this except for searching for them one by one, so this is a BIG ask - but if it could be done, it would be greatly appreciated!
btw - I always feel churlish asking for improvements to Maxima, because it is already so good, and so much excellent work has already gone into it.
Make a mini you on Windows Live Messenger!
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Maxima