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{RandomGraphs}:-\mathrm{RandomTree}\left(25\,\mathrm{seed}\=1024\right)$ $T≔\mathrm{Graph\; 1:\; an\; undirected\; unweighted\; graph\; with\; 25\; vertices\; and\; 24\; edge(s)}$ (1.1.1) >  $\mathrm{DrawGraph}\left(T\,\mathrm{style}\=\mathrm{tree}\right)$ >  $\mathrm{Newick}\left(T\right)$ $''(((7)13)14,(3)18,(((21)12,22)10,(((15,((5,9,23)2,16)19)4,8,(20)25)6,11)17)24)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{SpecialGraphs}:-\mathrm{HoffmanSingletonGraph}\left(\right)$ $\mathrm{HS}≔\mathrm{Graph\; 2:\; an\; undirected\; unweighted\; graph\; with\; 50\; vertices\; and\; 175\; edge(s)}$ (1.2.1) >  $\mathrm{edge} ≔ \mathrm{Edges}\left(\mathrm{HS}\right)\left[100\right]$ $\mathrm{edge}≔\left\{20\,25\right\}$ (1.2.2) >  $G ≔ \mathrm{DeleteVertex}\left(\mathrm{HS}\, \mathrm{convert}\left(\mathrm{Neighborhood}\left(\mathrm{HS}\,\mathrm{edge}\left[1\right]\right)\,\mathrm{set}\right) \mathbf{union} \mathrm{convert}\left(\mathrm{Neighborhood}\left(\mathrm{HS}\,\mathrm{edge}\left[2\right]\right)\,\mathrm{set}\right)\right)$ $G≔\mathrm{Graph\; 3:\; an\; undirected\; unweighted\; graph\; with\; 36\; vertices\; and\; 90\; edge(s)}$ (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{SpecialGraphs}:-\mathrm{SylvesterGraph}\left(\right)$ $\mathrm{SG}≔\mathrm{Graph\; 4:\; an\; undirected\; unweighted\; graph\; with\; 36\; vertices\; and\; 90\; edge(s)}$ (1.3.1) >  $\mathrm{IsSubgraphIsomorphic}\left(\mathrm{SG}\, \mathrm{HS}\right)$ $\mathrm{true}$ (1.3.2)

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.

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

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

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

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:

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 Ladder 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{SousselierGraph}\left(\right)\, \mathrm{size}\=\left[250\,250\right]\right)$ >  $\mathrm{DrawGraph}\left(\mathrm{WaltherGraph}\left(\right)\,\mathrm{size}\=\left[300\,300\right]\right)$ >  $\mathrm{DrawGraph}\left(\mathrm{WatkinsSnark}\left(\right)\, \mathrm{style}\=\mathrm{spring}\,\mathrm{size}\=\left[300\,300\right]\right)$