I am completely stuck on this multiple choice trees question. In this multiple-choice question, more than one option can be correct. I believe this is a trees question; if it is not, then I have gone down the wrong rabbit-hole!
Assuming that this question is a trees question , here is my logic/thought-process:
I can confidently eliminate option D as a potential option as through the definition of trees, all trees are graphs.
I think that option A is a potentially correct option as I believe the trees in question satisfy the definition of an asymmetric relation. The definition of an asymmetric relation is as follows: A relation R on a set A is called asymmetric if (a,b) ∈ R implies that (b,a) ∉ R for all a,b ∈ A.
I'm not entirely sure about option B either; if I had to guess, it is incorrect but I'm not fully understanding what message the option is trying to convey.
Please can someone help me with this question as I am absolutely stumped by it.
You can access the question here:
Thank you for reading.
A: It is indeed an asymmetric relation. Recall the graph theoretical interpretation of symmetric relations and assymetric relations. Symmetric relations are when pictured as graphs those relations who where if any arrows appear (not counting loops) the arrows are double-sided and have pointy ends on both ends. Antisymmetric relations are when pictured as graphs those who all arrows if any appear are single-sided.
B: This is correct, and to see why you must first understand what they are talking about and recognize the labels on the points in the image as being relevant. Here, we have as examples $(1,a)$ is a pair in the relation and so too is $(2,m)$. We do have that $1<2$ and we also have that $a$ appears before $m$ in alphabetical order. In order for B to have been false, then we would have needed to have found some examples of numbers $x_1,x_2$ and letters $y_1,y_2$ such that $(x_1,y_1)$ and $(x_2,y_2)$ were pairs in the relation with $x_1<x_2$ while at the same time $y_1$ not appearing before $y_2$. By inspection, no such choices exist which invalidate the statement and so statement B is indeed true. All of the letters associated with $1$ do indeed appear before each letter associated with 2 and similarly before those associated with 3.
C: This is transitive. Do not get fooled by the definition of transitivity which is often written with three variable names that those variables must all refer to different elements. Transitivity says that IF we have an $a,b,c$ (not necessarily distinct) such that $a\sim b$ and $b\sim c$ then these would imply that $a\sim c$. In the event there are no loops and the relation is not reflexive, then we can not ever find examples of $a,b,c$ such that $a\sim b$ and $b\sim c$ and so the relation is vacuously transitive. Even if we were to assume that the pictured relation was reflexive and the loops were just not visibly shown (as is common for Hasse diagrams) we would still have this as transitive. An often better description of transitivity is given in the graph theoretic explanation: To be transitive requires that "If you can go from one point to another along a directed path, possibly involving multiple edges in the process, then there needs to be a direct route as well involving only a single edge." That is clearly the case here as the only possible paths you can take are of length 1 anyways.
D: "The picture depicts a set of directed trees, thus is not a graph" Well... that depends on what specifically is meant. Yes, as pictured since the edges are directed it is a digraph and digraphs are a specific type of object who have a name different than "graph" and so in that sense, yes this is correct... however one could argue that digraphs are graphs with extra information. Saying that it is a digraph and not a graph is like saying that $(\Bbb R,+,\times)$ is a field and not a group like $(\Bbb R,+)$. That gets into more a question of language and depending on who is talking I could believe the argument could go in either way, largely revolving around what the meaning of the word "is" is.