GraphTheory - New Features in Maple 2019 - Maplesoft

What's New in Maple 2019

GraphTheory

Maple 2019 enhances the GraphTheory package with new functions, including: 



  • FindVertexCover , MinimumVertexCover
  • FindHamiltonianCycle , FindHamiltonianPath
  • GreedyClique , GreedyIndependentSet
  • IsStronglyRegular
  • IsTriangleFree
  • TransitiveReduction
  • BarabasiAlbertGraph
  • WattsStrogatzGraph
 

The SpecialGraphs subpackage also includes commands for eleven new graphs and many new options for customizing the visualizations of graphs have been added to the DrawGraph command. 

 

Examples 

FindVertexCover 

FindVertexCover returns a list of vertices which comprise a vertex cover in the graph G. The optional parameter size specifies a size for the clique. 

> with(GraphTheory); -1
 

> G := CompleteGraph(3, 4)
 

Typesetting:-mprintslash([G := `Graph 1: an undirected unweighted graph with 7 vertices and 12 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7], Array(%id = 18446884105546647662), `GR...
 

> DrawGraph(G)
 

Plot_2d
 

> FindVertexCover(G, 3)
 

[1, 2, 3]
 

> FindVertexCover(G, 4)
 

[4, 5, 6, 7]
 

MaximumClique 

MaximumClique returns a clique of the largest possible size in the specified graph. Maple 2019 includes a new heuristic, method=sat, which transforms the graph into an instance of the Boolean satisfiability problem, which it then solves using the Logic[Satisfy] command.
The new default heuristic,
method=hybrid, runs the two methods optimal and sat in parallel and returns the result of whichever method finishes first. 

> M := SpecialGraphs:-MirzakhaniGraph()
 

Typesetting:-mprintslash([M := `Graph 2: an undirected unweighted graph with 63 vertices and 183 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,...
 

> MaximumClique(M, method = sat)
 

[61, 62, 63]
 

WattsStrogatzGraph 

The WattsStrogatzGraph command permits the generation of random graphs with the Watts-Strogatz model, which produces graphs with a number of desirable real-world properties such as short average path lengths and high clustering.
 

> WSG := RandomGraphs:-WattsStrogatzGraph(20, .2)
 

Typesetting:-mprintslash([WSG := `Graph 3: an undirected unweighted graph with 20 vertices and 40 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17...
 

> DrawGraph(WSG, style = spring)
 

Plot_2d
 

 

New Special Graphs 

The SpecialGraphs subpackage now includes built-in commands to generate the following special graphs or graph families: 

> with(SpecialGraphs); -1
 

Brinkmann Graph 

Cameron Graph 

Circulant Graph 

Dürer Graph 

> DrawGraph(BrinkmannGraph(), style = spring, size = [250, 250])
DrawGraph(BrinkmannGraph(), style = spring, size = [250, 250])
 

Plot_2d
 

> CG := CameronGraph()
 

Typesetting:-mprintslash([CG := `Graph 4: an undirected unweighted graph with 231 vertices and 3465 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
Typesetting:-mprintslash([CG := `Graph 4: an undirected unweighted graph with 231 vertices and 3465 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
Typesetting:-mprintslash([CG := `Graph 4: an undirected unweighted graph with 231 vertices and 3465 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
Typesetting:-mprintslash([CG := `Graph 4: an undirected unweighted graph with 231 vertices and 3465 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
 

> NumberOfVertices(CG)
 

231
 

> NumberOfEdges(CG)
 

3465
 

> DrawGraph(CirculantGraph(7, 3), size = [250, 250])
DrawGraph(CirculantGraph(7, 3), size = [250, 250])
 

Plot_2d
 

> DrawGraph(DuererGraph(), size = [250, 250])
DrawGraph(DuererGraph(), size = [250, 250])
 

Plot_2d
 

Friendship Graph 

Hall-Janko Graph 

Johnson Graph 

Livingstone Graph 

> DrawGraph(FriendshipGraph(5), size = [250, 250])
DrawGraph(FriendshipGraph(5), size = [250, 250])
 

Plot_2d
 

> HJG := HallJankoGraph()
 

Typesetting:-mprintslash([HJG := `Graph 5: an undirected unweighted graph with 100 vertices and 1800 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,...
Typesetting:-mprintslash([HJG := `Graph 5: an undirected unweighted graph with 100 vertices and 1800 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,...
Typesetting:-mprintslash([HJG := `Graph 5: an undirected unweighted graph with 100 vertices and 1800 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,...
Typesetting:-mprintslash([HJG := `Graph 5: an undirected unweighted graph with 100 vertices and 1800 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,...
 

> NumberOfVertices(HJG); 1
 

100
 

> NumberOfEdges(HJG); 1
 

1800
 

> DrawGraph(JohnsonGraph(4, 2), size = [250, 250])
DrawGraph(JohnsonGraph(4, 2), size = [250, 250])
 

Plot_2d
 

> LG := LivingstoneGraph()
 

Typesetting:-mprintslash([LG := `Graph 6: an undirected unweighted graph with 266 vertices and 198 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1...
Typesetting:-mprintslash([LG := `Graph 6: an undirected unweighted graph with 266 vertices and 198 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1...
Typesetting:-mprintslash([LG := `Graph 6: an undirected unweighted graph with 266 vertices and 198 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1...
Typesetting:-mprintslash([LG := `Graph 6: an undirected unweighted graph with 266 vertices and 198 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1...
 

> Girth(LG)
 

5
 

Suzuki Graph 

Sylvester Graph 

Tietze Graph 

 

> SG := SuzukiGraph()
 

Typesetting:-mprintslash([SG := `Graph 7: an undirected unweighted graph with 1782 vertices and 370656 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1...
Typesetting:-mprintslash([SG := `Graph 7: an undirected unweighted graph with 1782 vertices and 370656 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1...
Typesetting:-mprintslash([SG := `Graph 7: an undirected unweighted graph with 1782 vertices and 370656 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1...
Typesetting:-mprintslash([SG := `Graph 7: an undirected unweighted graph with 1782 vertices and 370656 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1...
 

> NumberOfEdges(SG)
 

370656
 

> DrawGraph(SylvesterGraph(), style = spring, showlabels = false, size = [250, 250])
DrawGraph(SylvesterGraph(), style = spring, showlabels = false, size = [250, 250])
DrawGraph(SylvesterGraph(), style = spring, showlabels = false, size = [250, 250])
DrawGraph(SylvesterGraph(), style = spring, showlabels = false, size = [250, 250])
 

Plot_2d
 

> DrawGraph(TietzeGraph(), size = [250, 250])
DrawGraph(TietzeGraph(), size = [250, 250])
 

Plot_2d
 

 

New Visualization Options 

The DrawGraph command and various graph highlighting commands have been enhanced with even more new ways to customize graph display. Some of the defaults have changed so that the vertex shape will generally be closer to the size of the vertex label, vertex borders will not overlap, and the size option passed to DrawGraph will be used to make graphs look better at sizes different than the default. As well, the arrows on directed edges are now draw with a more typical solid triangle shape with new stylesheet options to customize the arrow positions and size. 

> GV1 := Graph({[[1, 2], 1], [[2, 3], 2], [[3, 4], 3], [[4, 5], 4], [[5, 1], 5]}); 1
 

Typesetting:-mprintslash([GV1 := `Graph 8: a directed weighted graph with 5 vertices and 5 arc(s)`], [GRAPHLN(directed, weighted, [1, 2, 3, 4, 5], Array(%id = 18446884105523144454), `GRAPHLN/table/34`...
 

> DrawGraph(GV1, stylesheet = [edgethickness = 3, vertexcolor =
 

Plot_2d
 

A new vertex shape option is now available as well, the shape can be any string understood by the new command plottools:-polygonbyname. 

> DrawGraph(GV1, stylesheet = [vertexshape =
 

Plot_2d
 

> HighlightVertex(GV1, 2, stylesheet = [shape =
 

Plot_2d
 

There is a new option to control the amount of padding (measured in font points) around vertex labels.  This is useful if the automatically selected size of the vertex shape is too large or too small. 

> HighlightVertex(GV1, 2, stylesheet = [shape =
 

Plot_2d
 

There is a new option to set the line style of graph edges.  Any linestyle from plot/options is supported. 

> HighlightEdges(GV1, [1, 2], stylesheet = [linestyle =
 

Plot_2d
 

In cases where the graph has many vertices, labels are turned off by default but plot annotations are added so that you can see the labels when you hover the mouse pointer over a vertex. 

> TV1 := RandomGraphs:-RandomTree(100); 1; DrawGraph(TV1)
 

 

Typesetting:-mprintslash([TV1 := `Graph 9: an undirected unweighted graph with 100 vertices and 99 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1...
Plot_2d
 

The DrawGraph tree style can now be used on graphs that are not trees. This is implemented by choosing a vertex layout based on the SpanningTree starting at a specified root. 

> GV2 := CompleteGraph(5, 2); 1; DrawGraph(GV2, style = tree, root = 3)
 

 

Typesetting:-mprintslash([GV2 := `Graph 16: an undirected unweighted graph with 7 vertices and 10 edge(s)`], [GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7], Array(%id = 18446884105546618270), ...
Plot_2d
 



Prêt(e) pour l'étape suivante ?

Discutez aujourd'hui avec nos spécialistes produits pour évaluation gratuite de Maple.

*Ce programme d'évaluation n'est proposé actuellement ni aux étudiants ni aux particuliers.