TravelingSalesman - Maple Help

GraphTheory

 TravelingSalesman

 Calling Sequence TravelingSalesman(G) TravelingSalesman(G, M)

Parameters

 G - a connected (di)graph M - (optional) a Matrix containing edge weights

Description

 • The TravelingSalesman command returns two objects, w of type numeric and the second C a list which is a permutation of the vertices The first output is the optimal value for the traveling salesman problem, and the second is a Hamiltonian cycle that achieves the optimal value.
 • The algorithm is a branch-and-bound algorithm using the Reduce bound (see Kreher and Stinson, 1999).
 • If a second argument is specified, it is used for the weights. If an edge from vertex u to v is not in G then, regardless of the edge weight in M, it is treated as infinity.
 • If G is not a weighted graph then the adjacency matrix of G is used for the edge weights.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(\left\{\left[\left\{1,2\right\},2\right],\left[\left\{1,4\right\},2\right],\left[\left\{2,3\right\},2\right],\left[\left\{3,4\right\},2\right]\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected weighted graph with 4 vertices and 4 edge\left(s\right)}}$ (1)
 > $\mathrm{TravelingSalesman}\left(G\right)$
 ${8}{,}\left[{1}{,}{2}{,}{3}{,}{4}{,}{1}\right]$ (2)
 > $\mathrm{AddEdge}\left(G,\left\{\left[\left\{1,3\right\},1\right],\left[\left\{2,4\right\},1\right]\right\}\right)$
 ${\mathrm{Graph 1: an undirected weighted graph with 4 vertices and 6 edge\left(s\right)}}$ (3)
 > $\mathrm{DrawGraph}\left(G,\mathrm{style}=\mathrm{circle}\right)$
 > $w,\mathrm{tour}≔\mathrm{TravelingSalesman}\left(G\right)$
 ${w}{,}{\mathrm{tour}}{≔}{6}{,}\left[{1}{,}{2}{,}{4}{,}{3}{,}{1}\right]$ (4)
 > $\mathrm{HighlightTrail}\left(G,\mathrm{tour},\mathrm{red}\right)$
 > $\mathrm{DrawGraph}\left(G,\mathrm{style}=\mathrm{circle}\right)$
 > $G≔\mathrm{CompleteGraph}\left(10\right):$
 > $M≔\mathrm{Matrix}\left(\left[\left[0,68,37,95,57,30,1,25,71,84\right],\left[68,0,9,26,90,26,97,29,47,78\right],\left[37,9,0,84,59,11,67,61,75,35\right],\left[95,26,84,0,1,99,55,63,19,8\right],\left[57,90,59,1,0,61,66,18,7,48\right],\left[30,26,11,99,61,0,93,10,14,54\right],\left[1,97,67,55,66,93,0,47,20,95\right],\left[25,29,61,63,18,10,47,0,28,52\right],\left[71,47,75,19,7,14,20,28,0,92\right],\left[84,78,35,8,48,54,95,52,92,0\right]\right]\right):$
 > $\mathrm{TravelingSalesman}\left(G,M\right)$
 ${142}{,}\left[{1}{,}{8}{,}{6}{,}{2}{,}{3}{,}{10}{,}{4}{,}{5}{,}{9}{,}{7}{,}{1}\right]$ (5)