G2 Gi G3 14 G6 G4 G5 Q1. (20pts + 20pts + 20 pts = 60pts) G=(VE) Consider the digraph G=(V,E) at the left figure composed of six internally fully connected subgraphs G, i=1,...,6 with V=6n vertices! Each G has n vertices (with indices ranging from (i-1)*n+1 to i*n; vertices of G3: [2n+1, 3n]). The interconnections between subgraphs are always from the highest indexed vertex Vimax of G, to lowest indexed vertex Vimin of G; (e.g., the edge from Gto G2 goes from Vsn to vn+1). The edges are weighted such that all edges of each G;, i=1,...,6 (both within G; and interconnecting) have a weight of i (e.g., each edge within G, and any edge going out of v, has a weight of 1 while each edge within G, and any edge going out of van has a weight of 2). Hint for (a and b): You may apply the algorithms from our online discussions to solve the following problems; but it may be easier to figure out the graph and solve it directly without using the algorithm. a) Find the shortest path to each vertex in G from y, and draw a graph that shows only these paths with the weights for each edge on that graph. b) Find (i.e. draw) one of the minimum spanning trees MST, of the underlying graph of G that minimizes the average distance pre- v1 Ep.(u, v), between all pairs of vertices where p (u, v) is the shortest path between vertices u and y in MST, Show each vertex of G and the connecting edges & weights in your MST. c) Apply depth first search (DFS) to the graph above starting at vz! Disregard the weights of edges for this part of question! Perform your search regarding the vertices'ascending numerical order! Show the final output (order of processed vertices along with the time stamps) of the algorithm! we ye G2 Gi G3 14 G6 G4 G5 Q1. (20pts + 20pts + 20 pts = 60pts) G=(VE) Consider the digraph G=(V,E) at the left figure composed of six internally fully connected subgraphs G, i=1,...,6 with V=6n vertices! Each G has n vertices (with indices ranging from (i-1)*n+1 to i*n; vertices of G3: [2n+1, 3n]). The interconnections between subgraphs are always from the highest indexed vertex Vimax of G, to lowest indexed vertex Vimin of G; (e.g., the edge from Gto G2 goes from Vsn to vn+1). The edges are weighted such that all edges of each G;, i=1,...,6 (both within G; and interconnecting) have a weight of i (e.g., each edge within G, and any edge going out of v, has a weight of 1 while each edge within G, and any edge going out of van has a weight of 2). Hint for (a and b): You may apply the algorithms from our online discussions to solve the following problems; but it may be easier to figure out the graph and solve it directly without using the algorithm. a) Find the shortest path to each vertex in G from y, and draw a graph that shows only these paths with the weights for each edge on that graph. b) Find (i.e. draw) one of the minimum spanning trees MST, of the underlying graph of G that minimizes the average distance pre- v1 Ep.(u, v), between all pairs of vertices where p (u, v) is the shortest path between vertices u and y in MST, Show each vertex of G and the connecting edges & weights in your MST. c) Apply depth first search (DFS) to the graph above starting at vz! Disregard the weights of edges for this part of question! Perform your search regarding the vertices'ascending numerical order! Show the final output (order of processed vertices along with the time stamps) of the algorithm! we ye
