Consider the digraph $G=(V,E)$ at the left figure composed of six internally fully connected

subgraphs $G_i,i=1,$dots,$6$ with $|V|=6n$ vertices! Each $G_i$ 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 $v_{i_{\text{m}\text{a}\text{x}}}$ of $G_i$ to lowest indexed vertex $v_{j_{\text{m}\text{i}\text{n}}}$ of $G_j$

$($e$.$g$.,$ the edge from $G_5$ to $G_2$ goes from $v_{5n}$ to $v_{n+1}).$ The edges are weighted such that all

edges of each $G_i,i=1,$dots,$6($both within $G_i$ and interconnecting$)$ have a weight of $i($e$.$g$.,$ each

edge within $G_1$ and any edge going out of $v_n$ has a weight of $1$ while each edge within $G_2$ and

any edge going out of $v_{2n}$ has a weight of $2).$

Hint for 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_1$ 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 $MS{T}_i$ of the underlying graph of $G$ that minimizes the

average distance $p_{\text{a}\text{v}\text{e}}^i=\frac{1}{|V{|}^2}{\displaystyle \underset{\text{u}\text{i}\text{n}\text{V}}{\overset{?}{}}}{\displaystyle \underset{\text{v}\text{i}\text{n}\text{V}}{\overset{?}{}}}{p}_i(u,v),$ between all pairs of vertices where $p_i(u,v)$ is the shortest path between

vertices $u$ and $v$ in $MS{T}_i.$ 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_1!$ 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!