- Email: [email protected]

HYPERCUBES, AND

[email protected]

SHUFFLE-EXCHANGE DE BRUIJN DIGRAPHS*

NIALL

GRAHAM Computing

AND FRANK

0895-7177193 $6.00 + 0.00 1993 Pergamon Press Ltd

GRAPHS

HARARY

Research Laboratory

New Mexico State University, Las Cruces, NM 88003, U.S.A.

Abstract-The hypercube Qn, the shuffle-exchange graph S, and the teleprinter diagram T,, have the same set of 2” nodes, namely the n digit binary strings. Our purpose is to specify precisely the pairwise intersections of their edge sets and of their arc sets. 1. MOTIVATION

There are now several massively parallel processors whose architecture is based on hypercube structures Qn. A survey of hypercube theory is given in [I]. As mentioned in [2], shuffle-exchange graphs have applications in the design of parallel processors and are suitable for executing certain parallel algorithms. Teleprinter diagrams, also known as de Bruijn digraphs, arise in the analysis of feedback shift registers, see [3]. The number of directed Eulerian trails in T, was determined by van Aardeene-Ehrenfest and de Bruijn [4]. 2. INTRODUCTION A hypercube may be defined recursively in terms of the Cartesian product of graphs [5, p. 23).

Q7L=

K2,

n=

&n-l

n > 2.

X &I,

1,

(1)

The hypercube Qn of dimension n may also be defined as the graph of 2n nodes, each of which is uniquely labelled with an n-digit binary string with two nodes adjacent whenever their labels vary in exactly one digit. The first four hypercubes are displayed in Figure 1.

Figure 1. The four smallest hypercubes.

As opposed to the definitions in [5], our digraphs may have (directed) loops, indeed in one case, we require two loops at one node as in Figure 2. The family of teleprinter diagrams T, = (V, A) with node set V and arc set A may be defined recursively in terms of line digraphs. Given a directed graph D, the line digraph L(D) is defined by specifying its nodes and arcs as follows. The nodes of L(D) are the arcs of D. Each pair of arcs in D of the form (x, y), (y, z) define the arc ((2, y)(, y, z)) in L(D). Note that z = z is permitted; thus a symmetric pair of * Research supported in part by ONR Grant N00014-90-J-1860. Typeset by &+TEX 69

N. GRAHAM, F. HARARY

70

0000

100

00 0

0

e

1100 IO

01 1

8 #

110

11

Figure 2. The four smallest teleprinter diagrams.

arcs in D goes over to a similar pair in L(D). Defining Te as one node with two loops as shown in Figure 2, which also shows Tl, T2 and T3, we have the recursive expression: T, = L(T,_i).

(2)

We label each arc (bw, WC) in L(T,-1) as bwc, where b and c are binary digits and w is a b ear the same labels as their corresponding binary (n - 2)-string. The nodes in T, = L(T,_i) has outdegree 2 since each node WC in T,_l has arcs in Tn-l. Any node bwc on V(L(T,_l)) outdegree 2. Note also that application of the unary operation L to T,_l doubles the number of nodes, since each node in T,_l has outdegree 2. Teleprinter diagrams may also be regarded as the state diagrams of n-bit shift registers and are sometimes called de Brzl+z diagrams [4]. The shufle-exchange graph S, of dimension n is the graph of 2n nodes, each of which is again an n-bit binary string; it has two different kinds of edges: shuffle edges and exchange edges. A shufle edge joins two nodes whose binary labels are exactly one “cyclic move” apart, i.e., , b2 bl is adjacent to both bl b,, . . . , b2 and b,_l, . . . bl 6,. For each binary digit b, b,b,_l,... let 6 = 1 - b. Then an exchange edge joins two nodes whose labels vary in the first digit, i.e., b,, . . , b2 bl and b,, . . . , bz 61. The shuffle-exchange graphs Ss, Ss and 5’4 are shows in Figure 3, in which the bold edges are exchange edges. The hypercube Qn, the shuffle-exchange graph S, and the teleprinter diagram T, all have precisely the same set of 2n nodes. Hence, it is natural to confront the edge and arc sets of these graphs with each other. The operator D on a graph G = (V, E) replaces G by the digruph of graph G, D(G) = (V, A), where the set A of arcs is derived from the edge set E by replacing each edge {x, y} by the symmetric pair of arcs (z, y) and (y, x). Similarly, the graph of a digraph D = (V, A) is the graph G(D) with the same node set V, in which two nodes x and y are adjacent whenever there is at least one arc joining them in D. 3. EDGE

INTERSECTIONS

