Chapter 7: Relations and Directed Graphs, Equivalence Relations
1. Relations
Definition
Let A and B be two sets. A relation R from A to B is any subset of the Cartesian product (A \times B).
[ R \subseteq A \times B ]
If ((a, b) \in R), we say a is related to b.
Example
Let: [ A = {1, 2, 3}, \quad B = {a, b} ]
[ A \times B = {(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)} ]
A relation: [ R = {(1,a),(2,b)} ]
2. Representation of Relations
(a) Roster Form
List all ordered pairs.
Example: [ R = {(1,1),(2,2),(3,3)} ]
(b) Matrix Representation
For finite sets, relation can be represented by a 0–1 matrix.
[ M_{ij} = \begin{cases} 1 & \text{if } (a_i, b_j) \in R \ 0 & \text{otherwise} \end{cases} ]
(c) Directed Graph (Digraph) Representation
- Elements of set → vertices
- Ordered pair ((a, b)) → directed edge from a to b
3. Directed Graphs (Digraphs)
Definition
A directed graph is a graph in which edges have a direction.
[ G = (V, E) ]
- V = set of vertices
- E = set of ordered pairs (edges)
Relation as a Directed Graph
Any relation on a set A can be represented as a directed graph where:
- Each element of A is a vertex
- ((a, b) \in R) is represented by an arrow from a to b
Example
Let: [ R = {(1,2),(2,3),(3,1)} ]
This corresponds to a directed cycle: [ 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 ]
Loops
If ((a, a) \in R), it is represented by a loop at vertex a.
4. Domain and Range of a Relation
-
Domain: Set of all first elements of ordered pairs [ \text{Dom}(R) = {a \mid (a,b) \in R} ]
-
Range: Set of all second elements [ \text{Ran}(R) = {b \mid (a,b) \in R} ]
5. Properties of Relations
Let R be a relation on a set A.
(a) Reflexive Relation
R is reflexive if: [ (a,a) \in R \quad \forall a \in A ]
Graph Interpretation: Every vertex has a loop.
Example
[ R = {(1,1),(2,2),(3,3)} ]
(b) Symmetric Relation
R is symmetric if: [ (a,b) \in R \Rightarrow (b,a) \in R ]
Graph Interpretation: Edges occur in pairs of opposite directions.
Example
Friendship relation.
(c) Transitive Relation
R is transitive if: [ (a,b) \in R \text{ and } (b,c) \in R \Rightarrow (a,c) \in R ]
Graph Interpretation: If there is a path from a → b → c, then a → c must exist.
(d) Antisymmetric Relation
R is antisymmetric if: [ (a,b) \in R \text{ and } (b,a) \in R \Rightarrow a = b ]
6. Equivalence Relations
Definition
A relation R on a set A is called an equivalence relation if it is:
- Reflexive
- Symmetric
- Transitive
Example 1: Congruence Modulo n
Let: [ a \equiv b ;(\text{mod } n) ] if (n) divides (a - b).
This relation is:
- Reflexive: (a \equiv a)
- Symmetric: (a \equiv b \Rightarrow b \equiv a)
- Transitive: (a \equiv b) and (b \equiv c \Rightarrow a \equiv c)
Example 2: Equality Relation
[ R = {(a,a) \mid a \in A} ]
7. Equivalence Classes
Definition
For an equivalence relation R, the equivalence class of an element a is:
[ [a] = {x \in A \mid (a,x) \in R} ]
Properties of Equivalence Classes
- Every element belongs to exactly one equivalence class
- Two equivalence classes are either equal or disjoint
- Union of all equivalence classes equals the set A
Example
Let A = {0,1,2,3,4,5}, modulo 3:
[ [0] = {0,3},\quad [1] = {1,4},\quad [2] = {2,5} ]
8. Applications in Computer Science
- Database normalization
- State equivalence in automata
- Partitioning data sets
- Compiler optimization
- Network connectivity