Information Technology Reference
In-Depth Information
possibly having parallel arcs and self-loops, is defined by a set
V
(
D
)
of vertices,
aset
A
(
D
)
of arcs and by two maps
s
D
and
t
D
that assign to each arc two ele-
ments of
V
: a source and a target (in general, the subscripts will be omitted).
A
symmetric
digraph
D
is a digraph endowed with a symmetry, that is, an invo-
lution
Sym
:
A
(
D
)
(
D
)
→
A
(
D
)
such that for every
a
∈
A
(
D
)
,
s
(
a
)=
t
(
Sym
(
a
))
and
Sym
(
Sym
(
a
)) =
a
. Given a simple connected graph
G
, a vertex labeling function
(
(
)
,
λ
,
δ
)
λ
, and a port-numbering
δ
, we will denote by
Dir
G
the labeled digraph
(
)
constructed in the following way. The vertices of
Dir
G
are the vertices of
G
and
(
,
λ
)
{
,
}
they have the same labels as in
G
. Each edge
u
v
is replaced by two arcs
a
)
,
a
)
∈
A
(
Dir
(
G
))
such that
s
(
a
)
)=
t
(
a
)
)=
u
,
t
(
a
)
)=
s
(
a
)
)=
v
,
(
u
,
v
(
v
,
u
(
u
,
v
(
v
,
u
(
u
,
v
(
v
,
u
δ
(
a
(
u
,
v
)
)=(
δ
u
(
v
)
,
δ
v
(
u
))
,
δ
(
a
(
v
,
u
)
)=(
δ
v
(
u
)
,
δ
u
(
v
))
and
Sym
(
a
(
u
,
v
)
)=
a
(
v
,
u
)
(See
Fig.
12.1
).
Fig. 12.1
Agraph
G
, the corresponding digraph Dir(
G
), and its minimum-base
H
from
D
to
D
satisfying the fol-
A
covering projection
is a homomorphism
ϕ
lowing: (i) For each arc
a
D
)
of
A
(
and for each vertex
v
of
V
(
D
)
such that
v
=
a
)
a
.
ϕ
(
v
)=
t
(
there exists a unique arc
a
in
A
(
D
)
such that
t
(
a
)=
v
and
ϕ
(
a
)=
(ii) For each arc
a
of
A
D
)
v
=
a
)
(
and for each vertex
v
of
V
(
D
)
such that
ϕ
(
v
)=
s
(
a
. A symmet-
ric digraph
D
is a
symmetric covering
of a symmetric digraph
D
via a homomor-
phism
there exists a unique arc
a
in
A
(
D
)
such that
s
(
a
)=
v
and
ϕ
(
a
)=
is a covering projection from
D
to
D
such that for each arc
a
ϕ
if
ϕ
∈
A
(
D
)
,
ϕ
(
.
Adigraph
D
is
symmetric-covering-minimal
if there does not exist any graph
D
not isomorphic to
D
such that
D
is a symmetric covering of
D
. The notions of
coverings extend to labeled digraphs in an obvious way: the homomorphisms must
preserve the labeling. Given a simple labeled graph
Sym
(
a
)) =
Sym
(
ϕ
(
a
))
(
G
,
λ
)
with a port-numbering
δ
,
(
,
λ
,
δ
)
(
(
)
,
λ
,
δ
)
we say that
G
is symmetric-covering-minimal if
Dir
G
is symmetric-
(
,
λ
)
covering-minimal. For any simple labeled graph
G
with a port-numbering
δ
,
(
,
μ
)
(
(
)
,
λ
,
δ
)
there exists a unique digraph
D
such that (i)
Dir
G
is a symmetric
D
covering of
(
D
,
μ
)
and (ii)
(
D
,
μ
)
is symmetric-covering-minimal. This labeled
D
D
digraph
(See Fig.
12.1
).
The main result that we will use from the theory of graph coverings is the fol-
lowing. Given an environment
(
D
,
μ
)
is called the
minimum base
of
(
G
,
λ
,
δ
)
D
(
G
,
λ
,
χ
p
,
δ
)
, if the corresponding labeled digraph
(
Dir
(
G
)
,
μ
G
)
is not symmetric-covering-minimal, i.e.
(
Dir
(
G
)
,
μ
G
)
covers a smaller
digraph
(
H
,
μ
H
)
, then the vertices of
G
can be partitioned into equivalence classes,
Search WWH ::
Custom Search