Question 1. (1 marks) Consider the directed graph G with nodes {1,2, 3, 4,5,6,7) that is represented by its adjacency lists A(1) 6,7,4 A(2)-6 A(3) = 1.4 A(4) 6 A(5) 2,6 A(6) NIL A(7) 5,2, 4 a. Draw a Depth-First Search forest generated by the DFS of G under the following assumptions: the DFS starts at node 1 and it erplores the edges in the order of appearance in the above adjacency lists, and all the vertices are erplored. Do not draw forward, back, or cross edges. Show the discovery and finishing times d[u] and f[u] of every node u of G, as computed by this DFS of G b. How many back edges, forward edges, and cross-edges are found by the above DFS? c. Suppose the graph G above represents seven courses and their prerequisites. For example, A(1) - 6,7,4 means that course 1 is a prerequise for i.e., it must be taken before) courses 6, 7 and 4; and A(6) NIL means that course 6 is not a prerequisite for any course. Using Part (b) above and a theorem that we learned in class, prove that it is possible to take all the courses in a sequential order that satisfies all the prerequisite requirements. State the theorem that you use in your argument; do not give a d. Now list the courses in an order they can be taken without violating any prerequisite. To do so you must use your DFS of Part (a) and an algorithm that we covered in a tutorial. e. Draw a Breadth-First Search tree of G that starts at node 3 and explores the edges in the order of appearance in the above adjacency lists specific course o rder here Question 1. (1 marks) Consider the directed graph G with nodes {1,2, 3, 4,5,6,7) that is represented by its adjacency lists A(1) 6,7,4 A(2)-6 A(3) = 1.4 A(4) 6 A(5) 2,6 A(6) NIL A(7) 5,2, 4 a. Draw a Depth-First Search forest generated by the DFS of G under the following assumptions: the DFS starts at node 1 and it erplores the edges in the order of appearance in the above adjacency lists, and all the vertices are erplored. Do not draw forward, back, or cross edges. Show the discovery and finishing times d[u] and f[u] of every node u of G, as computed by this DFS of G b. How many back edges, forward edges, and cross-edges are found by the above DFS? c. Suppose the graph G above represents seven courses and their prerequisites. For example, A(1) - 6,7,4 means that course 1 is a prerequise for i.e., it must be taken before) courses 6, 7 and 4; and A(6) NIL means that course 6 is not a prerequisite for any course. Using Part (b) above and a theorem that we learned in class, prove that it is possible to take all the courses in a sequential order that satisfies all the prerequisite requirements. State the theorem that you use in your argument; do not give a d. Now list the courses in an order they can be taken without violating any prerequisite. To do so you must use your DFS of Part (a) and an algorithm that we covered in a tutorial. e. Draw a Breadth-First Search tree of G that starts at node 3 and explores the edges in the order of appearance in the above adjacency lists specific course o rder here