Let F be the pair of edges {On,On-il} and {In, In-l 0). Thus the graph of F is a labelled 2Ks. We shall first establish that the intersection of all three edge sets gives two independent edges:

EC&n) n @GO’,))

c-iE(G)

=

=2.

(3)

In particular, their intersection is precisely F. To verify (3), we pairwise confront the sets of edges in the three graphs, by seeking pairs of binary numbers that (a) vary in one digit,

Hypercubes

71

Figure 3. The four smallest shuffle-exchange graphs.

(b) are successive shift register states, and (c) are distinct in the first digit or are one digit rotations

of each other.

The two edges in F uniquely satisfy these three requirements. We next establish the set equation E(S,)

= W%)

n

EC&J] u [W&d n (~(W’n))

- F)l

(4

and show that this is a partition of the edges in S,. In words, S, may be partitioned into two edge disjoint subgraphs, one of which is a subgraph of E(G(T,)) - F, the other of Qn. These are, respectively, the shuffle edges and the exchange edges of S,. The arc sets A(T,) - A(D(S,)) is depicted and A(D(Qn)) n ACT4 are also specified and a summary of the graph intersections in Figure 4. By applying the digraph operator an analogous summary for digraph intersections is found.

Figure 4. The intersections of Qn, S, and T’

N. GRAHAM. F. HARARY

72

Note that the right member of (4) becomes

on applying the set distributive law of intersection over union. As this is precisely E(S,) by (4), the assertion that (4) provides a partition states that each edge of S, is in either Qn or in G(tJ - F. We require the mobius function p(n) of a positive integer n. Writing n as a product of prime powers n = pyi pz2, . . . ,pF the mobius function ,u(n) is defined by n-

1, P(n) = i

1,

0,

any ei > 1,

(-IF,

er = e2 = . . . = e, = 1.

(5)

We will prove that E(S,)

n E(Q,)

= 2”-l K2

(6)

is a perfect matching of the node set, and that E(S,)

n E(G(T,))

= u

mi Ci,

(7)

iln

where the mi satisfy mn = ; c

I*.(d)2?

din PROOF OF (6). Clearly, E(Q,) d oes not contain any shuffle edges, as a shuffle changes an even number of binary digits, and edges in E(Q,) are defined between nodes whose labels vary in exactly one digit. Exchange edges are defined between all nodes whose labels vary in the last digit and are a subset of E(Q,). As they are all independent and cover all the nodes, they comprise a perfect matching of order 2”-l. Also the edges E(S,) n E(Q,) lie in one dimension of Qn and thus comprise a cut set that separates Qn into two copies of Qn_r, giving

EC&n) - -W&d = 2Q,-1.

(9)

PROOF OF (7). Obviously each node is on some cycle of shuffle edges in E(S,) and clearly no node is on two such cycles. Thus the shuffle edges form a set of node disjoint cycles in S,. It is convenient to define “cycles” of length 1 and 2: Cr as an undirected loop and C2 as the multigraph with two nodes which are joined by two edges. Obviously, the nodes On and In lie in cycles of length one. For prime n, a binary n-string cannot contain a periodic subsequence and thus the shuffle operation must be performed n times to permute a binary label onto itself. Therefore, all nodes other than On and In lie on cycles of length n. The number of such cycles is of course (2n - 2)/n, which provides a constructive proof of the well-known corollary of Fermat’s theorem [6, p. 631 that prime n divides 2+’ - 1. For composite n, all nodes with labels of period d < n lie in some cycle of length d in S, n G(T,_r). Let md be the number of cycles of length d. As every node is on some cycle we find by counting the nodes that xdrnd = 2n. (10) din Solving (10) for m, nm, = 2n - c din d

dmd,

(104

Hypercubes

73

it is seen that m, is the number of circular binary strings of length n that are not comprised

of periodic substrings. In other words, md is the number of circular binary strings of length d and period d. Given length n, any string of period d is completely specified by its first d digits. Hence, the number of such strings is exactly the number of strings of period d and length d. On replacing binary digits by beads, we find that md enumerates the ways of making an aperiodic, plane, two-colored necklace of d beads. By a routine application of the mobius inversion formula, (7) is immediately derived from (9), see [7, p. 111. The first twelve values of md are presented in Table 1. Table 1. The number of cycles of given length in S, CIG(T,) d md

11 2

2

3

4

5

6

7

8

9

10

11

12

1

3

3

6

9

18

30

56

99

186

335

4. ARC INTERSECTIONS The arcs of the teleprinter diagram T, are defined between nodes whose binary strings form a sequence of two successive shift register states. For example the two possible successive states of 0110 in T4 are 1100 and 1101. Clearly, nodes joined by shuffle edges in S, are also successive shift register states and are therefore adjacent in Tn. Also, exchange edges are defined between nodes that cannot be successive shift register states. Thus the shuffle edges are not the only edges common to both S, and G(T,). These edges are configured in node disjoint cycles and are enumerated by the coefficients md. As these cycles are directed, we may write down the analogue of (6) for digraphs A(%)

n A(D(%))

- u

md

ed.

(11)

db

For example, when n = 12, we obtain A(T12)

n A(D(&))

= 2ti1 u ez u 2& u 3tiJ u 9tiG u 335&.

(12)

We now show that

[email protected](&,))

n A(Td = &.

(13)

PROOF OF (13). As edges in Qn are defined between nodes whose labels vary in exactly one binary digit, it is immediate that the arcs common to both D(Qn) and T, must be those that join successive shift register states whose labels vary in exactly one binary digit. For every substring of the form 10 or 01 in a binary string, one digit will change when the binary string is shifted. Therefore, the arcs in A(D(Q,)) n A(T,) lie between nodes whose binary labels contain at most one substring of the form 01 or 10. This is precisely the set V, = (0” lnPk, 1” On-” : 0 < Ic < n}.

(14)

It is also clear that each element of V, has a successor under the shift operation that is also in V,. A nd 1 ‘t 1s . easily seen that this succession For example, Ok 1n-k has as its successor Ok-’ I+‘+‘. of nodes forms a directed cycle of length 2n as the arc intersection of the teleprinter diagram T, and the digraph of the hypercube D(Qn), establishing the result (13). Finally, we consider the arc set A(T,) - A(D(&)) w h’Kh a1so consists of a set of node disjoint directed cycles. With node labels of the form b,, . . . , bl the arc set may be defined as the set of allpairs(b,...babl,blb,.. . bz). In words, the bits are rotated right one place with the rightmost bit negated. As each such operation changes the weight of the binary string by one, it is obvious that all cycles defined in this way are of even length. On considering a binary string as the concatenation of s substrings ~1, ~2,. . , w, of equal length, we find that if a cycle of length 2s exists, then denoting by W the string obtained by negating each string in w, WlW2W3...

w, = W,_l

wsWI.

. . ws__2,

N. GFSHAM,

74

F. HARARY

for some s that divides n, and by equating the substrings we find the following unique solution for odd s: w1 z&&z... = (J, = ij, = (& =. . f = &_1. No solution exists for even s. It is convenient to define the pair of arcs found by forming F’ = {(on, on-1 l), (l”, In-1 0)) from the pair of edges F. Then by letting c2k enumerate the cycles of length 2k, we find that

W(W)1 u F’= u

[A(%.) -

~2n,s~2n,s.

(15)

471

s odd

Then by observing that all the 2n nodes are covered by these node-disjoint cycles, we deduce that c, is given by the recurrence relation,

cp,

1 = -

P-l - C

n

.

(n/s)c2,/,

sin

s odd

(16)

I

For prime n, (16) simplifies to y-1

_

1

(17)

c2n = n

f&k+1= 22k-k-?

(18)

The first eight values of ~2~ are presented in Table 2. Table 2. The number of directed cycles in T,, - D(&). n C2n

11 1

2

3

4

5

6

7

1

1

2

3

5

9

81 16

Evidently the arcs of F’ are included in the same cycle of length 2n for all values of n, namely the cycle specified by A(D(Q,)) n A(T,). When these two arcs are accounted for, their removal eliminates one directed cycle of length 2n and introduces two directed paths of length n - 1, giving A(G)

- A(D(%)

= 2%~1

u

22,,,2;2,,,

- 62,.

(19)

4n s odd

The intersection patterns for the graphs and digraphs resulting from ternary, quaternary, and larger alphabets are more complex and remain to be investigated. REFERENCES 1. F. Harary, J.P. Hayes and H.-J. Wu, A survey of the theory of hypercube graphs, Computers Math. Appl. 15 (4), 277-289 (1988). 2. F. Leighton, Complexity Issues in VLSI, Optimal Layouts for the ShuffIe-Exchange Graph and other Networks, MIT Press, Cambridge, MA, (1983). 3. S. Golomb, Shift Register Sequences, Holden Day, San Francisco, (1967). 4. T. van Aardenne-Ehrenfest and N.G. de Bruijn, Circuits and trees in directed graphs, Simon Stetin 28, 203-317 (1951). 5. F. Harary, Graph Theory, Addison-Wesley, Reading, (1969). 6. G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 5th edition, Clarendon Press, Oxford, (1979). 7. M. Hall, Combinatorial Theory, Wiley, New York, (1986).