Biomedical Engineering Reference
In-Depth Information
Definition 8:
The
graph Z
is created by start-
ing with a bipartite graph and then simplexifying
the entire graph to reach the desired number of
vertices. Simplexification is a graph operation
defined in (Bryden et al., 2006). Two of the steps
leading to the
graph Z
are shown in Figure 1(e)
and 1(f).
edge moves preserve the regularity of a graph
if it is regular.
Definition 10:
We generate random regular
graphs by the following algorithm. Start with
a regular graph and then repeatedly perform
3,000 edge moves on vertices selected uniformly
at random from those that are valid for edge
moves. For 3-regular random graphs of popu-
lation size 512, use P
256,1
as the starting point.
For 4-regular random graphs of population size
512, use T
16,32
as the starting point. For 9-regular
random graphs of population size 512, use H
9
as
the starting point. These graphs are denoted R(n,
k, i), where n is the number of vertices, k is the
regular degree, and i = 1, 2, 3 is the instance of
the graph in this study.
In addition, four classes of random graphs are
used. A random graph is specified by a randomized
algorithm which corresponds to a type of random
graph (a probability distribution on some set of
graphs). We use three instances of each type of
random graph.
Definition 9:
An edge move is performed as
follows. Two edges {a, b} and {c, d} are found
that have the property that none of {a, c}, {a, d},
{b, c}, or {c, d} are themselves edges. The edges
{a, b} and {c, d} are deleted from the graph, and
the edges {a, c} and {b, d} are added. Notice that
Definition 11:
We generate random toroidal
graphs as follows. A desired number of points are
placed onto the unit torus (unit square wrapped at
Figure 1. Examples of graphs used in this study
Search WWH ::
Custom Search