Graph Theory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : System : Information : Updates : Maple 2016 : updates/Maple2016/GraphTheory

Graph Theory

There have been several updates for the GraphTheory package in Maple 2016, including an update to the DrawGraph command such that the display for vertices uses round rather than rectangular background shapes. Maple 2016 also introduces nine new commands:

• 

CliqueCover

• 

CliqueCoverNumber

• 

GlobalClusteringCoefficient

• 

IntervalGraph

• 

IsArborescence

• 

LocalClusteringCoefficient

• 

MaximumMatching

• 

ReverseGraph

• 

TransitiveClosure

 

Example: Clustering Coefficients

In analyzing a connected graph, particularly one arising naturally from empirical data, it is often worthwhile to know the degree to which nodes cluster together. Clustering coefficients aim to measure both the local clustering within a graph and the overall clustering across the graph.

 

withGraphTheory: withRandomGraphs:

G  Graph6,1,3,1,6,2,6,2,4,3,6,4,6,4,5,5,6;

Graph 1: an undirected unweighted graph with 6 vertices and 8 edge(s)

(1)

The LocalClusteringCoefficient command computes a number between 0 and 1 measuring how close the neighborhood of a particular vertex is to being a clique. You can compute the coefficient for a specified vertex:

LocalClusteringCoefficientG,4

23

(2)

Alternatively you can compute the list of all coefficients for the graph in vertex order:

LocalClusteringCoefficientG

111231310

(3)

The GlobalClusteringCoefficient command computes a measure of how close G is to being a complete graph.

GlobalClusteringCoefficientG

917

(4)

An alternate definition of the global clustering coefficient is the mean of all local clustering coefficients.

GlobalClusteringCoefficientG,method=Mean

149180

(5)

Clustering coefficients can be also be computed for larger graphs.
Here we illustrate that invoking RandomGraph with probability p generates a graph with mean clustering coefficient approaching p.

HRandomGraph500,0.2

Graph 2: an undirected unweighted graph with 500 vertices and 24897 edge(s)

(6)

dataplotLocalClusteringCoefficientH,histogram

evalfGlobalClusteringCoefficientH,method=Mean

0.2001778096

(7)