Discussion Problems, 05/07, CS40, UCSB, 08S

The following exercises may seem pointless without some explanation in advance. So here's the best explanation I can give as to why they are not pointless, but actually quite useful.

Transistive closure is a really useful graph algorithm
To understand transitive closure, we need the notion of what R^*is (R raised to the * power).
To understand R^*, we need Rⁿ
To understand Rⁿ, we need to understand R ◦ R
To understand R ◦ R, it is easier to start with S ◦ R

So, here we go:

Notation: S ◦ R

Read this as (R composed with S, or the composite of R and S)

No, that's not a typo. S ◦ R is read as the composite of R and S. You read it "backwards" because you have to apply R first, and then S.

Here's an example of how it works.

Example:

Let A = {1, 2, 3}. Let B = {x, y, z}. Let C = {d, e, f}

Let R be a relation from A to B, and S be a relation from B to C.

Hence R ⊆ (A × B) and S ⊆ (B × C)

So, suppose R = {(1,x), (2,y), (3,y)} and S = {(x,f), (y,d), (z,e) }

Then the definition of S ◦ R is this:

S ◦ R = { (a,c) | (a ∈ A) ∧ (c ∈ C) ∧ (∃ b ∈B) ( (a,b) ∈ R ∧ (b,c) ∈ S ) }

So, in this case, S ◦ R = {(1,f), (2,d), (3,d)}

Now you work a few. In each of these problems:

Let A = {1, 2, 3}. Let B = {x, y, z}. Let C = {d, e, f},
Let R ⊆ (A × B)
Let S ⊆ (B × C)

Let R={(1,x), (2,x)} Let S = {(x,f), (x, e)}. What is S ◦ R ?
Let R={(1,x),(1,y),(1,z)}. Let S = {(z,d), (z,e)}. What is S ◦ R ?
Let R={(1,x),(1,y),(1,z)}. Let S = {(x,d), (z,d), (y,d)}. What is S ◦ R ?

Now, consider the set A={1,2,3,4,5)}, and let R ⊆ (A ×A). Now, applying the definition of S ◦ R to the case of R ◦ R, we get:

R ◦ R = { (a,c) | (a ∈ A) ∧ (c ∈ A) ∧ (∃ b ∈A) ( (a,b) ∈ A ∧ (b,c) ∈ A ) }

So, if R is {(1,2), (2,3), (2,5), (5,1), (5,4)}, then R ◦ R is {(1,3),(1,5),(2,1),(2,4),(5,2) }

Now, you work a few. In each of these problems,

Let A={1,2,3,4,5)}, and let R ⊆ (A ×A).

Let R={(1,2),(2,3),(3,4),(4,5),(5,1)}. What is R ◦ R?
Let R={(1,2),(2,3),(2,4),(2,5),(3,1),(4,1),(5,1)}. What is R ◦ R?
Let R ={(1,2),(3,4),(5,2)}. What is R ◦ R?

Now, define:

R¹ = R
R² = R ◦ R
R³ = (R ◦ R) ◦ R

In general, define (recursively):

R¹ = R, and for n≥1, Rⁿ⁺¹ = Rⁿ ◦ R

With that in mind, try these problems:

Let A={1,2,3,4,5)}, and let R ⊆ (A ×A).

Let R be the same as in problem 4 above. (So, your answer to problem 4 was R². What is R³?
Continuing from #7, what is R⁴?
Now, let R be the same as in problem 5 above. What is R³?
Continuing from #9, what is R⁴?
Now, let R be the same as in problem 6 above. What is R³?
Continuing from #11, what is R⁴?
Now, let's go back to the set from problem 5, 9, and 10, and represent it as a graph, like this:

In this case, what do R, R², R³, and R⁴ represent in terms of the graph?

Now, suppose we had a set A with k elements in it (i.e. |A| = k)
Consider what would happen if we took R¹∪ R²∪ R³ ∪ … and so on to infinity.

First, would this set be finite, or infinite?
What is the maximum number of elements that could possibly be in that set
Suppose we let R^* be the symbol for this set, that is:

Then what does it mean for (a,b) to be an element of R^*?
(Think in terms of the graph representation).
Suppose you build up R^* by starting with R, and then adding R², R³, R⁴, etc. into R^*, and you finally reach R^k, where k is |A|

It turns out that this is as far as you need to go. Although R^* is defined to be an infinite union, beyond R^k, it is impossible for anything new to be added into R^*. Why is this so? (It may help to think in terms of the "graphical meaning" of R², R³, R⁴, etc.)

After completing these exercises, re-read the following pages in your textbook: p. 526 and 527, p. 541, 542, 544-549. After having done these exercises above, the reading in the chapter should make a lot more sense.

P. Conrad, 05/07/2008