1
$\begingroup$

I know what it means by the term. However, if I have a relation R = {(1,2),(4,5),(2,3)} on a set A = {1,2,3,4,5}.

I know that straight away by drawing that (1,3) is a transitive edge. But with (4,5) to make the whole relation transitive can we draw an edge (3,5). i.e.

(1,2) and (2,3) -> (1,3) (3,4) and (4,5) -> (3,5) (2,3) and (3,4) -> (2,4) (2,4) and (4,5) -> (2,5) (1,3) and (3,4) -> (1,4) (1,4) and (4,5) -> (1,5)

This would mean R' = {(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}

or is the best way without drawing an extra edge:

R'={(1,2),(1,3),(2,3),(4,5)}

Thanks.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The correct answer is $\{(1,2), (1,3), (2,3), (4,5)\}.$

I can't say I understand your motivation for adding more edges than that. You seem to say the presence of $(3,4)$ and $(4,5)$ implies that $(3,5)$ needs to be there, but that's wrong since $(3,4)$ isn't present. It wasn't there in the first place and you didn't need to add it in the previous step where you (correctly) added $(1,3)$. So you don't need to add $(3,5).$

$\endgroup$
6
  • $\begingroup$ Thanks, I found this as an example but wasn't sure why its so easy. I.e. you just add one edge to make it a closure. The other examples involved a lot more edges. So in the end the transitive closure for the minimal amount of edges is 4? $\endgroup$
    – Fraser Gilbert
    Commented Sep 1, 2020 at 8:16
  • 1
    $\begingroup$ @FraserGilbert There is a procedure (and only one right answer). First you look and see if your graph is transitive. If it is, you're done and the graph itself is the transitive closure. If not, you add all edges whose absence violates transitivity (i.e. edges of the form (a,c) where (a,b) and (b,c) are in the graph). Then you look at the new graph and repeat these steps again. Eventually, after a finite number of iterations, you will have a transitive graph that is the transitive closure of the original graph. Sometimes it will take zero iterations, other times many. This time it took one. $\endgroup$
    – spaceisdarkgreen
    Commented Sep 1, 2020 at 14:36
  • $\begingroup$ Thanks mate. So basically this is two graphs in a sense. We look at the first graph and like yous aid find violations of transitive and then look at the second graph for transitive violations. In my case this is just the first graph with vertices (1,2,3). $\endgroup$
    – Fraser Gilbert
    Commented Sep 1, 2020 at 22:49
  • $\begingroup$ @FraserGilbert No, I don't think you're understanding. Every graph we consider has $5$ vertices. We are just adding edges. The fact that vertices $4$ and $5$ are disconnected from the others doesn't matter. I still don't understand your initial inclination to connect them. My wild guess is that the word "transitive" sounds like it might mean "we can get from one side to the other", and you're assuming it means or implies that. If that's it, erase that association in your brain cause that's nothing remotely close to what "transitive" means. Reread the definition and think about it. $\endgroup$
    – spaceisdarkgreen
    Commented Sep 1, 2020 at 23:20
  • 1
    $\begingroup$ @FraserGilbert (It doesn't help that sometimes the term "transitive" is used in math in a way that does correspond to 'there's a path between any two points', like the definition of a transitive group action.) $\endgroup$
    – spaceisdarkgreen
    Commented Sep 1, 2020 at 23:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .