Graph Theory - Maple Help

 GraphTheory

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.

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.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{GraphComplement}\left(\mathrm{CompleteGraph}\left(3,4\right)\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 7 vertices and 9 edge\left(s\right)}}$ (1.1.1)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{FindClique}\left(G,3\right)$
 $\left[{1}{,}{2}{,}{3}\right]$ (1.1.2)
 > $\mathrm{FindClique}\left(G,4\right)$
 $\left[{4}{,}{5}{,}{6}{,}{7}\right]$ (1.1.3)

GraphIntersection

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

$\mathrm{Vertices}\left(G\right)=\mathrm{Vertices}\left(\mathrm{G1}\right)\cup \cdots \cup \mathrm{Vertices}\left(\mathrm{Gs}\right)$

$\mathrm{Edges}\left(G\right)=\mathrm{Edges}\left(\mathrm{G1}\right)\cap \cdots \cap \mathrm{Edges}\left(\mathrm{Gs}\right)$

 > $\mathrm{G1}≔\mathrm{Graph}\left(5,\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{1,4\right\},\left\{1,5\right\}\right\}\right)$
 ${\mathrm{G1}}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 5 vertices and 4 edge\left(s\right)}}$ (1.2.1)
 > $\mathrm{G2}≔\mathrm{Graph}\left(5,\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{1,4\right\},\left\{1,5\right\},\left\{2,3\right\},\left\{2,5\right\},\left\{3,4\right\},\left\{4,5\right\}\right\}\right)$
 ${\mathrm{G2}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 5 vertices and 8 edge\left(s\right)}}$ (1.2.2)
 > $\mathrm{DrawGraph}\left(\mathrm{G1}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{G2}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{GraphIntersection}\left(\mathrm{G1},\mathrm{G2}\right)\right)$



IndependencePolynomial

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

 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{Graph}\left(\left\{\left\{1,2\right\},\left\{2,3\right\},\left\{3,4\right\}\right\}\right)$
 ${P}{≔}{\mathrm{Graph 4: an undirected unweighted graph with 4 vertices and 3 edge\left(s\right)}}$ (1.3.1)
 > $\mathrm{IndependencePolynomial}\left(P,x\right)$
 ${3}{}{{x}}^{{2}}{+}{4}{}{x}{+}{1}$ (1.3.2)
 > $C≔\mathrm{CycleGraph}\left(5\right)$
 ${C}{≔}{\mathrm{Graph 5: an undirected unweighted graph with 5 vertices and 5 edge\left(s\right)}}$ (1.3.3)
 > $\mathrm{IndependencePolynomial}\left(C,x\right)$
 ${5}{}{{x}}^{{2}}{+}{5}{}{x}{+}{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.

 > $M≔\mathrm{MirzakhaniGraph}\left(\right)$
 ${M}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 63 vertices and 183 edge\left(s\right)}}$ (1.4.1)
 > $\mathrm{ChromaticNumber}\left(M,\mathrm{method}=\mathrm{sat}\right)$
 ${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

 > $\mathrm{DrawGraph}\left(\mathrm{DoyleGraph}\left(5\right),\mathrm{style}=\mathrm{spring}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{GearGraph}\left(8\right)\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{GrayGraph}\left(\right)\right)$
 >

Nauru Graph

Poussin Graph

Turan Graph

Tutte Graph

 >
 > $\mathrm{DrawGraph}\left(\mathrm{PoussinGraph}\left(\right),\mathrm{style}=\mathrm{spring}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{TuranGraph}\left(5,4\right),\mathrm{style}=\mathrm{spring}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{TutteGraph}\left(\right),\mathrm{style}=\mathrm{spring}\right)$