Graphs and Connectivity

You are undoubtedly familiar with graphs of functions from your experience in algebra courses: y = f(x) on the Cartesian Plane. Those graphs all shared one common characteristic: any two graphs which appeared to be different did indeed represent different functions (as long as the units on the coordinate axes were the same). For example, it is clear that a straight line and a parabola represent different functions.

We are concerned in this chapter with a very different kind of graph. For us, a graph is a "topological" object: graphs are distinguished by the way in which their parts are connected, but not necessarily by their appearance. To be specific, we will define a graph as a set of points called "vertices" (singular "vertex") and a set of lines called "edges" which connect the vertices. Since we will not be concerned with graphs containing isolated vertices (with no edges connecting them to the remainder of the graph), we will be able to describe any graph completely as a set of edges, with each edge specified as a set containing the two vertices connected by that edge. For example, the following graph

is completely described by the set of edges
{{A,B},{A,C},{A,D},{B,C},{B,D},{C,D},{D,E},{E,F},{E,G}}
Since the edges are specified as sets, the order of the vertices does not matter: the edge
{A,B}
is the same as the edge
{B,A}.
Now consider the following graph:
It appears to be very different from the first graph: the vertices are in different places and most of the edges are either larger or smaller than before. However, the two graphs are identical! If we write down the set of edges in the second graph:
{{A,B},{A,C},{A,D},{B,C},{B,D},{C,D},{D,E},{E,F},{E,G}}
we see that it is exactly the same set which we wrote down for the first graph. Two graphs are equivalent if they have the same set of edges.

It is instructive to see visually how the second graph is equivalent to the first:

Click here to view the deformation of the first graph into the second. The most important thing to notice about this process is that none of the edges were disconnected from their vertices or otherwise broken at any time. This observation provides us with an intuitive understanding of topological objects: what matters is how they are connected, not how they appear.

We will define the "degree" of a vertex as the number of edges connected to it. For the graph above, the vertices A, B, C and E have degree 3, the vertex D has degree 4 and the vertices F and G each have degree 1. It is interesting to note that

the sum of the degrees of the vertices in a graph is equal to twice the number of edges.
In the example above, which had 9 edges, the sum of the degrees of the vertices is
3 + 3 + 3 + 3 + 4 + 1 + 1 = 18.
This relationship is perhaps the simplest example of a "topological invariant". A topological invariant is a relationship which is true regardless of the appearance or size of the graph.

Connectivity

We can describe the connectivity of a graph in terms of movement between vertices. We define a "walk" to be an alternating sequence of vertices and edges, beginning and ending with vertices. A walk is completely described by an ordered list of vertices: in the graph above,

are all walks (and there are infinitely many more). The length of a walk is defined to be the number of edges in the walk; the five walks listed above have lengths 1, 2, 2, 4 and 4, respectively.

A "path" is defined as a walk with no repeated vertices; of the walks above, only

are paths. A walk which begins and ends on the same vertex is called a "cycle"; of the walks above, only

are cycles. Obviously, cycles are not paths. Graphs can contain loops, such as the graph

(where the edge connecting the vertex A to itself is the loop). The walk
{A,A}
is then a cycle, but not a path.

A graph is "connected" if there is a path between any two vertices. Conversely, if there are two vertices in a graph which are not connected by any path, the graph is "disconnected". A vertex is a "cut point" if removal of the vertex disconnects the graph:

Here we have removed the vertex D (and the edges which were connected to it), and thereby disconnected the graph into two disjoint graphs. In this graph, E is also a cut point.

Similarly, an edge is a "bridge" if removal of the edge disconnects the graph:

Here we have removed the bridge edge {D,E}. In this graph, {E,F} and {E,G} are also bridge edges. Notice that every bridge edge has a cut point at (at least) one end.
The Internet (or any network) can be represented as a (very complex) graph: the vertices represent the routers (computers responsible for passing data through the network) and the edges represent the communications links (wires, fiber optic cables, satellite links, etc.) over which data travels. The presence of cut points or bridge edges in a network graph indicates a lack of fault tolerance: failure of the router at a cut point or failure of the link over a bridge edge disconnects the network and prevents data from passing through it.
There are two useful ways to measure distance in graphs. We define the distance between two vertices as the length of the shortest path between them. In the graph
the following paths exist between the vertices A and E:

These have lengths of 4, 3, 3 and 2, respectively, and so the distance between A and E is 2. This notion of distance will be important when you learn about routing in networks (where the shortest path is usually the fastest path).

We can also define the diameter of a graph as a whole as the maximum distance between any two vertices (remember that the distance is the length of the shortest walk; therefore, the diameter is the longest of the shortest walks!). To compute the diameter of the following graph (which is slightly different from the graph above),

we need in principle find the shortest path for every pair of vertices in the graph; the longest of these will be the diameter of the graph. Even with a graph as relatively small as this one, this can be a time consuming algorithm. Fortunately, we can apply the following heuristic (an intuitive simplification):
the most distant vertices in a graph will be on opposite sides of cut points or bridge edges, if any exist.
Hence in this case, we need only concern ourselves with paths connecting A, B or C with F or G:

The shortest path between A and F (or G) has length 3 (ie., A, D, E, F); the shortest path between B and F (or G) has length 4 (ie., B, C, D, E, G), and the shortest path between C and F (or G) has length 3 (ie., C, D, E, F). The longest of these is 4, and therefore the diameter of this graph is 4. Graph diameters are important when discussing collision domains in Ethernet.


Types of Graphs

Graphs can be categorized in a number of ways:

This list (as well as this entire chapter) is not exhaustive; we have attempted to focus on those topics of greatest interest to the student of computer science. We move next to a special class of graphs: trees.


Go to:Title PageTable of ContentsIndex

©2002, Kenneth R. Koehler. All Rights Reserved. This document may be freely reproduced provided that this copyright notice is included.

Please send comments or suggestions to the author.