Graph Theory - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


A substantial effort was put into Graph Theory for Maple 2023, including improved ability to solve traveling salesman problems, support for multigraphs, new commands for graph computation, and advances in visualization.



Traveling Salesman

Multigraph support

Graph products

Additions to SpecialGraphs

Traveling Salesman

The TravelingSalesman command now makes use of Concorde, a well-known library implementing highly efficient heuristics for solving instances of the traveling salesman problem. This addition considerably increases the size of problems which TravelingSalesman is able to handle.

Example: Using TravelingSalesman with vertexpositions

In the following example, we import a dataset of the 100 largest cities in the continent of Africa (including the island of Madagascar) and ask TravelingSalesman to find a minimal tour of them.

AfricanCities  Importexample/AfricanCities100.tsv,base=datadir,output=Matrix,skiplines=1

G  CompleteGraph convertAfricanCities..,2,list, vertexpositions=AfricanCities..,6,5

GGraph 1: an undirected graph with 100 vertices and 4950 edge(s)


With the new vertexpositions option, TravelingSalesman uses edge weights computed from the geometric distance between vertices in the graph layout specified previously when CompleteGraph was called. The new startvertex option allows a particular starting vertex to be specified.

W, T  TravelingSalesman G, vertexpositions,startvertex=Cairo

W,T421.032920193835,Cairo,Alexandria,Benghazi,Misratah,Tripoli,Tunis,Algiers,Oran,Tangier,Fez,Rabat,Casablanca,Marrakesh,Agadir,Nouakchott,Dakar,Conakry,Freetown,Monrovia,Bamako,Bobo Dioulasso,Ouagadougou,Niamey,Ilorin,Ibadan,Kumasi,Abidjan,Accra,Lomé,Abomey-Calavi,Lagos,Ikorodu,Benin City,Warri,Owerri,Umuahia,Onitsha,Nnewi,Port Harcourt,Yaoundé,Douala,Libreville,Uyo,Aba,Enugu,Lokoja,Abuja,Kaduna,Jos,Kano,Maiduguri,N'Djamena,Nyala,Bangui,Kisangani,Bunia,Kampala,Mwanza,Kigali,Bujumbura,Bukavu,Mbuji-Mayi,Kananga,Tshikapa,Kinshasa,Brazzaville,Pointe-Noire,Cabinda,Luanda,Benguela,Lubango,Cape Town,Gqeberha (Port Elizabeth),Durban (eThekwini),Vereeniging (Emfuleni),West Rand,Johannesburg,East Rand (Ekurhuleni),Pretoria (Tshwane),Matola,Maputo,Harare,Lusaka,Lubumbashi,Lilongwe,Blantyre,Antananarivo,Nampula,Dar es Salaam,Zanzibar,Mombasa,Nairobi,Mogadishu,Hargeisa,Addis Ababa,Asmara,Omdurman,Khartoum,Giza,Shubra el-Kheima,Cairo



We will illustrate the tour by constructing a subgraph consisting only of the edges included in the optimal tour across G.

TG  Subgraph G, TrailT ;

TGGraph 2: an undirected graph with 100 vertices and 100 edge(s)



To better visualize the tour we can combine this with a country map of Africa.


Using TravelingSalesman with an arbitrary weight matrix

The previous example demonstrates the use of TravelingSalesman with edge weights corresponding directly to geometric distances between vertices.  In many instances of the traveling salesman problem, the weights do not correspond so directly to the geometry.

Fortunately, TravelingSalesman can also compute a tour when given an arbitrary weight matrix. To illustrate this, let us extend the previous example of a tour of 100 African cities to incorporate the idea that there might be some increased cost associated with traversing an international border.

First let us get the matrix of Euclidean distances from the previous example:

DM  WeightMatrix MakeWeightedG,vertexpositions,metric=Euclidean

Now we can construct a new weight matrix WM in which the weight is doubled whenever the cities connected are in distinct countries.

WM  Matrix upperboundDM, i,jifelseAfricanCitiesi,3=AfricanCitiesj,3,DMi,j,2 DMi,j,datatype=double

We can now pass the weight matrix WM directly to TravelingSalesman to get a new tour.

 W2, T2  TravelingSalesman G, WM,startvertex=Cairo

