 Graph Theory - Maple Help

GraphTheory

A substantial effort was put into Graph Theory for Maple 2020, including significant advances in visualization, flexible graph manipulation options, powerful analysis tools, and support for over 20 new special graphs and graph properties.

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

Maple 2020 offers eight new functions for calculating the centrality of vertices in a graph. These are:

 •
 •
 •
 •
 •
 •
 •
 •

Here is an example of a simple social graph where the graph centrality measures social influence.

 >
 >
 > $\mathrm{Gs}≔\mathrm{Graph}\left(\mathrm{vertices},\mathrm{edges_weights}\right)$
 ${\mathrm{Gs}}{≔}{\mathrm{Graph 1: an undirected weighted graph with 11 vertices and 22 edge\left(s\right)}}$ (1.1)
 > > $\mathrm{centrality}≔\mathrm{EigenvectorCentrality}\left(\mathrm{Gs}\right)$
 ${\mathrm{centrality}}{≔}\left[{0.237978443268371}{,}{0.131195758579289}{,}{0.116408170276784}{,}{0.0410886760673835}{,}{0.113645015600347}{,}{0.00850460849139520}{,}{0.0148924786849715}{,}{0.271820184196355}{,}{0.00435475160238433}{,}{0.0207000263726866}{,}{0.0394118868600335}\right]$ (1.2)
 > $\mathrm{ind}≔\mathrm{sort}\left(\mathrm{centrality},\mathrm{>},\mathrm{output}=\mathrm{permutation}\right):$
 >  Graph Styling Improvements

