Directed Graphs: Reflexive, Symmetric, Transitive

8 replies · 6K views · last reply
number0
Messages
102
Reaction score
0

Homework Statement



Hello, I want to make sure that I graphed the directed graphs in my homework correctly. The problems and my work is located in the attachment. I also uploaded the directed graphs onto this link: http://img857.imageshack.us/f/83289329.png/"

Homework Equations



None

The Attempt at a Solution



In attachment + link.

Thanks.
 
Attachments
  • Handwritten grid of six directed graphs on set A = {a, b, c}: symmetric but not transitive; symmetric and transitive but not reflexive; transitive but not symmetric; not reflexive, not symmetric, not transitive; and an equivalence relation with loops at every vertex.
    hw.jpg
    21.6 KB · Views: 1,406
Last edited by a moderator:
micromass said:
(1) and (4) are incorrect. The relation you graphed there are transitive.

I do not understand why (4) is incorrect. But, I did changed somethings.
 
Attachments
  • Handwritten directed graphs on white background: graph 1 has vertices a, b, c with arrows a to b, b to c, c to a, and a back-arrow; graph 4 has vertices a, b, c with arrows a to b, b down to c, and b to c.
    hw.jpg
    4.8 KB · Views: 609
(4) is correct now. But (1) is still incorrect, since (1) is still transitive and it is not symmetric...

Transitive means: if you have an arrow from a to b, and an arrow from b to c, then you must have an arrow from a to c.
 
micromass said:
(4) is correct now. But (1) is still incorrect, since (1) is still transitive and it is not symmetric...

Transitive means: if you have an arrow from a to b, and an arrow from b to c, then you must have an arrow from a to c.

Woops... silly of me. I misread the question. Still I do not understand why the first time I did (1) and (4) I got it wrong.

(1) Is it because I excluded c from a to b and as a result, a to b is transitive?

(4) Is it because I gave them no relationships so a, b, c is nothing?
 
Well, transitive says that IF there is a relation between a and b, and b and c, THEN there is a relation between a and c.

But in your (4), there is no relation between a and b, and b and c, thus transitivity is satisfied. You only need to check transitivity whenever there is a relation, if there is no relation then it is trivially satisfied. Thesame with your (1)...
 
micromass said:
Well, transitive says that IF there is a relation between a and b, and b and c, THEN there is a relation between a and c.

But in your (4), there is no relation between a and b, and b and c, thus transitivity is satisfied. You only need to check transitivity whenever there is a relation, if there is no relation then it is trivially satisfied. Thesame with your (1)...

I see, then for (1), it should be something like this?
 
Attachments
  • Handwritten directed graph with vertices a, b and c; arrows run in both directions between a and b, and between b and c, with the label (1) at top left.
    Untitled.jpg
    3 KB · Views: 515
micromass said:
Yes, that looks fine!

Thank you very much.