Information Technology Reference
In-Depth Information
When
d
=
2, a 2
d/
2
×
2
d/
2
array is a 2
×
2 array that is itself a four-vertex hypercube.
When
d
=
3, a 2
(
d
+
1
)
/
2
×
2
(
d−
1
)
/
2
×
2 array. (See Fig.
7.13
,page
299
.) It
can be embedded into a three-dimensional hypercube by mapping the top and bottom 2
array is a 4
×
2
subarrays to the vertices of the two 2-cubes contained in the 3-cube. The edges between the
two subarrays correspond directly to edges between vertices of the 2-cubes.
Applying the same kind of reasoning to the inductive hypothesis, we see that the hypothesis
holds for all values of
d
≥
2. If a 2D array is not of the form indicated, it can be embedded
into such an array whose sides are a power of 2 by at most quadrupling the number of vertices.
7.6.2 Cube-Connected Cycles
A reasonable alternative to the hypercube is the
cube-connected cycles (CCC)
network shown
in Fig.
7.14
. Each of its vertices has degree 3, yet the graph has a diameter only a constant factor
larger than that of the hypercube. The
(
d
,
r
)
-CCC is defined in terms of a
d
-dimensional hy-
percube when
r
d
.Let
(
a
d−
1
,
a
d−
2
,
...
,
a
0
)
and
(
b
d−
1
,
b
d−
2
,
...
,
b
0
)
be the indices of two
adjacent vertices on the
d
-dimensional hypercube. Assume that these tuples differ in the
j
th
component, 0
≥
=
j
. Associated with vertex
(
a
d−
1
,
...
,
a
p
,
...
,
a
0
)
ofthehypercubearethevertices
(
p
,
a
d−
1
,
...
,
a
p
,
...
,
a
0
)
,0
≤
j
≤
d
−
1; that is,
a
j
=
b
j
⊕
1and
a
i
=
b
i
for
i
≤
p
≤
r
1, of the CCC that form a ring; that is, vertex
(
p
,
a
d−
1
,
...
,
a
p
,
...
,
a
0
)
is adjacent to
vertices
((
p
+
1
)mod
r
,
a
d−
1
,
...a
p
,
...
,
a
0
)
and
((
p
−
−
1
)mod
r
,
a
d−
1
,
...
,
a
p
,
...
,
a
0
)
.
≤
p
≤
d
−
1, vertex
(
p
,
a
d−
1
,
...
,
a
p
,
...
,
a
0
)
is adjacent to vertex
In addition, for 0
(
p
,
a
d−
1
,
...
,
a
p
⊕
1,
...
,
a
0
)
on the ring associated with vertex
(
a
d−
1
,
...
,
a
p
⊕
1,
...
,
a
0
)
of the hypercube.
Figure 7.14
The cube-connected cycles network replaces each vertex of a
d
-dimensional hyper-
cube with a ring of
r ≥ d
vertices in which each vertex is connected to its neighbor on the ring.
The
j
th ring vertex, 0
≤ j ≤ d −
1, is also connected to the
j
th ring vertex at an adjacent corner
of the original hypercube.
Search WWH ::
Custom Search