Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

alt text

  1. The answer for this turns out to be only irreflexive. However, how is this not transitive? The definition I have for transitive states "whenever there is a path from x to y then there must be a direct arrow from x to y". So for the above graph, if there exists a path from one point to another, then there should be a direct arrow. Well that appears to be the case for the above image, no? Theres a path from C to B, and there is a direct arrow. There is no path from C to E, so no arrow needed. No path from B to C, B to D, so no arrows needed here. There is a path from Z to A and there is also a direct arrow, and same for A to Z. Am I misunderstanding this?

  2. The Wikipedia article for transitive relation says:

For a transitive relation the following are equivalent:

  • Irreflexivity
  • Asymmetry
  • Being a strict partial order

Does this mean that if a relation is transitive, then it is also irreflexive? If thats the case, then shouldn't the above graph then be transitive?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

However, how is this not transitive?

There is an edge from Z to A and one from A to Z, but no edge from Z to itself or from A to itself.

Does this mean that if a relation is transitive, then it is also irreflexive?

No, it means that if a transitive relation is irreflexive, it is also asymmetric and a strict partial order (and if it is asymmetric, it is also irreflexive etc.).

So if the graph was transitive, its irreflexivity would imply that it's also antisymmetric, but since the graph is not transitive, this does not apply.

share|improve this answer
    
Ok so in order for a vertex to be transitive, it HAS to have a self-loop? And I dont understand what you mean by the second part. Your definition is not obvious from the Wikipedia definition. –  maq Nov 27 '10 at 20:49
    
@fprime: No, for a graph to be transitive there has to be an Edge from A to C if there is an Edge from A to B and one from B to C (for any A, B, C). In this case there is an edge from A to Z and one from Z to A, so there also needs to be one from A to A. –  sepp2k Nov 27 '10 at 20:52
    
As for the second part: I just restated what the article said in different words. –  sepp2k Nov 27 '10 at 20:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.