UNIT - V

Equivalence Relation
A relation R on a set A is said to be an equivalence
relation (~) if and only if the relation R is reflexive,
symmetric and transitive.
Reflexive: A relation is said to be reflexive, if (a, a) ∈ R, for
every a ∈ A.
Symmetric: A relation is said to be symmetric, if (a, b) ∈ R,
then (b, a) ∈ R, for every a,b ∈ A.
Transitive: A relation is said to be transitive, if (a, b) ∈ R
and (b, c) ∈ R, then (a, c) ∈ R, for every a,b,c ∈ A

Example:
Reflexive Symmetric Transitive

a ∈ A. a,b ∈ A. a,b,c ∈ A
(a, a) ∈ R if (a, b) ∈ R, then (b,
A={1,2,3} a) ∈ R A={1,2,3} if (a, b) ∈ R and (b, c)
(1,1) ∈ R if (1,2) ∈ R, then (2,1) ∈ R,
(2,2) ∈ R ∈R then (a, c) ∈ R
(3,3) ∈ R if (2,3) ∈ R, then A={1,2,3}
(3,2) ∈ R If (1,2) ∈ R and
1
 (2,3) ∈ R, then
(1,3) ∈ R

Example:

Show that the relation R is an equivalence relation in the set

A = { 1, 2, 3, 4, 5 } given by the relation R = { (a, b):|a-b| is
even }.
Solution :
A = { 1, 2, 3, 4, 5 }
R = { (a, b):|a-b| is even }. Where a, b belongs to A (a,b ∈
A)
Reflexive Property :
Reflexive: A relation is said to be reflexive, if (a, a) ∈ R, for
every a ∈ A.
Given relation is |a-b| is even
From the given relation,
|a – a| = | 0 |=0
And 0 is always even.
Thus, |a-a| is even
Therefore, (a, a) belongs to R

2
Hence R is Reflexive
Symmetric Property :
A relation is said to be symmetric, if (a, b) ∈ R, then (b, a) ∈
R, for every a,b in A.
Given relation is |a-b| is even
From the given relation,
|a – b| = |b – a|
We know that |a – b| = |-(b – a)|= |b – a|
Hence |a – b| is even,
Then |b – a| is also even.

Therefore, if (a, b) ∈ R, then (b, a) belongs to R

Hence R is symmetric
Transitive Property :
|a – b| and |b – c| is even , then |a-c| is even.
Therefore, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) also
belongs to R
Hence R is transitive.

3
Dynamic Equivalence Problem
The equivalence class of an element a is the subset of S
of all elements related to a. Equivalence classes are disjoint
sets.

Now the dynamic equivalence problem can be stated as

to check whether the a~b. Means whether a and b belong to
same equivalence class. The algorithm to find this is
frequently known as the disjoint set union/find algorithm.

Disjoint-set
A disjoint-set data structure is a data structure that keeps
track of a set of elements partitioned into a number of
4
disjoint (non-overlapping) subsets. It means, A pair of sets
which does not have any common element are called
disjoint sets.
S={a,b,c,d,e,f}
S={ S1={a,b,c},S2={e,f}}
S1 ∩ S2 = ϕ (S1,S2 are disjoint sets)

Example , set A={2,3} and set B={4,5} are disjoint sets. But
set C={3,4,5} and d={3,6,7} are not disjoint as both the sets
C and D are having 3 as a common element.
Example: Show that set A={2,5,6} and set B={4,7,8} are
disjoint sets.
Solution: Given:
set A={2,5,6}
set B={4,7,8}
To prove: Set A and Set B are disjoint.
Proof: Two sets are disjoint if their intersection results to the
null set.
Therefore,
A ∩ B = {2,5,6} ∩ {4,7,8}

5
As you can see, A and B do not have any common element.
So, A ∩ B = { }
Hence, proved A and B are disjoint.

The three operations on disjoint sets are:

i. FIND-SET(u): Returns the name of the set containing a

given element

ii. UNION(u,v): given two sets, create a new set that is a

union of both sets (i.e. includes all items of both sets)

Example:
Set A={2,5,6}
Set B={4,7,8}
Union(2,4)
FIND-SET(2) – A set
FIND-SET(4) - B set
Two elements are in two different sets so we can apply
union operation

6
Union(2,4)
S= {2,5,6,4,7,8} – this is considered as new set
Set C={2,5,6}
Set D={4,7,8}
Union(2,6)
FIND-SET(2) – C set
FIND-SET(6) - C set

