$(26$ pts$)$ Treat the following two parts independently.

a$)$ Suppose that Dijkstra's shortest path algorithm is being applied to the network presented in Figure $1($where all

arc lengths are positive$),$ to determine the shortest paths between node A and all other nodes. At the end of the

third iteration the lengths of the shortest paths between A and $B,D,G$ have been determined as $2,5,10$ units

respectively $($i$.$e$.$ the permanent labels of nodes $B,D,G$ are $2,5,10$ respectively$).$ Say True, False or Maybe to the

following statements; provide a brief explanation.

i$)$ The shortest path to $H$ must pass through $G.$

ii$)$ The shortest path to $G$ must pass through $D.$

iii$)$ The lenght of the arc $(A,C)$ is greater than $10.$

iv$)$ The lenght of the arc $(B,D)$ is $3.$

b$)$ Suppose Figure$1$ represents a transportation network where it is desired to maximize the flow from $A$ to $H.$ At

a particular iteration of the maximum flow algorithm $($the one discussed in class$),$ a total current flow of $34$ units is

reached and the corresponding residual network $($i$.$e$.$ showing maximum possible additional flow changes on

individual arcs$)$ are shown in Figure $2.$ Answer the following questions.

i$)$ Is it possible to increase the total flow from $A$ to $H?$ If yes, show how to increase it; if no$,$ explain why not.

ii$)$ Identify the minimum cut between A and $H,$ using the method described in class. That is$,$ give the set of

vertices defining the cut and the set of arcs in the cut. What is the capacity of this minimum cut? $($Give it without

computing the capacities on each individual arc$)$

Fig $2$