Madeasy 2k17

Question

Caption

Comments

for more study on such kind of problem you can visit here->

1)  https://courses.csail.mit.edu/6.006/oldquizzes/solutions/quiz2-s2011-sol.pdf

2) https://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2008-sol.pdf

Answer 1

a) If a topological sort exists for the vertices in a directed graph, then a DFS on the graph will produce no back edges. 

True because both parts of the statement hold if and only if the graph is acyclic.

b) traversing DFS algorithm on a directed graph G. if we removed all back edges from graph G then resulting graph is the acyclic graph.

True, For example, in graph G = (V, E) = ({a, b, c}, {(a, b),(b, c),(b, a),(c, a)}), there are two cycles ([a, b, a] and [a, b, c, a]) and a DFS from a in G returns two back edges ((b, a) and (c, a)), but a removal of  both back edges can disrupt both cycles, making the resulting graph acyclic.