Graph Theory Notation

Much of the load balancing problem can be described using terminology from graph theory. In fact some of these problems had already been studied in graph theory before they appeared in the context of parallel computing.

A * graph* has two key components:

- The vertex set , which is just a list of indices;
- The edge set . Each edge consists of two vertices.

A graph can be * directed*, in which case there is a
beginning and an end vertex
(also called the * head* and the * tail*, respectively) for
each edge. A graph can also be * undirected*.
For example, Figure 1 illustrates an undirected graph
(left) and a directed graph (right). The undirected graph has
5 vertices,
, and 4 edges,
. The number of vertices and edges are
therefore and respectively. The directed graph
also has 5 vertices and 4 edges,
although each edge has a direction associated. For instance,
the edge between vertex 4 and 2 has vertex 4 as the head and
vertex 2 as the tail.
All graphs in this paper are undirected, unless specified otherwise.

If two vertices and form an edge, this will be denoted
as , or
. A graph is * connected*,
if for any two vertices and , there exists a * path* connecting
them. Here a path is defined as
a list of vertices
such that
any two subsequent vertices in this list form an edge.

The distance between two vertices of a graph is defined as the minimum number of edges among all paths connecting these two vertices. For the undirected graph in Figure 1, the distance between vertex 1 and vertex 5 is 3. This is different to the physical distance between the two points in the Euclidean space.