A substantial effort was put into Graph Theory for Maple 2021, including new commands for graph computation and advances in visualization.
New functionality for existing commands
Additions to SpecialGraphs
These commands are new for Maple 2021:
Tree encodings: Newick and PrueferCode
The new Newick and PrueferCode offer alternate ways to encode a tree as a string or list of integers.
T ≔ RandomGraphs:-RandomTree25,seed=1024
T≔Graph 1: an undirected unweighted graph with 25 vertices and 24 edge(s)
IdentifyGraph: find isomorphisms among named special graphs
IdentifyGraph tests a graph for isomorphism against many of the named special graphs known to GraphTheory.
In this example we begin by picking any edge a,b from the Hoffman-Singleton graph and deleting all vertices incident to a or b.
HS≔Graph 2: an undirected unweighted graph with 50 vertices and 175 edge(s)
edge ≔ EdgesHS100
G ≔ DeleteVertexHS, convertNeighborhoodHS,edge1,set union convertNeighborhoodHS,edge2,set
G≔Graph 3: an undirected unweighted graph with 36 vertices and 90 edge(s)
With IdentifyGraph, we discover that this subgraph has a name: it is isomorphic to the Sylvester graph.
IsSubgraphIsomorphic: test for isomorphism against subgraphs of a graph
IsSubgraphIsomorphic tests whether a given graph is isomorphic to a subgraph of another given graph. This problem is strictly harder than the graph isomorphism problem.
Returning to the above example, here we show again that the Sylvester graph is isomorphic to a subgraph of the Hoffman-Singleton graph. Note however that we did not need to explicit construct the subgraph beforehand.
SG≔Graph 4: an undirected unweighted graph with 36 vertices and 90 edge(s)
The BipartiteMatching command has been extended to support weighted graphs, on which it computes a minimum weight maximum matching using the Kuhn-Munkres algorithm, also known as the Hungarian algorithm.
We begin with a 7x7 matrix whose rows represent seven workers and whose columns represent seven tasks, in which entry i,j represents the cost for worker i to complete task j. Our goal is to find an assignment of tasks to workers which minimizes the total cost.
M ≔ 1277333371953639979067279973438957818445629664101136584067728023916153447077236544564778465:
We now transform M into a 14x14 block matrix which will be the weight matrix for a bipartite graph:
WM ≔ Matrix Matrix7;M|M%T;Matrix7
The 14 vertices of this graph will be the seven workers and seven tasks.
V ≔ seqsprintfWorker %d, i,i=1..7,seqsprintfTask %d, i,i=1..7;
V≔Worker 1,Worker 2,Worker 3,Worker 4,Worker 5,Worker 6,Worker 7,Task 1,Task 2,Task 3,Task 4,Task 5,Task 6,Task 7
G ≔ GraphTheory:-GraphV, WM
G≔Graph 5: an undirected weighted graph with 14 vertices and 49 edge(s)
Here we see an optimal solution for this problem, assigning Task 1 to Person 7, Task 2 to Person 2, etc.
153,Task 1,Worker 7,Task 2,Worker 2,Task 3,Worker 1,Task 4,Worker 5,Task 5,Worker 6,Task 6,Worker 3,Task 7,Worker 4
Here is constructed the bipartite graph explicitly, but we can optionally also simply provide the original 7x7 matrix M directly to BipartiteMatching to produce a similar result:
The performance of the following GraphTheory commands has been substantially improved:
Approximate Speedup Factor
(compared with Maple 2020)
Maple 2021 provides support for 16 additional Special Graphs, bringing the total to 113.
Krackhardt Kite Graph
Download Help Document