A graph is a nonempty finite set V of elements called vertices together with a possibly empty set E of pairs of vertices called edges. Here are a few examples of graphs:
 Vertex set V={a, b, c, d} and edge set E={(a, b), (b, d)}
 Vertex set V={1, 2, 3, 4} and edge set E={(2, 4)}
 Vertex set V={wolf, goat, cabbage} and edge set E={(wolf, cabbage)}
 Vertex set V={A, B, C} and edge set E={}
We can draw pictures to represent graphs. Vertices are represented by dots and an edge (v, w) by an arc that starts from the dot representing v and ends at the dot representing w.
The simplest type of graph is a null graph. It consists of a nonempty finite set of vertices and no edges.
Java Web Start Activity:
To get examples of null graphs, launch the Java Web Start application
by clicking on the link below this paragraph. Once the application is
running, click on the
+ button to increase the number of vertices. Click on the
 button to decrease the number of vertices.
Petersen activity:
We shall use this activity to introduce you to the program
Petersen. You need Java 6 or later to run the program.
You can download the jar file for Petersen using the link
"Getting Petersen" above. Windows users can start the program
by double clicking on the jar file. For other platforms, there are instructions on
download page for starting the program from a command console.
After the welcome
message and copyright notice you will get a screen with a graph drawn
on it. This graph is called the Petersen Graph after Julius Petersen.
To get a null graph, click on the Graph menu item and then select Named Graph followed by Null Graph. In future we shall represent such a sequence of clicks as Graph  Named Graph  Null Graph. You will get an input box with the question 'How many vertices? Press 4 and then press the Enter key (or click OK.) You will get four vertices on the screen like in Fig. 1.1 The title 'N(4)' at the top of the frame in the program means Null graph on four vertices, sometimes written as N _{4} .
 

In a similar way, try to get the null graph with 10 vertices called N _{10}. Notice that the labels 1, 2, 3, etc. are the same color as the vertices they refer to. This will be useful when you have many vertices on the screen. You can move the vertices around by dragging them with the mouse. If the colors don't come out well on your monitor you can turn the color off by clicking the menu item Picture, and then unchecking the radio button labeled Color on/off. Try a few other null graphs like N _{25} and so on.
There will be a limit on the number of vertices the program can handle. This limit depends on the version of the program and the license installed. It can be anything from 10 to 1000. Other limitations will be the amount of memory available to you and the amount of screen space you have. Some algorithms take a very long time to run when the graphs are large. If you need to examine larger graphs you can get a license from the download page. You install the license by selecting Help  License in the program and pasting the license in the lower part of the dialog. Restart the program and you should be able to load larger graphs.
Null graphs are not very interesting so let us introduce some edges. If an edge e = (v, w), where v and w are vertices we call v and w the end vertices of e. The edge will be represented in the picture by an arc or a line segment from one end vertex to the other. Two vertices v and w are adjacent if there is an edge e = (v, w) in the graph. We also say that the edge e is incident to the vertex v (and also to vertex w). The Petersen graph, for example, has ten vertices and fifteen edges. If an edge has the form e = (v, v), i.e., it starts and ends at the same vertex we shall call it a loop. The Petersen graph has no loops.
 

Petersen activity:
In the Petersen program, use the procedure outlined above to get
N_{4} on your screen as in fig. 1.1. On the menu,
click
Mouse  Add/Delete Edge  Straight.
 

 

Experiment and add edges to graphs as you wish. In most of the material in this course we shall talk about simple graphs. A simple graph has no more than one edge between vertices and no loops.
Sometimes you will need to store your graph on disk so let us learn how to save and restore a graph. Get the graph N_{25} as above. To save it, click Graph  Write Graph to Disk. You will get a file chooser dialog to choose the location and name for the graph on your file system. The files are stored with a .pet extension. Now suppose at a later time you want to read this graph from the disk. To restore the graph from your disk drive click Graph  Read Graph from Disk. You will get a file chooser dialog to choose the location and name of the file you want to read into the program.
The program can also create JPEG images. To create a JPEG click Graph  Write JPEG to Disk. You can view the JPEG file in your favorite graphics program.
There are many interesting graphs so let us look at a few of them. Many graphs have names. The Petersen program has some named graphs. You get them by clicking Graph  Named Graph.
Complete graphs are graphs in which every vertex is adjacent to every other vertex. To get a complete graph, click Graph  Named Graph  Complete  Complete Graph. You will be asked how many vertices you want. Input an integer (e.g. 5). You will then get the complete graph on 5 vertices which we will call K_{5} for short.
A complete bipartite graph has the vertices in two groups (let us call them left and right). All the vertices in one group are adjacent to all the vertices in the other but vertices in the same group are not adjacent to one another. To get a complete bipartite graph click Graph  Named Graph  Complete  Complete Bipartite Graph. You will be asked how many vertices you want on the left and on the right. Try 4 vertices on the left and 3 on the right to get the graph we will call K_{4,3}. Examine some of the other named graphs in the program.
Programming Task
© C. Mawata