Information Technology Reference
In-Depth Information
A binary relation
R
is
reflexive
if for all
a
∈
A
,
aRa
.Itis
symmetric
if for all
a
,
b
∈
A
,
aRb
if and only if
bRa
.Itis
transitive
if for all
a
,
b
,
c
A
,if
aRb
and
bRc
,then
aRc
.
A binary relation
R
is an
equivalence relation
if it is reflexive, symmetric, and transitive.
For example, the pairs
(
a
,
b
)
,
a
,
b
∈
, for which both
a
and
b
have the same remainder on
division by 3, is an equivalence relation. (See Problem
1.3
.)
If
R
is an equivalence relation and
aRb
,then
a
and
b
are said to be
equivalent elements
.
We l e t
E
[
a
]
be the set of elements in
A
that are equivalent to
a
under the relation
R
and
call it the
equivalence class
of elements equivalent to
a
. It is not difficult to show that for all
a
,
b
∈
A
,
E
[
a
]
and
E
[
b
]
are either equal or disjoint. (See Problem
1.4
.) Thus, the equivalence
classes of an equivalence relation over a set
A
partition the elements of
A
into disjoint sets.
For example, the partition
∈
of the set
(
0
+
1
)
∗
of binary strings
defines an equivalence relation
R
. The equivalence classes consist of strings containing zero or
more 0's, strings starting with 0 and containing at least one 1, and strings beginning with 1. It
follows that 00
R
000 and 1001
R
11 hold but not 10
R
01.
0
∗
,0
(
0
∗
10
∗
)
+
,1
(
0
+
1
)
∗
}
{
1.2.5 Graphs
A
directed graph
G
=(
V
,
E
)
consists of a finite set
V
of distinct
vertices
and a finite set
of pairs of distinct vertices
E
V
called
edges
.
Edge
e
is incident on vertex
v
if
e
contains
v
.Adirectedgraphis
undirected
if for each edge
(
v
1
,
v
2
)
in
E
the edge
(
v
2
,
v
1
)
is also in
E
.Figure
1.2
shows two examples of directed graphs, some of whose vertices are
labeled with symbols denoting gates, a topic discussed in Section
1.2.7
.Inadirectedgraph
the edge
(
v
1
,
v
2
)
is directed from the vertex
v
1
to the vertex
v
2
, shown with an arrow from
v
1
to
v
2
.The
in-degree
of a vertex in a directed graph is the number of edges directed into it; its
out-degree
is the number of edges directed away from it; its
degree
is the sum of its in- and
out-degree. In a directed graph an
input vertex
has in-degree zero, whereas an
output vertex
either has out-degree zero or is simply any vertex specially designated as an output vertex. A
walk
in a graph (directed or undirected) is a tuple of vertices
(
v
1
,
v
2
,
...
,
v
p
)
with the property
that
(
v
i
,
v
i
+
1
)
is in
E
for 1
⊆
V
×
1. A walk
(
v
1
,
v
2
,
...
,
v
p
)
is
closed
if
v
1
=
v
p
.A
path
is a walk with distinct vertices. A
cycle
is a closed walk with
p
≤
i
≤
p
−
−
1 distinct vertices,
p
≥
3.
The
length of a path
is the number of edges on the path. Thus, the path
(
v
1
,
v
2
,
...
,
v
p
)
has
length
p
−
1. A
directed acyclic graph (DAG)
is a directed graph that has no cycles.
v
8
v
6
v
7
v
5
+
+
v
3
v
4
v
4
v
5
v
1
v
2
v
3
v
1
v
2
(a)
(b)
Figure 1.2
Two directed acyclic graphs representing logic circuits.
Search WWH ::
Custom Search