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.

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

- the vertex B was moved down and to the left;
- the vertex C was move to the left slightly;
- the edge connecting B to D was lifted "above" the graph without breaking the connection between B and D, and was deformed into a circular arc around A;
- the vertex E was moved down and slightly to the left;
- the vertex F was lifted above the graph and placed below B, and
- the vertex G was moved up and to the left.

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.

In the example above, which had 9 edges, the sum of the degrees of the vertices isthe sum of the degrees of the vertices in a graph is equal to twice the number of edges.

3 + 3 + 3 + 3 + 4 + 1 + 1 = 18.This relationship is perhaps the simplest example of a "

- A, B
- A, B, C
- A, B, A
- A, B, C, B, A
- A, C, D, E, G

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

- A, B
- A, B, C
- A, C, D, E, G

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

- A, B, A
- A, B, C, B, A

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

the following paths exist between the vertices A and E:

- A, B, C, D, E
- A, B, D, E
- A, C, D, E
- A, D, 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

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:

- A, B, C, D, E, F
- A, B, C, D, E, G
- A, C, D, E, F
- A, C, D, E, G
- A, D, E, F
- A, D, E, G
- B, A, C, D, E, F
- B, A, C, D, E, G
- B, A, D, E, F
- B, A, D, E, G
- B, C, A, D, E, F
- B, C, A, D, E, G
- B, C, D, E, F
- B, C, D, E, G
- C, A, D, E, F
- C, A, D, E, G
- C, B, A, D, E, F
- C, B, A, D, E, G
- C, D, E, F
- C, D, E, 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.

Graphs can be categorized in a number of ways:

- connected
- disconnected
**complete**, where every vertex is connected to every other vertex:**planar**, which can be drawn in a plane with no edges crossing:**labeled**(where each vertex or edge is assigned a numerical**weight**which is greater than or equal to 0)**acyclic**, which contains no cycles:

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 Page Table of Contents Index

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