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

GraphTheory

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

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.

 >
 >
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 100 vertices and 4950 edge\left(s\right)}}$ (1.1.1)

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}{≔}{421.032920193835}{,}\left[{"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\text{'}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 \left(Port Elizabeth\right)"}{,}{"Durban \left(eThekwini\right)"}{,}{"Vereeniging \left(Emfuleni\right)"}{,}{"West Rand"}{,}{"Johannesburg"}{,}{"East Rand \left(Ekurhuleni\right)"}{,}{"Pretoria \left(Tshwane\right)"}{,}{"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"}\right]$ (1.1.2)

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

 >
 ${\mathrm{TG}}{≔}{\mathrm{Graph 2: an undirected graph with 100 vertices and 100 edge\left(s\right)}}$ (1.1.3)
 > $\mathrm{DrawGraph}\left(\mathrm{TG}\right)$

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

 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{Import}\left("example/AfricaMap.kml",\mathrm{base}=\mathrm{datadir}\right),\mathrm{DrawGraph}\left(\mathrm{TG},\mathrm{stylesheet}=\left[\mathrm{vertexcolor}=\mathrm{black}\right]\right)\right)$

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:

 >

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

 >

We can now pass the weight matrix $\mathrm{WM}$ directly to TravelingSalesman to get a new tour.

 >
 ${\mathrm{W2}}{,}{\mathrm{T2}}{≔}{616.778513706285}{,}\left[{"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\text{'}Djamena"}{,}{"Bangui"}{,}{"YaoundÃ©"}{,}{"Douala"}{,}{"Libreville"}{,}{"Kinshasa"}{,}{"Brazzaville"}{,}{"Pointe-Noire"}{,}{"Cabinda"}{,}{"Luanda"}{,}{"Benguela"}{,}{"Lubango"}{,}{"Cape Town"}{,}{"Gqeberha \left(Port Elizabeth\right)"}{,}{"Durban \left(eThekwini\right)"}{,}{"Vereeniging \left(Emfuleni\right)"}{,}{"West Rand"}{,}{"Johannesburg"}{,}{"East Rand \left(Ekurhuleni\right)"}{,}{"Pretoria \left(Tshwane\right)"}{,}{"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"}\right]$ (1.2.1)
 >
 ${\mathrm{TG2}}{≔}{\mathrm{Graph 3: an undirected graph with 100 vertices and 100 edge\left(s\right)}}$ (1.2.2)

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.

 >

Multigraph support

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

 >
 ${\mathrm{MG}}{≔}{\mathrm{Graph 3: an undirected multigraph with 4 vertices and 5 edge\left(s\right)}}$ (2.1)

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

 >
 ${\mathrm{true}}$ (2.2)

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.

 > $\mathrm{Edges}\left(\mathrm{MG}\right)$
 $\left[\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{3}{,}{4}\right\}\right]$ (2.3)
 > $\mathrm{EdgeMultiplicity}\left(\mathrm{MG},\left\{1,2\right\}\right)$
 ${2}$ (2.4)

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

 > $\mathrm{DrawGraph}\left(\mathrm{MG}\right)$

Graph products

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

 • The vertex set of H is the Cartesian product  where  and  are the vertex sets of $\mathrm{G__1}$ and $\mathrm{G__2}$, respectively.
 ${V}{}\left(\mathrm{G__2}\right)$ (3.1)
 • Two vertices $\left(\mathrm{u__1},\mathrm{v__1}\right)$ and $\left(\mathrm{u__2},\mathrm{v__2}\right)$ of $H$ are connected by an edge, iff some condition about  and  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:

 Name Edge Condition $\mathrm{u__1}$ and $\mathrm{v__1}$ share an edge in $\mathrm{G__1}$ or $\mathrm{u__2}$ and $\mathrm{v__2}$ share an edge in $\mathrm{G__2}$ $\mathrm{u__1}$ and $\mathrm{v__1}$ share an edge in $\mathrm{G__1}$, or $\mathrm{u__1}=\mathrm{v__1}$ in $\mathrm{G__1}$ and $\mathrm{u__2}$ and $\mathrm{v__2}$ share an edge in $\mathrm{G__2}$ $\mathrm{u__1}$ and $\mathrm{v__1}$ share an edge in $\mathrm{G__1}$ and $\mathrm{u__2}$ and $\mathrm{v__2}$ share an edge in $\mathrm{G__2}$, or $\mathrm{u__1}$ and $\mathrm{v__1}$ do not share an edge in $\mathrm{G__1}$ and $\mathrm{u__2}$ and $\mathrm{v__2}$ do not share an edge in $\mathrm{G__2}$ $\mathrm{u__1}=\mathrm{v__1}$ in $\mathrm{G__1}$ and $\mathrm{u__2}$ and $\mathrm{v__2}$ share an edge in $\mathrm{G__2}$, or $\mathrm{u__1}$ and $\mathrm{v__1}$ share an edge in $\mathrm{G__1}$ and $\mathrm{u__2}=\mathrm{v__2}$ in $\mathrm{G__2}$ or $\mathrm{u__1}$ and $\mathrm{v__1}$ share an edge in $\mathrm{G__1}$ and $\mathrm{u__2}$ and $\mathrm{v__2}$ share an edge in $\mathrm{G__2}$

 >
 ${C}{≔}{\mathrm{Graph 4: an undirected graph with 3 vertices and 3 edge\left(s\right)}}$ (3.2)
 >
 ${H}{≔}{\mathrm{Graph 5: an undirected graph with 5 vertices and 6 edge\left(s\right)}}$ (3.3)
 >
 ${\mathrm{LP}}{≔}{\mathrm{Graph 6: an undirected graph with 15 vertices and 93 edge\left(s\right)}}$ (3.4)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{DrawGraph}~\left(⟨C|H|\mathrm{LP}⟩\right)\right)$

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

 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$

Bishops's Graph

Bouquet Graph

Dipole Graph

 >
 ${\mathrm{BG46}}{≔}{\mathrm{Graph 7: an undirected graph with 20 vertices and 40 edge\left(s\right)}}$ (4.1.1)
 >
 >
 ${\mathrm{BG}}{≔}{\mathrm{Graph 8: an undirected multigraph with 1 vertex, no edges, and 5 self-loops}}$ (4.1.2)
 >
 >
 ${\mathrm{DG}}{≔}{\mathrm{Graph 9: an undirected multigraph with 2 vertices and 2 edge\left(s\right)}}$ (4.1.3)
 >

Hamming Graph

House Graph

Windmill Graph

 >
 ${\mathrm{HG33}}{≔}{\mathrm{Graph 10: an undirected graph with 27 vertices and 81 edge\left(s\right)}}$ (4.1.4)
 >
 >
 ${\mathrm{HG}}{≔}{\mathrm{Graph 11: an undirected graph with 5 vertices and 6 edge\left(s\right)}}$ (4.1.5)
 > $\mathrm{DrawGraph}\left(\mathrm{HG},\mathrm{stylesheet}=\left[\mathrm{vertexpadding}=10\right]\right)$
 >
 ${\mathrm{WG}}{≔}{\mathrm{Graph 12: an undirected graph with 15 vertices and 21 edge\left(s\right)}}$ (4.1.6)
 > $\mathrm{DrawGraph}\left(\mathrm{WG},\mathrm{stylesheet}=\left[\mathrm{vertexpadding}=10\right]\right)$