The stylesheet option to DrawGraph is now fully supported for animations and all options except the ones controlling the shapes of vertices and arrows are supported for three-dimensional graphs.

 >
 ${S}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 60 vertices and 90 edge\left(s\right)}}$ (2.1)
 > The animate option to DrawGraph can now be set to a positive integer to control the number of frames generated.

 >
 ${P}{≔}{\mathrm{Graph 4: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (2.2)
 > A few new ways to style graphs were also added. A new arrowshape style was added for directed edges allowing any shape supported by plottools. As well, the arrowpos directive has been greatly improved to be more accurate. Vertex borders can now be given a color including several special dynamic coloring options "_contrast", "_blend", and "_match" which are also supported for vertex font colors, edge color, and edge font colors.

New commands have been introduced for adding styles to graph components that are independent of the concept of "highlighting". These are StyleVertex, StyleEdge, and StyleSubgraph and have basically the same calling sequences as their Highlight equivalents. They differ from their Highlight versions in that when called multiple times, they add to the existing style rather than replace it and they build on the base default style rather than the base "highlighted" style.

 >
 ${\mathrm{Gd}}{≔}{\mathrm{Graph 5: a directed weighted graph with 3 vertices and 5 arc\left(s\right)}}$ (2.3)
 >
 >
 > $\mathrm{DrawGraph}\left(\mathrm{Gd}\right);$  Style Vertices and Edges by Properties

You can now visually style graph vertices and edges with respect to properties, such as centrality or weight. For example, given its centrality, the color of a vertex can be chosen from a gradient of colors—this lets you emphasize the more important vertices in a graph. Similarly, those edges with greater weight can be assigned greater thickness.

In this example, given the

 • eigenvector centrality of a vertex, we linearly transition between two colors and two font sizes.
 • weight of an edge, we linearly transition between two colors and thicknesses.
 >
 > $\mathrm{DrawGraph}\left(\mathrm{Gs},\mathrm{style}=\mathrm{spring},\mathrm{stylesheet}=\left[\mathrm{vertexfontcolor}=\mathrm{white},\mathrm{vertexborder}=\mathrm{false},\mathrm{vertexpadding}=4\right],\mathrm{title}="Social Media Graph",\mathrm{titlefont}=\left[\mathrm{Arial},16\right],\mathrm{size}=\left[600,600\right],\mathrm{showweights}=\mathrm{false}\right)$ In this example, we demonstrate the valuesplit styling option that styles with a discrete set of values rather than a gradient or range:

 • for vertices, we assign specific colors and font sizes to ranges of the eigenvector centrality.
 • for edges, we assign specific colors and thicknesses to ranges of the weight.
 > $\mathrm{c1}≔"#67809F":$$\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{c2}≔"#004F79":$$\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{c3}≔"#96281B":\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}$$\mathrm{StyleVerticesByProperty}\left(\mathrm{Gs},\mathrm{EigenvectorCentrality},\mathrm{colorscheme}=\left["valuesplit",\left[..0.1=\mathrm{c1},0.1..0.25=\mathrm{c2},\mathrm{c3}\right]\right],\mathrm{fontsizescheme}=\left["valuesplit",\left[..0.2=10,18\right]\right]\right);$$\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{StyleEdgesByProperty}\left(\mathrm{Gs},\mathrm{WeightMatrix},\mathrm{colorscheme}=\left["valuesplit",\left[..20=\mathrm{c1},\mathrm{c2}\right]\right],\mathrm{thicknessscheme}=\left["valuesplit",\left[..10=1,10..20=2,4\right]\right]\right):$
 > $\mathrm{DrawGraph}\left(\mathrm{Gs},\mathrm{style}=\mathrm{spring},\mathrm{stylesheet}=\left[\mathrm{vertexfontcolor}=\mathrm{white},\mathrm{vertexborder}=\mathrm{false},\mathrm{vertexpadding}=4\right],\mathrm{title}="Social Media Graph",\mathrm{titlefont}=\left[\mathrm{Arial},16\right],\mathrm{size}=\left[600,600\right],\mathrm{showweights}=\mathrm{false}\right)$  Graph Layout Methods

Maple 2020 offers a number of new ways to lay out plots of graphs.  The style option from previous version has been renamed layout to better clarify the difference between stylesheets and the layout of the vertices.  (The old option name style will continue to be supported as an alias for layout however).  A new option layoutoptions has been added to pass in options to layout methods to further customize them.

 >
 ${\mathrm{Gp}}{≔}{\mathrm{Graph 7: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (4.1)
 > There is a new interactive method to lay out graphs manually starting from a selected layout. A plot component is created where vertices can either be dragged or selected and moved to new positions. The new position will be stored as the 'user' layout, and will be the default layout for future calls to DrawGraph.

 >
 ${\mathrm{Gr}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 10 vertices and 25 edge\left(s\right)}}$ (4.2)
 >

 > $\mathrm{DrawGraph}\left(\mathrm{Gr}\right)$ There are a few new layout methods, most notably, a new spectral two- and three-dimensional layout method.

 >
 ${\mathrm{G1}}{≔}{\mathrm{Graph 8: an undirected unweighted graph with 100 vertices and 250 edge\left(s\right)}}$ (4.3)
 > $\mathrm{DrawGraph}\left(\mathrm{G1},\mathrm{layout}=\mathrm{spectral}\right)$ > $\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{DrawGraph}\left(\mathrm{G1},\mathrm{layout}=\mathrm{spectral},\mathrm{dimension}=3\right)$ A full list of layout methods is on the Graph Layout Methods help page. The grid and random layout methods are also new in Maple 2020 and support two and three dimensions. Self-Loops

The core routines of the GraphTheory package have been extended to support graphs with self-loops.  Graphs with self-loops may be directed or undirected, and weighted or unweighted.

The number of self-loops in a graph is displayed in the graph description along with the vertex and edge count:

 >
 ${G}{≔}{\mathrm{Graph 11: a directed unweighted graph with 125 vertices, 620 arc\left(s\right), and 5 self-loop\left(s\right)}}$ (5.1)

Several new commands have been added to work with self-loops:

 • HasSelfLoops returns true if a graph has an edge or arc to itself.
 • NumberOfSelfLoops returns the number of self-loops in a graph.
 • SelfLoops returns the set of self-loops in a graph.

The HasSelfLoop and NumberOfSelfLoops commands permit querying graphs for the existence and number of self-loops, respectively, while SelfLoops returns the set of vertices with self-loops.

 > $\mathrm{HasSelfLoop}\left(G\right)$
 ${\mathrm{true}}$ (5.2)
 > $\mathrm{NumberOfSelfLoops}\left(G\right)$
 ${5}$ (5.3)
 > $\mathrm{SelfLoops}\left(G\right)$
 $\left\{{1}{,}{32}{,}{63}{,}{94}{,}{125}\right\}$ (5.4)

Directed Graphs with Self-Loops

The support for self-loops extends to both directed and undirected graphs.  Here is a directed graph with a self-loop at vertex 1:

 >
 ${\mathrm{G1}}{≔}{\mathrm{Graph 8: a directed unweighted graph with 4 vertices, 5 arc\left(s\right), and 1 self-loop\left(s\right)}}$ (5.5)
 > $\mathrm{DrawGraph}\left(\mathrm{G1}\right)$ > $\mathrm{NumberOfSelfLoops}\left(\mathrm{G1}\right)$
 ${1}$ (5.6)

The Edges command now returns self-loops in its list of edges.  If only edges between distinct vertices are desired, the option selfloops=false can be specified:

 > $\mathrm{Edges}\left(\mathrm{G1}\right)$
 $\left\{\left[{1}{,}{1}\right]{,}\left[{1}{,}{2}\right]{,}\left[{1}{,}{3}\right]{,}\left[{1}{,}{4}\right]{,}\left[{2}{,}{3}\right]{,}\left[{3}{,}{4}\right]\right\}$ (5.7)
 > $\mathrm{Edges}\left(\mathrm{G1},\mathrm{selfloops}=\mathrm{false}\right)$
 $\left\{\left[{1}{,}{2}\right]{,}\left[{1}{,}{3}\right]{,}\left[{1}{,}{4}\right]{,}\left[{2}{,}{3}\right]{,}\left[{3}{,}{4}\right]\right\}$ (5.8)

The in-degree and out-degree of a vertex are each increased by one when it receives a self-loop:

 > $\mathrm{InDegree}\left(\mathrm{G1},1\right)$
 ${1}$ (5.9)
 > $\mathrm{OutDegree}\left(\mathrm{G1},1\right)$
 ${4}$ (5.10)

Undirected Graphs with Self-Loops

We can produce a copy of G1 which discards the directionality of its edges while preserving self-loops by calling UnderlyingGraph with the selfloops option:

 >
 ${\mathrm{G2}}{≔}{\mathrm{Graph 9: an undirected unweighted graph with 4 vertices, 5 edge\left(s\right), and 1 self-loop\left(s\right)}}$ (5.11)
 > $\mathrm{DrawGraph}\left(\mathrm{G2}\right)$ By convention, the degree of a vertex is increased by 2 when it receives a self-loop:

 > $\mathrm{DegreeSequence}\left(\mathrm{G2}\right)$
 $\left[{5}{,}{2}{,}{3}{,}{2}\right]$ (5.12)

In a simple graph the smallest possible girth (length of the shortest cycle) is 3.  In a graph with a self-loop, the length of the shortest cycle is 1:

 > $\mathrm{Girth}\left(\mathrm{G2}\right)$
 ${1}$ (5.13)

By definition, any graph with a self-loop cannot be colored with any number of colors. The chromatic polynomial therefore is identically zero:

 > $\mathrm{ChromaticPolynomial}\left(\mathrm{G2},x\right)$
 ${0}$ (5.14)

Removing self-loops

We can generate a copy of a graph with the self-loops removed simply by calling UnderlyingGraph without specifying the selfloops option:

 >
 ${\mathrm{G3}}{≔}{\mathrm{Graph 10: an undirected unweighted graph with 4 vertices and 5 edge\left(s\right)}}$ (5.15)
 > $\mathrm{NumberOfSelfLoops}\left(\mathrm{G3}\right)$
 ${0}$ (5.16)
 > $\mathrm{DegreeSequence}\left(\mathrm{G3}\right)$
 $\left[{3}{,}{2}{,}{3}{,}{2}\right]$ (5.17)
 > $\mathrm{Girth}\left(\mathrm{G3}\right)$
 ${3}$ (5.18)
 > $\mathrm{ChromaticPolynomial}\left(\mathrm{G3},x\right)$
 ${x}{}\left({x}{-}{1}\right){}{\left({x}{-}{2}\right)}^{{2}}$ (5.19) Geometric Graphs

A new Maple 2020 function in RandomGraphs subpackage generates a random geometric graph.

 > $\mathrm{G5}≔\mathrm{RandomGraphs}:-\mathrm{RandomGeometricGraph}\left(10,2,\mathrm{distribution}=\mathrm{Weibull}\left(3,2\right),\mathrm{weighted}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{G5}\right)$ Maple 2020 contains a new subpackage, GeometricGraphs, for generating graphs from geometric data, such as a set of 2-D or 3-D points.  This subpackage includes the following new commands:

 •
 •
 •
 •
 •
 •
 •
 •

 > $\mathrm{with}\left(\mathrm{GeometricGraphs}\right);$
 $\left[{\mathrm{DelaunayGraph}}{,}{\mathrm{EuclideanMinimumSpanningTree}}{,}{\mathrm{FarthestNeighborGraph}}{,}{\mathrm{GabrielGraph}}{,}{\mathrm{GeometricMinimumSpanningTree}}{,}{\mathrm{NearestNeighborGraph}}{,}{\mathrm{RelativeNeighborhoodGraph}}{,}{\mathrm{SphereOfInfluenceGraph}}{,}{\mathrm{UnitDiskGraph}}{,}{\mathrm{UrquhartGraph}}{,}{\mathrm{VisibilityGraph}}\right]$ (6.1)
 > $\mathrm{points}≔\mathrm{Matrix}\left(50,2,\mathrm{rand}\left(0..100.\right)\right):$

The Euclidean minimum spanning tree, the Delaunay graph, the Gabriel graph, the relative neighborhood graph, and the Urquhart graph are all derived from a Delaunay triangulation of the point data.

These graphs have a hierarchical relationship:

 • The Euclidean minimum spanning tree is a subgraph of the relative neighborhood graph,
 • The relative neighborhood graph is a subgraph of the Urquhart graph,
 • The Urquhart graph is a subgraph of the Gabriel graph.
 • The Gabriel graph is a subgraph of the Delaunay graph.

Euclidean Minimum Spanning Tree     Note that we can also build spanning trees for this point data using norms other than the Euclidean norm, for example the 1-norm; the result is similar but not identical to the Euclidean spanning tree. NearestNeighborGraph and FarthestNeighborGraph return a nearest and farthest neighbor graph for a point set.  You can also build k-nearest neighbor and k-farthest neighbor graphs for specified k.

Nearest Neighbor Graph

Farthest Neighbor Graph

2-Nearest Neighbor

2-Farthest Neighbor    The UnitDiskGraph command returns a graph in which two points are connected if their distance falls below a specified threshold.

 > $\mathrm{DrawGraph}\left(\mathrm{UnitDiskGraph}\left(\mathrm{points},15\right)\right)$ For a set of points, SphereOfInfluenceGraph draws a circle around each point with radius equal to the distance to its nearest neighbor. The sphere of influence graph is the graph whose vertices correspond to these points in which an edge between two points exists if the corresponding circles intersect at more than one point.

 > $\mathrm{DrawGraph}\left(\mathrm{SphereOfInfluenceGraph}\left(\mathrm{points}\right)\right)$ Most of these graphs commands are not limited to two dimensions, and can be used to analyze and visualize relationships with higher-dimensional data as well.

$\mathrm{points3D}≔\mathrm{Matrix}\left(50,3,\mathrm{rand}\left(0..100.\right)\right):$  Split Graphs

IsSplitGraph returns true if a graph is can be partitioned into a clique and an independent set.

 >
 ${\mathrm{G3}}{≔}{\mathrm{Graph 12: an undirected unweighted graph with 5 vertices and 6 edge\left(s\right)}}$ >
 ${\mathrm{result}}{,}{\mathrm{split}}{≔}{\mathrm{true}}{,}\left[\left[{2}{,}{3}{,}{4}\right]{,}\left[{1}{,}{5}\right]\right]$ (7.1)
 >
 > $\mathrm{DrawGraph}\left(\mathrm{G3}\right)$  ContractSubgraph

The ContractSubgraph command returns a new graph with all the vertices in S merged into a single vertex. The neighborhood of the new vertex will be the union of the neighborhoods of all of merged vertices.

 > $C≔\mathrm{CycleGraph}\left(6\right):$$\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}H≔\mathrm{ContractSubgraph}\left(C,\left[1,2,6\right]\right)$
 ${H}{≔}{\mathrm{Graph 13: an undirected unweighted graph with 4 vertices and 4 edge\left(s\right)}}$ (8.1)
 > $\mathrm{DrawGraph}\left(H\right)$  SpecialGraphs

Maple 2020 provides support for 18 additional Special Graphs, bringing the total to 97.

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

Barnette-Bosák-Lederberg Graph

Berlekamp-van Lint-Seidel Graph

Biggs-Smith Graph

Brouwer-Haemers Graph

 > > $G≔\mathrm{BerlekampVanLintSeidelGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 243 vertices and 2673 edge\left(s\right)}}$ (9.1)
 > $\mathrm{IsStronglyRegular}\left(G,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{22}{,}{1}{,}{2}\right]$ (9.2)
 > > $G≔\mathrm{BrouwerHaemersGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 15: an undirected unweighted graph with 81 vertices and 810 edge\left(s\right)}}$ (9.3)
 > $\mathrm{IsStronglyRegular}\left(G,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{20}{,}{1}{,}{6}\right]$ (9.4)
 > $\mathrm{ChromaticNumber}\left(G\right)$
 ${7}$ (9.5)

