Graph theory package

The graph theory package in Maple (GraphTheory) at first looks ominous and daunting with 225 functions and three sub-packages. We'll look at some of the more common functions and features here.

There are two functions in the GraphTheory package used to create graphs: Graph(...) is used to create undirected graphs, and Digraph(...) is used to create directed graphs. With this package, is is probably best to include the package while using it.

The vertices are passed as the first argument, and each vertex may be identified by either a symbol or an indexed name, an integer, or a string. In general, of course, it is likely best if you choose one and only one format per graph. The identifiers of the vertices are passed as a list to either the Graph([...], ...) or Digraph([...], ...) function. As a shorthand, a positive integer n is equivalent to the first argument [1, 2, 3, ..., n].

Recommendation: If you intend to draw the graph, use one- or two-character strings but place all these into an array first so that you can easily switch between integers and the strings:

[> # The list ["A", ..., "Z"]:
[> vA := [seq( StringTools['Char']( k ), k = 65..90 )]:
[> #  - Use va := [seq( ..., k = 97..122 )]: for ["a", ..., "z"]

The following creates all possible pairs ["AA", "AB", ..., "AZ", "BA", ..., "YZ", "ZA", ..., "ZZ"] (676):

[> vAA := [seq( seq(
    cat( StringTools['Char']( k1 ), StringTools['Char']( k2 ) ),
    k2 = 65..90
), k1 = 65..90 )]:

The following creates all possible pairs ["A0", "A1", ..., "A9", "B0", ..., "Y9", "Z0", ..., "Z9"] (260):

[> vA0 := [seq( seq(
    cat( StringTools['Char']( k1 ), k2 ), k2 = 0..9
), k1 = 65..90 )]:

We will look at working with

undirected graphs,
directed graphs, and
weighted graphs (directed and undirected).

Creating and working with an undirected graph

You can now use these lists to create an undirected graph with a specific number of nodes; for example, this one has ten vertices labelled "J" through "T":

[> with( GraphTheory ):
[> UG := Graph( vA[1..10] ):

In an undirected graph, Maple refers to connections between vertices to be edges, while connections in a directed graph are arcs.

You can either add edges using either a second argument of a set of sets of pairs representing edges, or you can subsequently add edges to an undirected graph by calling the AddEdge(...) function. The following two are equivalent: either creating the graph with the edges, or adding the edges later:

[> UG := Graph( vA[1..10], {{"A", "B"}, {"D", "G"}} ):

[> UG := Graph( vA[1..10] ):
[> AddEdge( UG, {{"A", "B"}, {"D", "G"}} ):
[> Edges( UG );

${{"A", "B"}, {"D", "G"}}$

If you are only adding one edge, you can just pass a single set with the two vertices. If the set contains only a single vertex, it is interpreted as a self-loop. The following creates a graph and adds 20 random edges:

[> UG := Graph( vA[1..16] ):
[> to 20 do
    vertex1 := vA[mod1( rand(), 16 )];
    vertex2 := vA[mod1( rand(), 16 )];
    AddEdge( UG, {vertex1, vertex2} );
end do:

If you are only adding one edge, you can just pass a single set with the set of two vertices as a second argument.

You can draw this graph:

[> DrawGraph( UG );

Instead of adding an edge one at a time, it is also possible to add a trail, so if you call AddEdge( UG, Trail( "A", "C", "E", "D", "G" ) ), this would add edges from "A" to "C", "C" to "E", and so on.

The HasEdge(...) function returns true if the edge has an edge and false otherwise. You can delete one or more edges by using the DeleteEdge(...) function, but one must be careful not to try to delete an edge that is not in the graph, as this returns an error. Here we take the previous graph and trying to delete fifty randomly deleted edges:

[> to 50 do
    vertex1 := vA[mod1( rand(), 16 )];
    vertex2 := vA[mod1( rand(), 16 )];
    if HasEdge( UG, {vertex1, vertex2} ) then
        DeleteEdge( UG, {vertex1, vertex2} );
    end if;
end do:
[> DrawGraph( UG );

Note that there are binomial( 16, 2 ) + 16 different edges (including self-loops), so the probability of a randomly generated edge being in this graph is only about one in seven, hence not that many edges were actually deleted.

Creating and working with a directed graph

You can also use these lists to create a direct graph with a specific number of nodes; for example, this one has forty-two vertices labelled "AA" through "BP", and adds up to 100 randomly generated arcs:

[> DG := Digraph( vAA[1..42] ):
[> to 100 do
    vertex1 := vA[mod1( rand(), 16 )];
    vertex2 := vA[mod1( rand(), 16 )];
    AddArc( DG, [vertex1, vertex2] );
end do:

In a directed graph, Maple refers to connections between vertices to be arcs, while connections in an undirected graph are edges.

[> DrawGraph( DG );

Like undirected graphs, you can check if a directed graph has an edge using HasArc(...) and delete arcs using DeleteArc(...).

Creating and working with weighted graph

An edge {"A0", "B3"} can be given a weight by including the weight in a list: [{"A0", "B3"}, 3.2] where the weight is any numeric value. Similarly, [["A0", "B3"], 3.2] is used to designate the weight of the corresponding arc.

For example, the following is a weighted undirected graph:

[> WG := Graph( vA0[1..12], {[{"A0", "A4"}, 3.2],
                          [{"A2", "A7"}, 0.9],
                          [{"A2", "B1"}, 8.4],
                          [{"A3", "A9"}, 7.5],
                          [{"A4", "B1"}, 1.6],
                          [{"A5", "A7"}, 9.1],
                          [{"A6", "A9"}, 6.3],
                          [{"A7", "A6"}, 4.0],
                          [{"B0", "A1"}, 5.7],
                          [{"A8", "A2"}, 2.8],
                          [{"B0", "A2"}, 5.1]}, 'weighted' );
):
end do:
[> DrawGraph( WG );

To get or set the weight of an edge, you can use the GetEdgeWeight(...) and SetEdgeWeight(...). Unfortunately, there is no corresponding GetArcWeight(...) or SetArcWeight(...). You can extract the adjacency matrix using the WeightMatrix( WG ) function.

[> WeightMatrix( WG );

$\begin{pmatrix} 0 & 0 & 0 & 0 & 3.2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 5.7 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.9 & 2.8 & 0 & 5.1 & 8.4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 7.5 & 0 & 0 \\ 3.2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1.6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9.1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4.0 & 0 & 6.3 & 0 & 0 \\ 0 & 0 & 0.9 & 0 & 0 & 9.1 & 4.0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2.8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 7.5 & 0 & 0 & 6.3 & 0 & 0 & 0 & 0 & 0 \\ 0 & 5.7 & 5.1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 8.4 & 0 & 1.6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

Constructors

There are many common graphs that may be constructed without specifying each edge, and there are operations that may take one or more existing graphs and create a new graph. Some of these are listed here:

CartesianProduct( G1, G2, ... ): Create a Cartesian product of the vertices, and apply specific rules to determine if the product graph has edges between the product vertices.
GraphUnion( G1, G2, ... ): Create a graph that has a union of all the vertices in the argument graphs and the union of all edges.
DisjointUnion( G1, G2, ... ): Create a graph that is the union of all of the argument graphs where all vertices in the argument graphs are assumed to be different.
GraphIntersection( G1, G2, ... ): Create a graph that is the union of all the vertices in the argument graphs, but where the only edges includd are those that appear in all of the argument graphs.
CompleteGraph( vertices ): Similar to the Graph(...) constructor, but immidiately add all possible non-self-looping edges.
ContractSubgraph( G, vertices ) or CompleteGraph( G, SG ): Return a graph that has all the vertices specified in the list or set of vertices, or a given sub-graph into a single vertex.
CycleGraph( vertices ): Create a graph with the given vertices and have that list of vertices define a sequence of edges.
FundamentalCycle( G ): If G has exactly one cycle, then this function returns a subgraph with those vertices and edges that make up that cycle.
GraphComplement( G ): Returns a graph that has all the same vertices as G, but the edges of which are all those that are not in the graph G.
GraphNormal( G ): An exponential run-time algorithm that rearranges the order of the vertices so that the most number of edges appear as early as possible in the adjacency matrix.
LineGraph( G ): Create a new graph where each edge in G is represented by a vertex in the new graph, and two vertices in this new graph are connected by an edge if both corresponding edges are adjacent in G.
IdentifyGraph( G ): Determine if there are any known graphs that are isomorphic to the given graph, and return the commands and arguments that would generate the given graph.
GraphPower( G, n ): Returns a graph with all the vertices of G and includes an edge between two vertices if there is a path no longer than $n$ between the two vertices in G.
GraphComplement( G, H ): Returns a graph that takes the disjoint union of the graphs G and H, but then also addes edges from each vertex in G to each vertex in H and vice versa.

Graph operations

There are three sub-packages for generating specialized named graphs, random graphs, and for creating graphs based on geometric data. Commands exist to determine if a graph has specific properties, and other commands implement algorithms that traverse graphs, such as Dijkstra's algorithm. There is just so much to discuss... Enjoy.

Graph derived from geometric data

The GraphTheory[GeometricGraphs] subpackage includes a number of commands that return graphs based on points in $\textbf{R}^n$. The first argument is either a list of $m$ lists each of $n$ entries, or it is an $m \times n$ matrix. In either case, the first index identifies the points, while the second identifies the coordinate within the point.

The algorithms are as follows:

GeometricMinimumSpanningTree( points, ... ): The minimum spanning tree with respect to the specified norm. The result will be connected.
EuclideanMinimumSpanningTree( points, ... ): A special case of the previous command where the 2- or Euclidean norm is used. The result will be connected.
NearestNeighborGraph( points, ... ): Each vertex is connected to its nearest neighbor with either a directed arc or undirected edge, as specified. The result need not be connected.
FarthestNeighborGraph( points, ... ): Each vertex is connected to its furthest neighbor with either a directed arc or undirected edge, as specified. The result will be connected.
DelaunayGraph( points, ... ): Create a triangulation that maximizes the minimum angle in each of the triangles according to the Delaunay triangulation algorithm. The result will be connected.
UrquhartGraph( points, ... ): Take the Delaunay triangulation and remove the longest edge from each triangle. See Urquhart graph algorithm. The result will be connected.
GabrielGraph( points, ... ): Each vertex is connected to any other vertex so long as the ball with radius equal to the distance between those two points that contains those two points on the surface contains no other vertices. See Gabriel graph. The result will be connected.
RelativeNeighborhoodGraph( points, ... ): Each vertex is connected to any other vertex so long as there is no third vertex that is closer to both vertices than the distance between the two. See relative neighborhood graph. The result will be connected.
SphereOfInfluenceGraph( points, ... ): Place a ball around each point with radius equal to the distance to the nearest neighbor. Two vertices are connected if the intersection of their two balls contains at least one vertex. The result need not be connected.
UnitDiskGraph( points, threshold, ... ): Each vertex is connected to each other vertex that is within the given threshold distance. The result need not be connected.
VisibilityGraph( points, ... ): The points are assumed to define the boundary of a polygon, and to this polygon, any edges that lie entirely within the polygon are also added. The result will be connected.