# [Maxima] Suggestions For Improvements To hamilton_path() Function In Graphs Package

Tawny Owl 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)\$
(%i6) hamilton_path(mg);
(%o6) [0,1,2,3,4,5,11,10,9,8,7,6,12,13,14,15,16,17,23,22,21,20,19,18,24,25,26,27,28,29,35,34,33,32,31,30]

Instantaneous result - excellent! Now add two vertices and connect them to the grid to force a particular starting and ending position for the path:

(%i22) connect_vertices(36, 0, mg);
(%i23) connect_vertices(37, 34, mg);
(%i26) hamilton_path(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!
http://clk.atdmt.com/UKM/go/107571437/direct/01/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.math.utexas.edu/pipermail/maxima/attachments/20080830/76af7939/attachment.htm
```