GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/TravelingSalesman

GraphTheory

  

TravelingSalesman

 

Calling Sequence

Parameters

Description

Examples

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

withGraphTheory:

GGraph1,2,2,2,3,2,3,4,2,4,1,2

GGraph 1: an undirected weighted graph with 4 vertices and 4 edge(s)

(1)

TravelingSalesmanG

8,1,2,3,4,1

(2)

AddEdgeG,2,4,1,1,3,1

Graph 1: an undirected weighted graph with 4 vertices and 6 edge(s)

(3)

DrawGraphG,style=circle

w,tourTravelingSalesmanG

w,tour6,1,2,4,3,1

(4)

HighlightTrailG,tour,red

DrawGraphG,style=circle

GCompleteGraph10:

MMatrix0,68,37,95,57,30,1,25,71,84,68,0,9,26,90,26,97,29,47,78,37,9,0,84,59,11,67,61,75,35,95,26,84,0,1,99,55,63,19,8,57,90,59,1,0,61,66,18,7,48,30,26,11,99,61,0,93,10,14,54,1,97,67,55,66,93,0,47,20,95,25,29,61,63,18,10,47,0,28,52,71,47,75,19,7,14,20,28,0,92,84,78,35,8,48,54,95,52,92,0:

TravelingSalesmanG,M

142,1,8,6,2,3,10,4,5,9,7,1

(5)

See Also

AllPairsDistance

IsHamiltonian

WeightMatrix