Prove or disprove each of these statements about DAGs: (a) If a directed graph h
ID: 3833266 • Letter: P
Question
Prove or disprove each of these statements about DAGs: (a) If a directed graph has a source, then it is a DAG. (b) If a directed graph has a topological ordering, then it is a DAG. (c) For two distinct vertices u, v in a DAG, if there exists a path from u to v, then there cannot exist a path from v to u. (d) The number of layers in a DAG G is the same as the number of vertices in the longest path in G. (e) In a DAG G where s is a source, there is a path from s to each other vertex v in G. (f) Given a DAG G, for every vertex v in G, there is a path from v to some sink in G.Explanation / Answer
a) No All the Directed Graphs with the source might not be DAG's. Because there are some Directed graphs who comes to the source vertex back when we start from the source and follow the edges i.e. cycles. Only the directed graphs with no cycles are DAG's.
b) Yes, A DAG is a directed graph which is having topological order i.e. every edge from source is directed to next vertex in the sequence.
c) Yes, because DAG means Directed Acyclic Graphs, The name itself tells that the DAG is an acyclic one which means it must not contian Cycles. As mentioned the edge connects u to v in DAG and the same time if another edge connects from v to u then we will get cycle which means it doesn't be a DAG.
d) No, The layers will be different than the no of vertices in longest path. It doen't be the same.
e) Yes, DAG's will have the path to all the other vertexes from source s.
f) Yes, DAG's will have the path from every vetex v to sink G.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.