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