Two elements are in same set so we can’t apply union

operation

Basic data structure

Various Representations Of Disjoint Set ADT
1. Tree representation
2. Array representation
3. Linked list representation

7
 1. TREE REPRESENTATION
A tree data structure can be used to represent a
disjoint set ADT. Each set is represented by a tree. The
trees do not have to be binary since we only need a
parent pointer. In this representation, two operations
will be used. They are
UNION: To perform a union of two sets, we merge the
two trees by making the root of one tree point to the
root of the other.
Find: It returning the root of the tree.

Example:

S = {1,2,3,4,5,6,7,8} here each element considered as one

set
Eight elements, initially in different sets
S1={1}, S2={2}, S3={3}, S4={4}, S5={5}, S6={6},
S7={7}, S8={8}

UNION (5,6)
Find(5) - 5 (this is root of 5)
8
Find(6) - 6 (this is root of 6)
These two elements are in two different roots, so we can
apply UNION(5,6)
Here UNION operation is to merge the two trees by making the root of
one tree point to the root of the other. After UNION(5,6)

UNION (7.8)
Find(7) - 7 (this is root of 7)
Find(8) - 8 (this is root of 8)
These two elements are in two different roots, so we can apply UNION
(7.8)
Here UNION operation is to merge the two trees by making the root of one
tree point to the root of the other. After UNION (7.8)

UNION (5,7)
9
Find(5) - 5 (this is root of 5)
Find(7) - 7 (this is root of 7)
These two elements are in two different roots, so we can apply UNION
(5,7)
Here UNION operation is to merge the two trees by making the root of one
tree point to the root of the other. After UNION (5,7)

Applications of Union-find Algorithms:

The application of Disjoint set is to check whether a given undirected graph
contains a cycle or not.

Union-Find Algorithm

It can be used to check whether an undirected graph contains cycle or not.

How to find cycle:

 The make set operation makes a new set by creating a new element with
a parent pointer to itself.

10
 Then process each edge of the graph and perform find and Union
operations to make subsets using both vertices of the edge.

 If find operation on both the vertices returns the same parent (means
both vertices belongs to the same subset) then cycle is detected.

Example:

Step1:

11
Step2:

12
Step3:

13
Step4:

14
Step5:

15
Step6:

16
 2. Array representation
This representation assigns one position for each element. An array of
integers, called parent[]. If we are dealing with n items, i’th element of the
array represents the i’th item. More precisely, the i’th element of the array
is the parent of the i’th item. These relationships create one, or more, virtual
trees.

This representation assigns one position for each element. Example:

Initially there are 10 subsets and each subset has one element in it.

When each subset contains only one element, the array is as follows:

Initially, all slots of parent array are initialized to -1

1. Union(2, 1)
Find(2) – 2 (this is root of 2)
Find(1) – 1 (this is root of 1)

17
These twe elements are in different roots. So we can apply Union(2, 1). It
will connect 1 to 2

Here set 1 as root element of 2

Array representation is

2. Union(4, 3)
Find(4) – 4 (this is root of 4)
Find(3) – 3 (this is root of 3)

These twe elements are in different roots. So we can apply Union(4, 3). It
will connect 3 to 4

Here set 3 as root element of 4

18
Array representation is

3. Union(8, 4)
Find(8) – 8 (this is root of 8)
Find(4) – 3 (this is root of 4)

These twe elements are in different roots. So we can apply Union(8, 4)

Here set 3 as root element and 8 will connect to 4

Array representation is

19
 4. Union(9, 3)

Find(9) – 9 (this is root of 9)

Find(3) – 3 (this is root of 3)

These twe elements are in different roots. So we can apply Union(9, 3)

Here set 3 as root element and 9 will connect to 3

Array representation is

20
 5. Union(6,5)
Find(6) – 6 (this is root of 6)
Find(5) – 5 (this is root of 5)

These twe elements are in different roots. So we can apply Union(6, 5)

Here set 5 as root element of 6

Array representation is

21
Algorithm for Union and find
int find(int parent[], int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}

void Union(int parent[], int x, int y)

{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}

3. LINKED LIST REPRESENTATION

All the elements of an equivalence class is maintained in a linked list. The

first object in each linked list is its set's representative. Each object in the
linked list contains a set member, a pointer to the object containing the next
member of the set, and a pointer back to the representative.

Each list maintains head pointer, to the representative, and tail pointer, to
the last object in the list. Within each linked list, the objects may appear in
any order.

22
Example:

