Maple 2018 enhances the GraphTheory package with new functions, including:
The ChromaticNumber function includes a new heuristic for graph coloring.
The SpecialGraphs subpackage also includes commands for eight new graphs.
New Special Graphs
FindClique returns a list of vertices which comprise a clique in the graph G. The optional parameter size specifies a size for the clique.
G ≔ GraphComplement⁡CompleteGraph⁡3,4
G≔Graph 1: an undirected unweighted graph with 7 vertices and 9 edge(s)
GraphIntersection returns a graph G which is the intersection of the graphs G1,...,Gs, such that
G1 ≔ Graph⁡5,1,2,1,3,1,4,1,5
G1≔Graph 2: an undirected unweighted graph with 5 vertices and 4 edge(s)
G2 ≔ Graph⁡5,1,2,1,3,1,4,1,5,2,3,3,4,4,5,5,2
G2≔Graph 3: an undirected unweighted graph with 5 vertices and 8 edge(s)
IndependencePolynomial returns the independence polynomial for the graph G in the variable x.
P ≔ Graph⁡1,2,2,3,3,4
P≔Graph 4: an undirected unweighted graph with 4 vertices and 3 edge(s)
C ≔ CycleGraph⁡5
C≔Graph 5: an undirected unweighted graph with 5 vertices and 5 edge(s)
ChromaticNumber returns the minimum number of colours necessary to colour the vertices of a graph so that no adjacent vertices are coloured the same. Maple 2018 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=fastest, runs the two methods optimal and sat in parallel and returns the result of whichever method finishes first.
M ≔ MirzakhaniGraph⁡
M≔Graph 1: an undirected unweighted graph with 63 vertices and 183 edge(s)
The SpecialGraphs subpackage now includes built-in commands to generate the following special graphs:
Download Help Document