4
$\begingroup$

enter image description here

Is this graph a tree?


I'm not sure if my answer and especially my reasoning is correct?

A tree is an undirected graph where two arbitrary vertices are connected by exactly one path, e.g. a graph is a tree if it is acyclic and connected. A directed graph is a tree if its undirected form is a tree. So if we consider the graph as an undirected tree, we have that it's cyclic. As example, we have the path $(A,C,D,A)$. Since the undirected graph is not acyclic, it is not a tree. Since the undirected graph is not a tree, its directed form is not a tree. Thus the given directed graph above is not a tree.

Is my reasoning correct and is there an easier / better way to reason it?

$\endgroup$
  • 2
    $\begingroup$ Makes sense to me. $\endgroup$ – Jair Taylor May 24 '18 at 22:15
  • 2
    $\begingroup$ What could be simpler than appealing directly to the definition? A tree is acyclic, this graph (undirected form) has cycles. $\endgroup$ – Morgan Rodgers May 24 '18 at 22:17
1
$\begingroup$

Yeah your reasoning is correct, any graphs containing nodes with more than 1 parent are not trees because of undirected cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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