The GraphTheory Package
This worksheet demonstrates some features of the GraphTheory package. It is presented in a tutorial format.
restart:withGraphTheory:
Creating Graphs
The main command for creating an undirected graph is the Graph command. For a directed graph the main command is the Digraph command. For both commands, you may specify the vertices in an ordered list. The vertices may be integers, symbols, or strings. By using strings, you can affix any text that you want for the vertex labels.
G:=Graph⁡a,b,c
G≔Graph 1: an undirected unweighted graph with 3 vertices and 0 edge(s)
Vertices⁡G
a,b,c
T:=Digraph⁡1,2,3
T≔Graph 2: a directed unweighted graph with 3 vertices and 0 arc(s)
Vertices⁡T
1,2,3
H:=Graph⁡0:0,0:1,1:0,1:1
H≔Graph 3: an undirected unweighted graph with 4 vertices and 0 edge(s)
Vertices⁡H
0:0,0:1,1:0,1:1
You may specify the number of vertices, n, in which case they are labeled 1,2,..., n.
G:=Graph⁡4
G≔Graph 4: an undirected unweighted graph with 4 vertices and 0 edge(s)
1,2,3,4
Inserting edges
You may insert edges into an undirected graph one at a time using the AddEdge command. Each edge should be input as a set of two vertices.
You can also specify more than one edge at a time in a set.
G≔Graph 5: an undirected unweighted graph with 4 vertices and 0 edge(s)
AddEdge⁡G,1,2;AddEdgeG,2,3,3,4
Graph 5: an undirected unweighted graph with 4 vertices and 1 edge(s)
Graph 5: an undirected unweighted graph with 4 vertices and 3 edge(s)
Edges⁡G
1,2,2,3,3,4
For a directed graph, use the AddArc command and input the edges as lists of vertices.
H:=Digraph⁡4
H≔Graph 6: a directed unweighted graph with 4 vertices and 0 arc(s)
AddArc⁡H,1,2,2,3,3,4
Graph 6: a directed unweighted graph with 4 vertices and 3 arc(s)
Edges⁡H
Using a set of edges
You may create an undirected graph with given edges by passing them in as a set where each edge is itself a set of two vertices. If the vertices are not specified explicitly, the vertices will be taken to be all vertices appearing in the set of edges. Thus, the previous graph G, which is a simple path, can be created by
G:=Graph⁡1,2,2,3,3,4
G≔Graph 7: an undirected unweighted graph with 4 vertices and 3 edge(s)
AdjacencyMatrix⁡G
0100101001010010
Similarly, the above previous directed graph H, which is a directed path, can be created by
H:=Digraph⁡1,2,2,3,3,4
H≔Graph 8: a directed unweighted graph with 4 vertices and 3 arc(s)
AdjacencyMatrix⁡H
0100001000010000
Using an adjacency matrix
The above graphs G and H can also be created from the adjacency matrix. If the vertices are not explicitly given in a list, then the vertex labels are taken to be integers 1,2,...,n where n is the dimension of the adjacency matrix.
A:=0100101001010010
A≔0100101001010010
G:=Graph⁡A
G≔Graph 9: an undirected unweighted graph with 4 vertices and 3 edge(s)
B:=0100001000010000
B≔0100001000010000
H:=Digraph⁡a,b,c,d,B
H≔Graph 10: a directed unweighted graph with 4 vertices and 3 arc(s)
a,b,c,d
a,b,b,c,c,d
Using a list of neighbors
If G has n vertices, the input is a list of n lists of vertices.
L:=2,1,3,2,4,3
L≔2,1,3,2,4,3
G:=Graph⁡L
G≔Graph 11: an undirected unweighted graph with 4 vertices and 3 edge(s)
Neighbors⁡G
2,1,3,2,4,3
For a directed graph, the list of neighbors need not be symmetric. Here is a directed cycle, i.e., the directed edges 1 to 2, 2 to 3, 3 to 4 and 4 to 1. This list corresponds to the list of "departures" of the graph.
L:=2,3,4,1
L≔2,3,4,1
H:=Digraph⁡L
H≔Graph 12: a directed unweighted graph with 4 vertices and 4 arc(s)
Neighbors⁡H
2,4,1,3,2,4,1,3
Arrivals⁡H
4,1,2,3
Departures⁡H
2,3,4,1
Using trails
This is a convenient shorthand. The trail 1,2,3,4 represents the edges 1 to 2 to 3 to 4.
T:=Trail⁡1,2,3,4,1
T≔Trail⁡1,2,3,4,1
G:=Graph⁡T
G≔Graph 13: an undirected unweighted graph with 4 vertices and 4 edge(s)
1,2,1,4,2,3,3,4
H:=Digraph⁡Trail⁡a,b,c,d,c,b,a
H≔Graph 14: a directed unweighted graph with 4 vertices and 6 arc(s)
a,b,b,a,b,c,c,b,c,d,d,c
Weighted edges
To create a weighted graph, use the weighted option.
G:=Graph⁡5,weighted
G≔Graph 15: an undirected weighted graph with 5 vertices and 0 edge(s)
An undirected edge (u,v) of weight w is input in the form [{u,v},w]. For a directed edge from u to v with weight w, use [[u,v],w] instead.
AddEdge⁡G,1,2,2.3;AddEdgeG,3,4,4.5
Graph 15: an undirected weighted graph with 5 vertices and 1 edge(s)
Graph 15: an undirected weighted graph with 5 vertices and 2 edge(s)
0100010000000100010000000
W:=WeightMatrix⁡G
W≔02.30002.300000004.50004.50000000
The same graph can be created directly with
G:=Graph⁡5,1,2,2.3,3,4,4.5
G≔Graph 16: an undirected weighted graph with 5 vertices and 2 edge(s)
An edge weight can be 0.
AddEdge⁡G,2,3,0.0
Graph 16: an undirected weighted graph with 5 vertices and 3 edge(s)
0100010100010100010000000
WeightMatrix⁡G
02.30002.300.0000.04.50004.50000000
Paths, cycles, and complete graphs
Paths and cycles can be created by using a trail. There are also two primitives for creating these because they are heavily used. There is also a primitive for creating complete graphs.
P:=PathGraph⁡4
P≔Graph 17: an undirected unweighted graph with 4 vertices and 3 edge(s)
Edges⁡P
C:=CycleGraph⁡4
C≔Graph 18: an undirected unweighted graph with 4 vertices and 4 edge(s)
Edges⁡C
K4:=CompleteGraph⁡4
K4≔Graph 19: an undirected unweighted graph with 4 vertices and 6 edge(s)
Edges⁡K4
1,2,1,3,1,4,2,3,2,4,3,4
IsPlanar⁡K4
true
K33:=CompleteGraph⁡3,3
K33≔Graph 20: an undirected unweighted graph with 6 vertices and 9 edge(s)
IsPlanar⁡K33
false
Drawing Graphs
Here we just show some examples which illustrate the main options. Further examples are given under the section "Special Graphs".
G:=Graph⁡9,1,2,2,3,3,1,6,7,7,8
G≔Graph 21: an undirected unweighted graph with 9 vertices and 5 edge(s)
DrawGraph⁡G
H:=Digraph⁡5,1,2,2,3,3,4,2,5
H≔Graph 22: a directed unweighted graph with 5 vertices and 4 arc(s)
DrawGraph⁡H
DrawGraph⁡H,style=circle
If you dislike the placement of the vertices, you can specify them as follows.
SetVertexPositions⁡H,0,0,0.5,0,1.0,0,1.5,0,0.5,1
P:=SpecialGraphs:-PetersenGraph⁡
P≔Graph 23: an undirected unweighted graph with 10 vertices and 15 edge(s)
The Petersen graph is very well known in graph theory. It is a non-planar graph. This is one of the standard drawings.
DrawGraph⁡P
The placement of the vertices is stored in the graph data structure.
GetVertexPositions⁡G
1.700000000,1.0,2.133012702,0.2499999999,1.266987298,0.2500000000,0.4999999999,1.0,0.9330127020,0.2499999999,2.4,1.,2.4,0.5000000000,2.4,0.,0.06698729810,0.2500000000
The "spring" method for drawing graphs will find other "symmetric" drawings of the Petersen graph. Try executing this a few times.
DrawGraph⁡P,style=spring,redraw
The spring method works in 3-D
DrawGraph⁡P,style=spring,dimension=3
The spring method will work for moderately large graphs (graphs up to 1000 vertices).
S:=SpecialGraphs:-SoccerBallGraph⁡
S≔Graph 24: an undirected unweighted graph with 60 vertices and 90 edge(s)
DrawGraph⁡S,style=spring
For large weighted graphs the edge weights and edge labels may "clutter" the graph. You can turn these off.
G:=Graph⁡a,b,2,b,c,3,c,d,4,d,b,5
G≔Graph 25: an undirected weighted graph with 4 vertices and 4 edge(s)
DrawGraph⁡G,showweights=false
DrawGraphG,showlabels=false
Exporting and Importing Graphs
The commands ExportGraph and ImportGraph allow you to output one or more graphs to a file or read graphs from a file. Supported formats are `dimacs`, `dimacs_relaxed`, `combinatorica`, `edges`, `metapost`, `dot`, `graphml`, `gxl`, `leda`, `pajek`, `tgf`, `sparse6`, and `graph6`.
Graph Properties
There are lots of graph commands. Here we illustrate basic commands and how to accomplish various tasks.
Undirected graphs
G:=Graph⁡1,2,2,3,3,1,3,4,4,5,5,6
G≔Graph 26: an undirected unweighted graph with 6 vertices and 6 edge(s)
IsConnected⁡G
ConnectedComponents⁡G
1,2,3,4,5,6
IsBiconnected⁡G
BiconnectedComponents⁡G
5,6,4,5,3,4,1,2,3
011000101000110100001010000101000010
Distance⁡G,1,6
4
AllPairsDistance⁡G
011234101234110123221012332101443210
ArticulationPoints⁡G
3,4,5
H:=DeleteVertex⁡G,3
H≔Graph 27: an undirected unweighted graph with 5 vertices and 3 edge(s)
IsConnected⁡H
ConnectedComponents⁡H
1,2,4,5,6
H:=InducedSubgraph⁡G,3,4,5
H≔Graph 28: an undirected unweighted graph with 3 vertices and 2 edge(s)
P:=SpecialGraphs[PetersenGraph]⁡
P≔Graph 29: an undirected unweighted graph with 10 vertices and 15 edge(s)
IsRegular⁡P
DegreeSequence⁡P
3,3,3,3,3,3,3,3,3,3
CliqueNumber⁡P
2
IsPlanar⁡P
IsHamiltonian⁡P
Girth⁡P
5
ChromaticNumber⁡P
3
Directed graphs
M:=Digraph⁡1,2,2,1,1,3,2,4,2,5,4,5,5,4
M≔Graph 30: a directed unweighted graph with 5 vertices and 7 arc(s)
DrawGraph⁡M
IsConnected⁡M
IsAcyclic⁡M
IsStronglyConnected⁡M
StronglyConnectedComponents⁡M
3,1,2,4,5
AdjacencyMatrix⁡M
0110010011000000000100010
AllPairsDistance⁡M
0112210211∞∞0∞∞∞∞∞01∞∞∞10
Graph Attributes
You may attach arbitrary information to the graph as a whole, each vertex of the graph, and each edge of the graph. This is done using the attribute commands {Get/Set/List/Discard}{Graph/Vertex/Edge}Attribute(s).
G≔Graph 31: an undirected unweighted graph with 4 vertices and 3 edge(s)