De Bruijn Graph

Gewirtz Graph

Golomb Graph

Harr Graph

 > > $G≔\mathrm{GewirtzGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 16: an undirected unweighted graph with 56 vertices and 280 edge\left(s\right)}}$ (9.6)
 > $\mathrm{IsStronglyRegular}\left(G,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{10}{,}{0}{,}{2}\right]$ (9.7)
 > $\mathrm{ChromaticNumber}\left(G\right)$
 ${4}$ (9.8)



 > > Harborth Graph

Higman-Sims Graph

M22 Graph

McLaughlin Graph

 > > $G≔\mathrm{HigmanSimsGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 17: an undirected unweighted graph with 100 vertices and 1100 edge\left(s\right)}}$ (9.9)
 > $\mathrm{IsStronglyRegular}\left(G,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{22}{,}{0}{,}{6}\right]$ (9.10)
 > $\mathrm{ChromaticNumber}\left(G\right)$
 ${6}$ (9.11)
 > $G≔\mathrm{M22Graph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 18: an undirected unweighted graph with 77 vertices and 616 edge\left(s\right)}}$ (9.12)
 > $\mathrm{IsStronglyRegular}\left(G,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{16}{,}{0}{,}{4}\right]$ (9.13)
 > $\mathrm{ChromaticNumber}\left(G\right)$
 ${5}$ (9.14)
 > $G≔\mathrm{McLaughlinGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 275 vertices and 15400 edge\left(s\right)}}$ (9.15)
 > $\mathrm{IsStronglyRegular}\left(G,\mathrm{parameters}\right)$
 ${\mathrm{true}}{,}\left[{112}{,}{30}{,}{56}\right]$ (9.16)

