Graph Theory - Maple Help

GraphTheory

A substantial effort was put into Graph Theory for Maple 2021, including new commands for graph computation and advances in visualization.

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

New commands

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}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 25 vertices and 24 edge\left(s\right)}}$ (1.1.1)
 > $\mathrm{DrawGraph}\left(T,\mathrm{style}=\mathrm{tree}\right)$
 > $\mathrm{Newick}\left(T\right)$
 ${"\left(\left(\left(7\right)13\right)14,\left(3\right)18,\left(\left(\left(21\right)12,22\right)10,\left(\left(\left(15,\left(\left(5,9,23\right)2,16\right)19\right)4,8,\left(20\right)25\right)6,11\right)17\right)24\right)1;"}$ (1.1.2)
 > $\mathrm{PrueferCode}\left(T\right)$
 $\left[{18}{,}{2}{,}{13}{,}{6}{,}{2}{,}{17}{,}{14}{,}{1}{,}{4}{,}{19}{,}{1}{,}{24}{,}{25}{,}{12}{,}{10}{,}{10}{,}{24}{,}{2}{,}{19}{,}{4}{,}{6}{,}{17}{,}{6}\right]$ (1.1.3)

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 $\left\{a,b\right\}$ from the Hoffman-Singleton graph and deleting all vertices incident to $a$ or $b$.

 >
 ${\mathrm{HS}}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 50 vertices and 175 edge\left(s\right)}}$ (1.2.1)
 >
 ${\mathrm{edge}}{≔}\left\{{20}{,}{25}\right\}$ (1.2.2)
 >
 ${G}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 36 vertices and 90 edge\left(s\right)}}$ (1.2.3)

With IdentifyGraph, we discover that this subgraph has a name: it is isomorphic to the Sylvester graph.

 > $\mathrm{IdentifyGraph}\left(G\right)$
 $\left[\left[{\mathrm{SpecialGraphs}}{:-}{\mathrm{SylvesterGraph}}\right]\right]$ (1.2.4)

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.

 >
 ${\mathrm{SG}}{≔}{\mathrm{Graph 4: an undirected unweighted graph with 36 vertices and 90 edge\left(s\right)}}$ (1.3.1)
 >
 ${\mathrm{true}}$ (1.3.2)

New functionality for existing commands

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 $\left(i,j\right)$ 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.

 >
 > $\mathrm{dataplot}\left(M,\mathrm{heatmap},\mathrm{color}=\mathrm{green}..\mathrm{red}\right)$

We now transform $M$ into a 14x14 block matrix which will be the weight matrix for a bipartite graph:

 >
 ${{\mathrm{_rtable}}}_{{36893488152086811940}}$ (2.1)

The 14 vertices of this graph will be the seven workers and seven tasks.

 >
 ${V}{≔}\left[{"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"}\right]$ (2.2)
 >
 ${G}{≔}{\mathrm{Graph 5: an undirected weighted graph with 14 vertices and 49 edge\left(s\right)}}$ (2.3)

Here we see an optimal solution for this problem, assigning Task 1 to Person 7, Task 2 to Person 2, etc.

 > $\mathrm{GraphTheory}:-\mathrm{BipartiteMatching}\left(G\right)$
 ${153}{,}\left\{\left\{{"Task 1"}{,}{"Worker 7"}\right\}{,}\left\{{"Task 2"}{,}{"Worker 2"}\right\}{,}\left\{{"Task 3"}{,}{"Worker 1"}\right\}{,}\left\{{"Task 4"}{,}{"Worker 5"}\right\}{,}\left\{{"Task 5"}{,}{"Worker 6"}\right\}{,}\left\{{"Task 6"}{,}{"Worker 3"}\right\}{,}\left\{{"Task 7"}{,}{"Worker 4"}\right\}\right\}$ (2.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:

 > $\mathrm{GraphTheory}:-\mathrm{BipartiteMatching}\left(M\right)$
 ${153}{,}\left\{\left[{1}{,}{7}\right]{,}\left[{2}{,}{2}\right]{,}\left[{3}{,}{1}\right]{,}\left[{4}{,}{5}\right]{,}\left[{5}{,}{6}\right]{,}\left[{6}{,}{3}\right]{,}\left[{7}{,}{4}\right]\right\}$ (2.5)

Performance improvements

The performance of the following GraphTheory commands has been substantially improved:

 Command Approximate Speedup Factor (compared with Maple 2020) AllPairsDistance (weighted) 3.1 4.8 Graph${}$ 8.8 GraphPower 4.6 IsBipartite${}$ 200 18 18 22 35 18 TransitiveClosure (unweighted) 2.5 TransitiveClosure (weighted) 3.4 TransitiveReduction (unweighted) 7.6 TransitiveReduction (weighted) 3.4 4.0

Maple 2021 provides support for 16 additional Special Graphs, bringing the total to 113.

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

Banana Tree

Bidiakis Cube

Butterfly Graph

Crown Graph

 > $\mathrm{DrawGraph}\left(\mathrm{BananaTree}\left(5,4\right),\mathrm{size}=\left[250,250\right]\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{BidiakisCube}\left(\right),\mathrm{size}=\left[250,250\right]\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{ButterflyGraph}\left(\right),\mathrm{size}=\left[250,250\right]\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{CrownGraph}\left(6\right),\mathrm{size}=\left[250,250\right]\right)$

Goldner-Harary Graph

Gosset Graph

King's Graph

Kittell Graph

 > $\mathrm{DrawGraph}\left(\mathrm{GoldnerHararyGraph}\left(\right),\mathrm{size}=\left[250,250\right]\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{GossetGraph}\left(\right),\mathrm{style}=\mathrm{spring}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{KingsGraph}\left(8,8\right),\mathrm{size}=\left[300,300\right]\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{KittellGraph}\left(\right),\mathrm{style}=\mathrm{planar},\mathrm{size}=\left[250,250\right]\right)$

Knight's Graph

Krackhardt Kite Graph

Markström Graph

 > $\mathrm{DrawGraph}\left(\mathrm{KnightsGraph}\left(8,8\right),\mathrm{size}=\left[300,300\right]\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{KrackhardtKiteGraph}\left(\right),\mathrm{size}=\left[250,250\right],\mathrm{style}=\mathrm{spring}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{LadderGraph}\left(5\right),\mathrm{size}=\left[250,250\right]\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{MarkstroemGraph}\left(\right),\mathrm{style}=\mathrm{planar},\mathrm{size}=\left[250,250\right]\right)$

Queen's Graph

Sousselier Graph

Walther Graph

Watkins Snark

 > $\mathrm{DrawGraph}\left(\mathrm{QueensGraph}\left(8,8\right),\mathrm{size}=\left[300,300\right]\right)$
 >
 > $\mathrm{DrawGraph}\left(\mathrm{WaltherGraph}\left(\right),\mathrm{size}=\left[300,300\right]\right)$
 >