I need help with a transitive closure question

Question

the question deals with relations

$R$ is a binary relation defined on $A = \{0,1,2,3\}$.

Let $R = \{(0,1), (0,2), (1,1), (1,3), (2,2), (3,0)\}$.

Find $R^t$, the transitive closure of $R$.

I have the answer but I can't seem to figure out how to get to the answer. The answer: $\{(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,2), (3,0), (3,1), (3,2), (3,3)\}$

I dont understand the order of the points. For example, why is it (1,2) instead of (2,1)?

If anyone knows the steps or a website that can help with transitive closures, I would greatly appreciate it. Thanks!

But there are other good ways that may be more efficient for finite cases. For example, you can iteratively expand the relation by adding in all two-link chains until there are no more to worry about. — dfeuer, Nov 14 '13 at 03:51

Adriano · Answer 1 · 2013-11-14T04:10:16.283

0

Given a relation $R$ defined on some set $A = \{a_1,\ldots,a_n\}$, use the following algorithm to get the transitive closure:

For each k from 1 to n, do the following:
    For each i from 1 to n, do the following:
        For each j from 1 to n, do the following:
            If (a_i,a_k) and (a_k,a_j) are both in R, then do the following:
                Set R := R ∪ {(a_i,a_j)}.

This is a modified version of the Floyd–Warshall algorithm and has running time $O(n^3)$.

Note that if we run this algorithm on your given inputs, we would start by examining $a_1 = 0$. Since $(3,0) \in R$ and $(0,1),(0,2) \in R$, we would set $R:=R \cup \{(3,1),(3,2)\}$. This process repeats for each $a_k$.

edited Nov 14 '13 at 04:10

answered Nov 14 '13 at 04:03

Adriano

41,576

I dont understand the order of the points. For example, why is it (1,2) instead of (2,1)? – Joe Park Nov 14 '13 at 04:14
Since $(1,3),(3,0),(0,2) \in R$, we know that $(1,2) \in R$. Imagine the numbers as vertices and draw an arrow from vertex $i$ to $j$ iff $(i,j) \in R$. Then it makes sense that $(1,2) \in R$ because the path $1 \to 3 \to 0 \to 2$ tells us that there is a path from $1$ to $2$. There is no way to get out of $2$ though; the only ordered pair in $R$ with $2$ as the first coordinate is the "loop" $(2,2)$. – Adriano Nov 14 '13 at 04:21
so how do you know where to start? – Joe Park Nov 14 '13 at 04:33
Did you read my answer? I said: "...we would start by examining $a_1 = 0$. Since $(3,0) \in R$ and $(0,1),(0,2) \in R$, we would set $R:=R \cup {(3,1),(3,2)}$." Can you see how to do the next iteration? – Adriano Nov 14 '13 at 08:16

I need help with a transitive closure question

1 Answers1