Question

For each section, is it TRUE or FALSE?

a) Every DAG is a Directed Forest.

b) Every Directed Forest is a DAG.

c) In a Directed Tree, there is a path from every vertex to every other vertex.

d) Suppose that you search a Directed Graph using DFS from all unvisited vertices, coloring edges red if they go between vertex v and an outgoing neighbor of v that you visit for the first time from v. Then the red edges form a Directed Forest.

e) Suppose that you search a Directed Graph using BFS from all unvisited vertices, coloring edges red if they go between vertex v and an outgoing neighbor of v that you visit for the first time from v. Then the red edges form a Directed Forest.

f) Suppose that a Directed Graph is Strongly Connected, and you search that Directed Graph using DFS starting from any vertex, coloring edges red if they go between vertex v and an outgoing neighbor of v that you visit for the first time from v. Then the red edges form a Directed Tree.

Answer 1

a) FALSE. Every DAG is not a directed forest. For example, take the following DAG: There are 4 nodes A,B,C and D. The edges are - $A\rightarrow B$, $B\rightarrow D$, $A\rightarrow C$ and $C\rightarrow D$. Although it's a valid DAG, it's not a directed forest since D has two parents (B and C).

b) TRUE. Since every Directed Forest has no cycles and has directed edges, they are a subset of the DAG family.

c) TRUE. In a directed tree there is always a path (and only one path) between any two nodes.

d) TRUE. Here I am assuming that your directed graph does not contain self-edges. If there are self edges, these edges form a cycle. In that case, they don't form a forest and the answer would be FALSE. Generally self-edges are ignored.

e) FALSE. Consider a case where the vertex A has two edges to another vertex B. When we perform a DFS (in the previous statement), we consider only one of the edges because after a single DFS, both the vertices are marked as visited. But in this case, where we are performing a BFS, we would consider both the edges from A to B. This would violate the property of the directed forest that for any two nodes, only one path should be available.

f) TRUE. From statement (d) it's evident that a DFS on a directed graph would give rise to a directed forest. But considering a strongly connected graph, every node is connected with every other node. This would mean every node in the DFS forest should be connected. A connected Directed forest is a Directed tree.