Prove or disprove each of these statements about DAGs: (a) If a directed graph h
ID: 3836251 • 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) this statement is false, disprove:- because a DAG has many vertices and edges where all the vertices are structureless such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again.
(b) it's true, proof:-DAG is a directed graph that has a topological ordering, a sequence of the vertices such that every edge is directed from earlier to later in the sequence.A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way.
(c) this statement is true, proof:- as stated earlier a graph is said to be DAG when it does not have any cycle, and if there exists a path from v to u then it becomes a cycle hence if there exists a path from u to v then there can not be a path from v to u.
(d)this statement is true, proof:- The family of topological orderings of a DAG is the same as the family of linear extensions of the reachability relation for the DAG.
(e)this is true, proof:- A vertex v of a directed graph is said to be reachablefrom another vertex u when there exists a path that starts at u and ends at v.
(f) this statement is false, disprove:- because if such thing happens then directed graph gets a cycle which is not possible for DAG
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.