GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : System : Information : Updates : Maple 2018 : updates/Maple2018/GraphTheory

GraphTheory

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

• 

CliquePolynomial

• 

DistancePolynomial

• 

FindClique

• 

GraphIntersection

• 

IndependencePolynomial

• 

IsReachable

• 

Reachable

The ChromaticNumber function includes a new heuristic for graph coloring.

The SpecialGraphs subpackage also includes commands for eight new graphs.

 

Examples

New Special Graphs

Examples

FindClique

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

withGraphTheory:

GGraphComplementCompleteGraph3,4

GGraph 1: an undirected unweighted graph with 7 vertices and 9 edge(s)

(1.1.1)

DrawGraphG

FindCliqueG,3

1,2,3

(1.1.2)

FindCliqueG,4

4,5,6,7

(1.1.3)

GraphIntersection

GraphIntersection returns a graph G which is the intersection of the graphs G1,...,Gs, such that

VerticesG=VerticesG1VerticesGs

EdgesG=EdgesG1EdgesGs

G1Graph5,1,2,1,3,1,4,1,5

G1Graph 2: an undirected unweighted graph with 5 vertices and 4 edge(s)

(1.2.1)

G2Graph5,1,2,1,3,1,4,1,5,2,3,3,4,4,5,5,2

G2Graph 3: an undirected unweighted graph with 5 vertices and 8 edge(s)

(1.2.2)

DrawGraphG1

DrawGraphG2

DrawGraphGraphIntersectionG1,G2

IndependencePolynomial

IndependencePolynomial returns the independence polynomial for the graph G in the variable x.

withSpecialGraphs:

PGraph1,2,2,3,3,4

PGraph 4: an undirected unweighted graph with 4 vertices and 3 edge(s)

(1.3.1)

IndependencePolynomialP,x

3x2+4x+1

(1.3.2)

CCycleGraph5

CGraph 5: an undirected unweighted graph with 5 vertices and 5 edge(s)

(1.3.3)

IndependencePolynomialC,x

5x2+5x+1

(1.3.4)

ChromaticNumber

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.

MMirzakhaniGraph

MGraph 1: an undirected unweighted graph with 63 vertices and 183 edge(s)

(1.4.1)

ChromaticNumberM,method=sat

3

(1.4.2)

New Special Graphs

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

 

Doyle Graph

Gear Graph

Gray Graph

Mirzakhani Graph

DrawGraphDoyleGraph5,style=spring

DrawGraphGearGraph8

DrawGraphGrayGraph

DrawGraph MirzakhaniGraph,style=spring

Nauru Graph

Poussin Graph

Turan Graph

Tutte Graph

DrawGraph NauruGraph5

DrawGraphPoussinGraph,style=spring

DrawGraphTuranGraph5,4,style=spring

DrawGraphTutteGraph,style=spring