The GraphTheory Package
This worksheet demonstrates some features of the GraphTheory package. It is presented in a tutorial format.
>



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.
>


 (1.1) 
>


 (1.2) 
>


 (1.3) 
>


 (1.4) 
>


 (1.5) 
>


 (1.6) 
You may specify the numberof vertices, , in which case they are labeled 1,2,..., .
>


 (1.7) 
>


 (1.8) 

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.
>


 (1.1.1) 
>


 (1.1.2) 
>


 (1.1.3) 
For a directed graph, use the AddArc command and input the edges as lists of vertices.
>


 (1.1.4) 
>


 (1.1.5) 
>


 (1.1.6) 


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
>


 (1.2.1) 
>


 (1.2.2) 
>


 (1.2.3) 
Similarly, the above previous directed graph H, which is a directed path, can be created by
>


 (1.2.4) 
>


 (1.2.5) 


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.
>


 (1.3.1) 
>


 (1.3.2) 
>


 (1.3.3) 
>


 (1.3.4) 
>


 (1.3.5) 
>


 (1.3.6) 
>


 (1.3.7) 
>


 (1.3.8) 


Using a list of neighbors


If G has n vertices, the input is a list of n lists of vertices.
>


 (1.4.1) 
>


 (1.4.2) 
>


 (1.4.3) 
>


 (1.4.4) 
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.
>


 (1.4.5) 
>


 (1.4.6) 
>


 (1.4.7) 
>


 (1.4.8) 
>


 (1.4.9) 


Using trails


This is a convenient shorthand. The trail 1,2,3,4 represents the edges 1 to 2 to 3 to 4.
>


 (1.5.1) 
>


 (1.5.2) 
>


 (1.5.3) 
>


 (1.5.4) 
>


 (1.5.5) 


Weighted edges


To create a weighted graph, use the weighted option.
>


 (1.6.1) 
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.
>


 (1.6.2) 
>


 (1.6.3) 
>


 (1.6.4) 
The same graph can be created directly with
>


 (1.6.5) 
An edge weight can be 0.
>


 (1.6.6) 
>


 (1.6.7) 
>


 (1.6.8) 
>


 (1.6.9) 


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.
>


 (1.7.1) 
>


 (1.7.2) 
>


 (1.7.3) 
>


 (1.7.4) 
>


 (1.7.5) 
>


 (1.7.6) 
>


 (1.7.7) 
>


 (1.7.8) 
>


 (1.7.9) 



Drawing Graphs


Here we just show some examples which illustrate the main options.
Further examples are given under the section "Special Graphs".
>


 (2.1) 
>


>


 (2.2) 
>


>


If you dislike the placement of the vertices, you can specify them as follows.
>


>


>


 (2.3) 
The Petersen graph is very well known in graph theory. It is a nonplanar graph. This is one of the standard drawings.
>


The placement of the vertices is stored in the graph data structure.
>


 (2.4) 
The "spring" method for drawing graphs will find other "symmetric" drawings of the Petersen graph. Try executing this a few times.
>


The spring method works in 3D
>


The spring method will work for moderately large graphs (graphs up to 1000 vertices).
>


 (2.5) 
>


For large weighted graphs the edge weights and edge labels may "clutter" the graph. You can turn these off.
>


 (2.6) 
>


>


>




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`, `sparse6`, and `graph6`.


Graph Properties


There are lots of graph commands. Here we illustrate basic commands and how to accomplish various tasks.

Undirected graphs


>


 (4.1.1) 
>


>


 (4.1.2) 
>


 (4.1.3) 
>


 (4.1.4) 
>


 (4.1.5) 
>


 (4.1.6) 
>


 (4.1.7) 
>


 (4.1.8) 
>


 (4.1.9) 
>


 (4.1.10) 
>


 (4.1.11) 
>


 (4.1.12) 
>


>


 (4.1.13) 
>


 (4.1.14) 
>


 (4.1.15) 
>


>


 (4.1.16) 
>


 (4.1.17) 
>


 (4.1.18) 
>


 (4.1.19) 
>


 (4.1.20) 
>


 (4.1.21) 
>


 (4.1.22) 


Directed graphs


>


 (4.2.1) 
>


>


 (4.2.2) 
>


 (4.2.3) 
>


 (4.2.4) 
>


 (4.2.5) 
>


 (4.2.6) 
>


 (4.2.7) 



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).
>


 (5.1) 
>


>


 (5.2) 
>


 (5.3) 
>


>


 (5.4) 
>


 (5.5) 


Special Graphs and Random Graphs


The two packages SpecialGraphs and RandomGraphs must be loaded separately.
>


>


 (6.1) 
>


>


>


 (6.2) 
>


As an example, we assign random integer edge weights to the prism graph G and run Kruskal's algorithm to compute the minimal spanning tree and highlight the graph with the minimal spanning tree.
>


 (6.3) 
>


>


 (6.4) 
>


>


As an example of a directed graph, we generate a weighted network on 10 vertices and compute the max flow through the network.
>


 (6.5) 
>


 (6.6) 
>


>


 (6.7) 


Highlighting Vertices and Edges


>


 (7.1) 
>


 (7.2) 
>


 (7.3) 
>


>


>


 (7.4) 
>


>


 (7.5) 
>


 (7.6) 
>


>



Return to Index for Example Worksheets
