Course contentsShow
← Computer Science
Lesson 68 of 2,8722. Discrete Mathematics for CSFree lesson

Representing Relations

Represent relations using sets, matrices, and directed graphs; translate between representations.

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.