G2 GI G3 Vimax G4 G5 =(VE) Consider the digraph G=(V,E) at the left figure composed of six internally fully connected 1 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 of G; to lowest indexed vertex Vi min of G, (e.g., the edge from Gs to G, 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 G6 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 v2n 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 v, 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 pave p.(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 v,! 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! wel ve G2 GI G3 Vimax G4 G5 =(VE) Consider the digraph G=(V,E) at the left figure composed of six internally fully connected 1 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 of G; to lowest indexed vertex Vi min of G, (e.g., the edge from Gs to G, 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 G6 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 v2n 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 v, 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 pave p.(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 v,! 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! wel ve