W2,T2616.778513706285,Cairo,Shubra el-Kheima,Alexandria,Benghazi,Misratah,Tripoli,Tunis,Algiers,Oran,Fez,Tangier,Rabat,Casablanca,Marrakesh,Agadir,Nouakchott,Dakar,Conakry,Freetown,Monrovia,Bamako,Bobo Dioulasso,Ouagadougou,Niamey,Abidjan,Kumasi,Accra,Lomé,Abomey-Calavi,Lagos,Ikorodu,Ibadan,Ilorin,Benin City,Warri,Port Harcourt,Aba,Uyo,Umuahia,Owerri,Nnewi,Onitsha,Enugu,Lokoja,Abuja,Jos,Kaduna,Kano,Maiduguri,N'Djamena,Bangui,Yaoundé,Douala,Libreville,Kinshasa,Brazzaville,Pointe-Noire,Cabinda,Luanda,Benguela,Lubango,Cape Town,Gqeberha (Port Elizabeth),Durban (eThekwini),Vereeniging (Emfuleni),West Rand,Johannesburg,East Rand (Ekurhuleni),Pretoria (Tshwane),Matola,Maputo,Nampula,Antananarivo,Blantyre,Lilongwe,Harare,Lusaka,Lubumbashi,Mbuji-Mayi,Kananga,Tshikapa,Kisangani,Bunia,Bukavu,Bujumbura,Kigali,Kampala,Mwanza,Dar es Salaam,Zanzibar,Mombasa,Nairobi,Mogadishu,Hargeisa,Addis Ababa,Asmara,Khartoum,Nyala,Omdurman,Giza,Cairo


TG2  SubgraphG,TrailT2

TG2Graph 3: an undirected graph with 100 vertices and 100 edge(s)


This new tour is similar to the previous one in many respects, but notably does not visit Sudan or the Democratic Republic of the Congo twice as the first one did, illustrating the effect of our increased edge weights.


Finally we can draw the original tour (in green) and the new tour (in red) to see the effect of the altered weights.

 plots:-display DrawGraphTG,stylesheet=edgecolor=darkgreen|DrawGraphTG2,stylesheet=edgecolor=red


Multigraph support

GraphTheory now supports multigraphs. That is, graphs in which there may be multiple edges between the same pair of vertices.

MG  Graph4,0200201001020020,multigraph

MGGraph 3: an undirected multigraph with 4 vertices and 5 edge(s)


The new command IsMultigraph tests whether a graph is a multigraph.




Many other commands have been updated to support multigraphs.

The Edges command for this graph returns a list, not a set, and repeats the edge between vertices 3 and 4 twice.







Graph visualization commands such as DrawGraph will draw an integer weight on edges for which the edge multiplicity is greater than 1.



Graph products

A graph product is a binary operation on graphs which takes two graphs G__1 and G__2 and produces a graph H with the following properties:


The vertex set of H is the Cartesian product VG__1 × VG__2 where VG__1  and VG__2  are the vertex sets of G__1 and G__2, respectively.



Two vertices u__1,v__1 and u__2,v__2 of H are connected by an edge, iff some condition about u__1, v__1  G__1 and u__2, v__2  G__2 is fulfilled.

Many different graph products have been defined which differ in the condition imposed on the edges. To the existing CartesianProduct and TensorProduct commands, the following new graph products have been added:


Edge Condition


u__1 and v__1 share an edge in G__1 or u__2 and v__2 share an edge in G__2


u__1 and v__1 share an edge in G__1, or u__1=v__1 in G__1 and u__2 and v__2 share an edge in G__2


u__1 and v__1 share an edge in G__1 and u__2 and v__2 share an edge in G__2,
or u__1 and v__1 do not share an edge in G__1 and u__2 and v__2 do not share an edge in G__2


u__1=v__1 in G__1 and u__2 and v__2 share an edge in G__2,
or u__1 and v__1 share an edge in G__1 and u__2=v__2 in G__2
or u__1 and v__1 share an edge in G__1 and u__2 and v__2 share an edge in G__2


C  CycleGraph3

CGraph 4: an undirected graph with 3 vertices and 3 edge(s)


H  SpecialGraphs:-HouseGraph

HGraph 5: an undirected graph with 5 vertices and 6 edge(s)


LP  LexicographicProductC,H

LPGraph 6: an undirected graph with 15 vertices and 93 edge(s)




Additions to SpecialGraphs

Maple 2023 provides support for 6 additional Special Graphs, bringing the total to 119.  


Bishops's Graph

Bouquet Graph

Dipole Graph

BG46  BishopsGraph4,5

BG46Graph 7: an undirected graph with 20 vertices and 40 edge(s)


DrawGraphBG46, stylesheet = vertexpadding = 12

BG  BouquetGraph5

BGGraph 8: an undirected multigraph with 1 vertex, no edges, and 5 self-loops


DrawGraphBG, stylesheet = vertexpadding = 12

DG DipoleGraph2

DGGraph 9: an undirected multigraph with 2 vertices and 2 edge(s)


DrawGraphDG, stylesheet = vertexpadding = 12

Hamming Graph

 House Graph

 Windmill Graph

HG33  HammingGraph3,3

HG33Graph 10: an undirected graph with 27 vertices and 81 edge(s)


DrawGraphHG33,style=spring, stylesheet = vertexpadding = 12

HG HouseGraph

HGGraph 11: an undirected graph with 5 vertices and 6 edge(s)



WG  WindmillGraph3,7

WGGraph 12: an undirected graph with 15 vertices and 21 edge(s)