Meredith Graph

Perkel Graph

Rooks Graph

Schläfli Graph

 > > $G≔\mathrm{PerkelGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 20: an undirected unweighted graph with 57 vertices and 171 edge\left(s\right)}}$ (9.17)
 > $\mathrm{IsRegular}\left(G\right)$
 ${\mathrm{true}}$ (9.18)
 > $\mathrm{ChromaticNumber}\left(G\right)$
 ${3}$ (9.19)
 > $\mathrm{DrawGraph}\left(\mathrm{RooksGraph}\left(2,3\right),\mathrm{labelstyle}=\mathrm{offset}\right)$ > $G≔\mathrm{SchlaefliGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 21: an undirected unweighted graph with 27 vertices and 216 edge\left(s\right)}}$ (9.20)
 > $\mathrm{IsStronglyRegular}\left(G,'\mathrm{parameters}'\right)$
 ${\mathrm{true}}{,}\left[{16}{,}{10}{,}{8}\right]$ (9.21)
 > $\mathrm{ChromaticNumber}\left(G\right)$
 ${9}$ (9.22)

Wells Graph

Wiener-Araya Graph





 > $\mathrm{DrawGraph}\left(\mathrm{WellsGraph}\left(\right),\mathrm{layout}=\mathrm{spring},\mathrm{size}=\left[250,250\right]\right)$ > $\mathrm{DrawGraph}\left(\mathrm{WienerArayaGraph}\left(\right),\mathrm{layout}=\mathrm{spring}\right)$ 