Linked-list representations of two sets. Set S1 contains members d, f, and g,

with representative f, and set S2 contains members b, c, e, and h, with
representative c. Each object in the list contains a set member, a pointer to
the next object in the list, and a pointer back to the set object. Each set
object has pointers head and tail to the first and last objects, respectively.

The result of UNION(e, g), which appends the linked list containing e to
the linked list containing g. The representative of the resulting set is f . The
set object for e’s list, S2, is destroyed.

23
Smart union algorithms
The unions above were performed rather arbitrarily, by making the second
tree a subtree of the first.
A simple improvement is always to make the smaller tree a subtree of the
larger, breaking ties by any method; we call this approach union by-size.

Example:

24
union by-size

Array representation of the above tree(using union by-size)

25
Array representation of the above tree(using union by-size)

One more example for union by-size

Union (7,3)
26
Algorithm for Union by size

To implement this strategy, we need to keep track of the size of each tree.
Since we are really just using an array, we can have the array entry of each
27
root c ontain the negative of the size of its tree. Thus, initially the array
representation of the tree is all -1s.When a union is performed, check the
sizes; the new size is the sum of the old.

Thus, union-by-size is not at all difficult to implement and requires no extra

space. It is also fast, on average.

An alternative implementation, which also guarantees that all the trees

will have depth at most O(log n), is union-by-height. We keep track of the
height, instead of the size, of each tree and perform unions by making the
shallow tree a subtree of the deeper tree. This is an easy algorithm, since
the height of a tree increases only when two equally deep trees are joined
(and then the height goes up by one). Thus, union-by-height is a trivial
modification of union-by-size.

Example for union-by-height:

28
Array representation of the above tree(using union by-height)

Array representation of the above tree(using union by-height)

Union by rank: (Union by height)

Uses Find to determine the roots of the trees x and y belong to. If the roots
are distinct, the trees are combined by attaching the root of one to the root
of the other. If this is done naively, such as by always making x a child
of y, the height of the trees can grow as O(n). We can optimize it by using
union by rank.
29
Union by rank always attaches the shorter tree to the root of the taller tree.
To implement union by rank, each element is associated with a rank.
Initially a set has one element and a rank of zero.

If we union two sets and

 Both trees have the same rank – the resulting set’s rank is one larger
 Both trees have the different ranks – the resulting set’s rank is the larger
of the two. Ranks are used instead of height or depth because path
compression will change the trees’ heights over time.

The MakeSet operation makes a new set by creating a new element with a
unique id, a rank of 0, and a parent pointer to itself. The parent pointer to
itself indicates that the element is the representative member of its own set.

Example1: for Normal Union operation

30
Example2: for Union by rank (Union by height)

31
Example3: for Union by rank (Union by height)

32
Union (7,3)

Algorithm for union by rank (Union by height)

33
Path compression

Path compression` is a way of flattening the structure of the tree

whenever Find is used on it. Since each element visited on the way to a root
is part of the same set, all of these visited elements can be reattached
directly to the root. The resulting tree is much flatter, speeding up future
operations not only on these elements, but also on those referencing them.

34
Example1:

35
Example2:

Find(x)- find(9)
Union(0,9)

36
Find(x)- find(6)

Union(0,6)

37
Find(x)- find(3)
Union(0,3)

Find(x)- find(1)
Union(0,1)

38
Algorithm for path compression

Analysis of union/find algorithm

Algorithm for Union by size

39
Example:

Union (7,3)

40
Algorithm for union by rank (Union by height)

41
Example: for Union by rank (Union by height)

Union (7,3)

42
Union by rank properties

43
44
Complexity of Union by rank

 Using link-by-rank, each application of FIND takes O(lg n) steps.

 Starting from an empty data structure with n elements, the

performance of union-find implemented using link-by-rank, for any n
MAKESET and any intermixed sequence of m FIND and UNION
operations is O(n + m lg n) steps.

45
Complexity of path compression
Example:

This implementation of the data structure is the one that reduces the
complexity of making a sequence of m UNION and FIND operations. Key
Observation: Path compression does not create new roots, change ranks, or
move elements from one tree to the another As a corollary, the properties of
Link by rank also hold for this implementation. Notice, the FIND
operations only affect the inside nodes, while the UNION operations only
affect roots. Thus, compression has no effect on UNION operations.

Starting from an empty data structure, path compression with naïve linking
performs any intermixed sequence of m ≥ n MAKE-SET, UNION, and
FIND operations on a set of n elements in O(m log n) time.
46