Graph Based Evolutionary Algorithms - Advancing Artificial Intelligence Through Biological Process Applications - page 314

informed decision when selecting a graph for use
on a new problem.

Definition 3: The n-cycle , denoted C n , has
vertex set Z n . Edges are pairs of vertices that differ
by 1 (mod n) so that the vertices form a ring with
each vertex having two neighbors.

bACkGROUND

Definition 4: The n-hypercube , denoted H n ,
has the set of all n character binary strings as its
set of vertices. Edges consist of pairs of strings
that differ in exactly one position. A 4-hypercube
is shown in Figure 1(d).

A combinatorial graph or graph G is a collection
of vertices V(G) and edges E(G), where E(G) is a
set of unordered pairs from V(G). Two vertices
of the graph are neighbors if they are members
of the same edge. We say an edge is incident on
the two vertices it contains. The degree of the
vertex is the number of edges containing (incident
upon) that vertex. If all vertices in a graph have
the same degree, the graph is said to be regular ,
and if the common degree of a regular graph is k ,
then the graph is said to be k-regular . If you can
go from any vertex to any other vertex traveling
along vertices and edges of the graph, the graph
is connected . A cycle is a path going from any
vertex back to itself. The diameter of a graph is
the longest that the most direct path between any
two of the vertices can be.

Definition 5: The n x m-torus , denoted T n,m , has
vertex set Z n x Z m . Edges are pairs of vertices that
differ either by 1 (mod n) in their first coordinate
or by 1 (mod m) in their second coordinate, but
not both. These graphs are n x m grids that wrap
(as tori) at the edges. A T 12_6 graph is shown in
Figure 1(c).

Definition 6: The generalized Petersen graph
with parameters n,k, denoted P n,k has vertex set
[0, 1, . . . , 2n - 1]. The two sets of vertices are
both considered to be copies of Z n . The first n
vertices are connected in a standard n-cycle . The
second n vertices are connected in a cycle-like
fashion, but the connections jump in steps of size
k (mod n). The graph also has edges joining cor-
responding members of the two copies of Z n . The
graph P 32,5 is shown in Figure 1(b).

List of Graphs

The mathematical definitions of the graphs used
here are given, as well as those of other graphs
required to properly describe them.

Definition 1: The complete graph on n verti-
ces, denoted K n , has n vertices and all possible
edges. An example of a complete graph is shown
in Figure 1(a).

Definition 7: A tree is a connected graph
with no cycles. Degree zero or one vertices are
termed leaves of the tree. A balanced regular tree
of degree k is a tree constructed in the follow-
ing manner. Begin with a single vertex. Attach k
neighbors to that vertex and place these neighbors
in a queue. Processing the queue in order, add
k-1 neighbors to the vertex most recently removed
from the queue and add these neighbors to the
end of the queue. Continue in this fashion until
the tree has the desired number of vertices. We
denote these graphs RBT(n,k) where n is the
number of vertices. (Notice that not all n are
possible for a given k.)

Definition 2: The complete bipartite graph
with n and m vertices, denoted K n,m , has vertices
divided into disjoint sets of n and m vertices and
all possible edges that have one end in each of
the two disjoint sets. The 3-pre-Z graph shown in
Figure 1(e) is the complete bipartite graph K 4,4 .