A graph is a computation object that is used to model relationships among things. For example, constituent atoms within a molecule, components within an electrical circuit, and nodes in a communication network are all things that you can represent and manipulate as graphs. Trees are graphs with special properties, so you could represent a hierarchical chart or family tree as a graph. There is a lot of terminology involved with graph theory. The next few paragraphs give a quick overview of the basic terminology needed to study concurrent algorithms to compute with graphs. If you’re already familiar with graph theory terms, feel free to skip ahead a bit. Of course, if you’ve made it this far through the book, what’s another page and a half between reader and author?

A graph is made up of two finite sets: a set of
*nodes* (or *vertices*) and a set of
*edges*. Each node has a label to identify it and
distinguish it from other nodes. Edges in a graph connect exactly two nodes
and are denoted by the labels of the pair of nodes that are related. If you
have a graph of three nodes—*A*, *B*,
and *C*—the two edges connecting *A*
with *B* and *B* with
*C* would be written as
(*A*,*B*) and
(*B*,*C*).

A graph is *directed* if all edge pairs are
ordered. Directed edges represent a one-way relationship from one node to
another. If the node pairs are unordered, the graph is
*undirected*. A directed graph ...

Start Free Trial

No credit card required