3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Snowman
    Commented Nov 27, 2010 at 20:49
  • $\begingroup$ @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. $\endgroup$
    – sepp2k
    Commented Nov 27, 2010 at 20:52
  • $\begingroup$ As for the second part: I just restated what the article said in different words. $\endgroup$
    – sepp2k
    Commented Nov 27, 2010 at 20:54

You must log in to answer this question.

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