How can i draw the transitive closure?
- Thread starter Torrento
- Start date
HallsofIvy
Elite Member
- Joined
- Jan 27, 2012
- Messages
- 7,763
Well, it helps to know what "transitive" means! I say that because you did not give a definition or any other indication that you did. A relation, R, is transitive if, whenever we have aRb and bRc. we also have aRc. And the "transitive closure" of a relation, S, is a relation that is transitive and includes all of S.
So you need to add "arrows" to make this transitive. And that means you need to identify why the given relation is NOT transitive. For example I see an arrow from f to w and an arrow from w to y but NO arrow from f to y! You must add an arrow from f to y. Can you find any other situations like that?
So you need to add "arrows" to make this transitive. And that means you need to identify why the given relation is NOT transitive. For example I see an arrow from f to w and an arrow from w to y but NO arrow from f to y! You must add an arrow from f to y. Can you find any other situations like that?
So i have to draw arrow to anywhere?I mean, f-y,z-w,y-c,z-f?
HallsofIvy
Elite Member
- Joined
- Jan 27, 2012
- Messages
- 7,763
Oh dear, I really should have said that the "transitive closure" of S is the transitive graph that contains S and has the fewest possible new arrows.
Yes, you need an arrow from f to y because there is an arrow from f to w and an arrow from w to y as I said before.
No, you do not need an arrow from z to w because there is NO arrow from z to f which is the only place that has an arrow to w.
No, you do not need an arrow from y to c because there is no place with an arrow from y and an arrow to c. We do NOT have "y to A" and "A to c" for any "A". In fact there is no arrow to c from any place except c itself!
No, you do not need an arrow from z to f because we do not have "z to A" and "A to f" for any "A".
You can make any graph "transitive" by drawing arrow from every place to every place but that would not be the "closure" of the given graph because it would not be minimal (which I admit I forgot to say).
Yes, you need an arrow from f to y because there is an arrow from f to w and an arrow from w to y as I said before.
No, you do not need an arrow from z to w because there is NO arrow from z to f which is the only place that has an arrow to w.
No, you do not need an arrow from y to c because there is no place with an arrow from y and an arrow to c. We do NOT have "y to A" and "A to c" for any "A". In fact there is no arrow to c from any place except c itself!
No, you do not need an arrow from z to f because we do not have "z to A" and "A to f" for any "A".
You can make any graph "transitive" by drawing arrow from every place to every place but that would not be the "closure" of the given graph because it would not be minimal (which I admit I forgot to say).
