COMPUTING SCIENCE

# Graph Theory in Practice: Part I

# Connect the Dots

The graphs studied by graph theorists have nothing to do with the wiggly-line charts that plot stock prices. Here is a definition of a graph, in all its glory of abstraction: A graph is a pair of sets, *V* and *E*, where every element of *E* is a two-member set whose members are elements of *V*. For example, this is a graph: *V* = {*a*, *b*, *c*}, *E* = {{*a*, *b*}, {*a*, *c*}}.

So much for definitions; most of us prefer to think of our graphs graphically. And in fact everyone knows that what graph theory is *really* about is connecting the dots. The set *V* is made up of vertices (also known as nodes), which are drawn as dots. The set *E* consists of edges (also called arcs, links or bonds), and each edge is drawn as a line joining the two vertices at its end points. Thus the graph defined abstractly above looks like this:

Most of the time, a picture is worth at least a thousand sets, and yet there are reasons for retaining the more formal definition. When you look at a graph drawing, it's hard not to focus on the arrangement of the dots and lines, but in graph theory all that matters is the pattern of connections: the topology, not the geometry. These three diagrams all depict the same graph:

Each of the graphs sketched above is in one piece, but not all the vertices in a graph have to be joined by edges; disconnected components can be parts of a single graph. "Multigraphs" are allowed to have multiple edges connecting the same pair of vertices. And some graphs have self-loops: edges whose two ends are both attached to the same vertex. Another variation is the directed graph, where each edge can be traversed in only one direction.

**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Feature Article**: Twisted Math and Beautiful Geometry

**Feature Article**: Simulating Star Formation on a Galactic Scale

**Perspective**: Searching for Great Adventures