2 3 3 n 4 6 CSE2(0)25 DATA STRUCTURES MAKE-UP EXAM Student Name: Fall 2020 Session #1: 50 minutes Student Number: Q1. (20pts + 15pts + 15pts = 50pts) a) Is topological sort applicable to G G G? If no, discuss why! If yes, apply topological sort to G and GI show the processing order of vertices and the step-by-step content of the queue! Disregard the arc weights only for this part of (a) (b) question! Figure Q1. a) Graph G, b) G's subgraph G1 Consider the weighted digraph G and its subgraph b) Show the shortest path to each vertex in G from vertex 2 G. G is composed of n vertices. The last n-7 by drawing a graph that shows only these paths with vertices (from vertex 8 to n) are in G. The arcs the weights for each are on that graph. (connections) and their weights are as shown in Fig. Q1 (a) where all incoming arcs to G, arrive at c) Find (i.e. draw) one of the minimum spanning trees MST; of vertex 8 and all that leave G, depart from vertex n. the underlying graph of G that minimizes the average As shown in Fig. Q1 (b), there exists an arc in G distance Pave EXP;(u,v), between all pairs of vertices from each vertex i, i E{8,...,n-1}, to each vertex where py(u,v) is the shortest path between vertices u and v in k>i. In other words, there is an arc from a vertex to MST;. Show each vertex of G and the connecting arcs & each higher indexed vertex in Gj. Further all arcs weights in your MST. in G, have a weight of 1. In membeli