Information Technology Reference
In-Depth Information
1:0
1:1
0:1
1:2
Fig. 3.
Digraph
PD
(
q, m
)for
q
=3,
m
=2
of
O
m
are both two, and the other vertices have out-degree and in-degree equal
to
q
.
Theorem 4.
There is a natural bijection from the set of Eulerian circuits
E
(
PD
(
q, m
))
to the set of projective de Bruijn sequences of degree m
+1
.
Proof.
An Eulerian circuit
C
gives a cyclic sequence of arrows, namely, a cyclic
sequence of elements of
P
(
q, m
)
O
. Since the indegree and the outdegree of
O
m
are two,
C
has the subsequence
A
m
+1
,O
m
+1
,B
m
+1
. Take the representative
(0
,...,
0
,
1) for
B
m
+1
, and define (
x
0
,...,x
m
):=(0
,...,
0
,
1). We define
x
m
+1
∈
F
q
so that [
x
1
:
:
x
m
+1
] is the next arrow to
B
m
+1
in the sequence
C
.Thisis
unique, since (
x
1
,...,x
m
) is nonzero. Inductively we define
x
m
+2
,...
, according
to the sequence of arrows in
C
. Then, this process will end just before reaching
to
O
m
+1
at
A
m
+1
, where we have [
x
p−
1
:
x
p
:
···
···
:
x
p
+
m−
2
]=
A
m
+1
for some
p
.
Since the length of
C
is (
q
m
1) + 1, we have
p
=(
q
m
1), and
the sequence
x
0
,...,x
p−
1
with period
p
is a projective de Bruijn sequence, since
by the construction
C
[
m
] consists of
P
(
q, m
). The converse construction of an
Eulerian circuit from a projective de Bruijn sequence is equally easy.
−
1)
/
(
q
−
−
1)
/
(
q
−
Definition 3.
Note that an Eulerian circuit of PD
(
q, m
)
has the subsequence of
vertices A
m
,O
m
,O
m
,B
m
, connected by arrows A
m
+1
,O
m
+1
,B
m
+1
.LetPD
(
q, m
)
be the digraph obtained from PD
(
q, m
)
by removing the arrows A
m
+1
,O
m
+1
,B
m
+1
and the vertex O
m
, and adding an arrow AB
m
+1
from A
m
to B
m
.
The following can be easily shown.
Lemma 2.
PD
(
q, m
)
is a q-regular digraph, and E
(
PD
(
q, m
)) =
E
(
PD
(
q, m
))
holds.
Definition 4.
Suppose m
2
.WeremoveallthearrowsfromA
m
to B
m
in
PD
(
q, m
)
, and then identify A
m
and B
m
(the identified vertex is denoted by
≥
