Graph Theory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : System : Information : Updates : Maple 2017 : updates/Maple2017/GraphTheory

Graph Theory

There have been several updates for the GraphTheory package in Maple 2017, including an update to the DrawGraph command to use a grayscale color scheme for graphs and the ability to control the graph drawing styles as well as several new commands.

 

Graph Drawing Options

Automorphism Groups

New Commands: CanonicalGraph, Eccentricity, Radius

Support for Digraph6 Format

New Special Graphs

Graph Drawing Options

By default, graphs in Maple 2017 are drawn using a grayscale color scheme.

You can now control many aspects of how a graph is drawn.  The colors, line weights, and font choices can be specified with the stylesheet option.  For details, see Graph Drawing Options.

withGraphTheory:

You can use the graph drawing settings from previous versions of Maple by specifying stylesheet="legacy".  Animations and 3-D graph renderings currently do not support the stylesheet option.

Automorphism Groups

AutomorphismGroup

The new GraphTheory[AutomorphismGroup] command computes and returns the group of automorphisms of a given graph, represented as a permutation group.

withGraphTheory: withGroupTheory: 

PG  SpecialGraphs:-PetersenGraph

PGGraph 1: an undirected unweighted graph with 10 vertices and 15 edge(s)

(2.1.1)

AG  AutomorphismGroupPG

AG1,23,56,97,8,2,53,47,108,9,3,94,87,10,4,75,68,10

(2.1.2)

After the automorphism group is computed, you can use GroupTheory commands to analyze the computed group. Here we use GroupTheory[IdentifySmallGroup] and GroupTheory[AreIsomorphic] to confirm the identity of the generated group and demonstrate it is, in fact, isomorphic to symmetric group on 5 elements:

IdentifySmallGroupAG

120,34

(2.1.3)

AreIsomorphicAG,SymmetricGroup5

true

(2.1.4)

DrawAutomorphism

The new GraphTheory[DrawAutomorphism] command enables visualizing the action of an automorphism of a graph as an animation.
When given a graph and a permutation corresponding to an automorphism, DrawAutomorphism produces an animation showing the action of each of the generators of the graph's automorphism group.

In the example below, we extract the generators of the computed automorphism group and create a permutation corresponding to a particular graph automorphism by multiplying all four generators. We then instruct DrawAutomorphismGroup to show this particular automorphism.g  GeneratorsAG

g1,23,56,97,8,2,53,47,108,9,3,94,87,10,4,75,68,10

(2.2.1)

p  g1 · g2· g3·g4

p1,6,7,3,24,9,5,10,8

(2.2.2)

If one provides only the graph, DrawAutomorphism shows an animation of the automorphisms corresponding to each of the generators of the automorphism group, as returned by AutomorphismGroup.

DrawAutomorphismPG

New Commands: CanonicalGraph, Eccentricity, Radius

The new commands GraphTheory[CanonicalGraph], GraphTheory[Eccentricity], and GraphTheory[Radius] enable the construction of new graph normal forms and the computation of quantities from graphs.

The CanonicalGraph command constructs a version of the input graph in which the vertices have been reordered such that the resulting graph is in a canonical form. The output is canonical in the sense that any two graphs G and H are isomorphic if and only if AdjacencyMatrixCanonicalGraphG =AdjacencyMatrixCanonicalGraphH. In this example, the Foster cage graph and the Meringer graph serve as examples of graphs which are both cage graphs with the same number of vertices and edges, but are nevertheless not isomorphic.

 CanonicalGraphSpecialGraphs:-FosterCageGraph

Graph 2: an undirected unweighted graph with 30 vertices and 75 edge(s)

(3.1)

CanonicalGraphSpecialGraphs:-MeringerGraph

Graph 3: an undirected unweighted graph with 30 vertices and 75 edge(s)

(3.2)

EqualEntries AdjacencyMatrix, AdjacencyMatrix 

false

(3.3)

The new command Eccentricity computes the eccentricity of the graph at a specified vertex or, if not specified, computes the list of eccentricities at each vertex. The eccentricity of a vertex v is the maximum graph distance between v and any other vertex in the graph.

Eccentricity SpecialGraphs:-HoffmanGraph 

3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4

(3.4)

The maximum eccentricity over the entire graph is known as the graph diameter and can be computed with GraphTheory[Diameter] (also available in previous Maple versions).Diameter SpecialGraphs:-HoffmanGraph

4

(3.5)

The minimum eccentricity over the entire graph is known as the graph radius, and it can be computed directly using the new command Radius:

Radius SpecialGraphs:-HoffmanGraph

3

(3.6)

Support for Digraph6 Format

The general-purpose commands Import and Export as well as the GraphTheory commands GraphTheory[ImportGraph], GraphTheory[ExportGraph], and GraphTheory[ConvertGraph] now support the Digraph6 graph format.  The Digraph6 format is a concise text-based format for serializing a directed graph.

For more information on supported graph-theoretic formats in Maple, see Formats.

Digraph6 Format

GraphTheory:-DrawGraphImportexample/dgex.d6,base=datadir

New Special Graphs

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

 

Book Graph

Chvatal Graph

Folkman Graph

DrawGraph SpecialGraphs:-BookGraph5

DrawGraph SpecialGraphs:-ChvatalGraph

DrawGraph SpecialGraphs:-FolkmanGraph,style=spring

 Franklin Graph

Frucht Graph

Hoffman Graph

DrawGraph SpecialGraphs:-FranklinGraph5,style=spring

DrawGraphSpecialGraphs:-FruchtGraph

DrawGraph SpecialGraphs:-HoffmanGraph,style=spring