Representing Relations
What you'll learn: Three different ways to visualize and store the same relation: as a set, a matrix, and a directed graph.
The Core Idea
You already know a relation is a set of ordered pairs from one set to another. But writing out {(a,1), (b,2), (a,3)} gets clumsy fast. Computer scientists use three equivalent representations depending on what they need to do with the relation.
Three Ways to Show the Same Thing
1. Set Notation (What You Know)
The explicit list: R = {(a,b), (c,d), ...}
2. Matrix Representation
Build a table where rows are the first set, columns are the second set. Put 1 where a pair exists, 0 where it doesn't.
Example: Relation R = {(x,2), (x,3), (y,3)} from {x, y} to {1, 2, 3}
1 2 3
x [ 0 1 1 ]
y [ 0 0 1 ]
Each 1 marks an ordered pair in the relation.
3. Directed Graph (Digraph)
Draw dots for elements and arrows for pairs. If (a,b) ∈ R, draw an arrow from a to b.
For the same relation above, you'd draw nodes x, y, 1, 2, 3 with arrows: x→2, x→3, y→3.
Why This Matters
- Sets are precise for definitions
- Matrices are perfect for computation and finding properties
- Graphs make patterns visually obvious
You can translate between any two representations without losing information.
Key Takeaway: A relation can be represented as a set of pairs, a binary matrix, or a directed graph—all three describe exactly the same relationships between elements.