Java Reference
In-Depth Information
equivalence relations
24.1
A
relation R
is defined on a set
S
if for every pair of elements (
a, b
),
a R b
is either true or false. If
a R b
is true, we say that
a
is related to
b
.
An
equivalence relation
is a relation
R
that satisfies three properties.
ab
,
∈
S
,
A
relation
is defined
on a set if every
pair of elements
either is related or
is not. An
equiva-
lence relation
is
reflexive,
symmetric, and
transitive.
1.
Reflexive: a R a
is true for all
a
.
∈
2.
Symmetric: a R b
if and only if
b R a.
3.
Transitive: a R b
and
b R c
implies that
a R c.
Electrical connectivity, where all connections are by metal wires, is an
equivalence relation. The relation is clearly reflexive, as any component is
connected to itself. If
a
is electrically connected to
b,
then
b
must be electri-
cally connected to
a,
so the relation is symmetric. Finally, if
a
is connected to
b
and
b
is connected to
c,
then
a
is connected to
c
.
Likewise, connectivity through a bidirectional network forms equivalence
classes of connected components. However, if the connections in the network
are directed (i.e., a connection from
v
to
w
does not imply one from
w
to
v
),
we do not have an equivalence relation because the symmetric property does
not hold. An example is a relation in which town
a
is related to town
b
if trav-
eling from
a
to
b
by road is possible. This relationship is an equivalence rela-
tion if the roads are two-way.
dynamic equivalence
and applications
24.2
For any equivalence relation, denoted ~, the natural problem is to decide for
any
a
and
b
whether
a
~
b
. If the relation is stored as a two-dimensional array
of Boolean variables, equivalence can be tested in constant time. The problem
is that the relation is usually implicitly, rather than explicitly, defined.
For example, an equivalence relation is defined over the five-element set
. This set yields 25 pairs of elements, each of which either
is or is not related. However, the information that
a
1
~
a
2
,
a
3
~
a
4
,
a
1
~
a
5
, and
a
4
~
a
2
are all related implies that all pairs are related. We want to be able to
infer this condition quickly.
The
equivalence class
of an element is the subset of
S
that contains
all the elements related to
x
. Note that the equivalence classes form a parti-
tion of
S:
Every member of
S
appears in exactly one equivalence class. To
decide whether
a
~
b,
we need only check whether
a
and
b
are in the same
The
equivalence
class
of an ele-
ment
x
in set
S
is
the subset of
S
that
contains all the ele-
ments related to
x.
The equivalence
classes form
disjoint sets
.
{
a
1
a
2
a
3
a
4
a
5
,
,
,
,
}
xS
∈
Search WWH ::
Custom Search