This is a question from the past paper.

(3) Consider the graphs (1'1 and 02 below. each of which has optimal connectivity. V (i) What is the value of the connectivity of each graph? (ii) These graphs each have two specified vertices labelled s and t. Which of G1, G; provides a more reliable connection between 3 and t? Explain your answer carefully. (b) Consider the following network. (The circled number is a capacity restriction on the vertex D, and the edge EG is undirected.) (i) Transform this network into a basic network. (ii) Use the maximum flow algorithm. as given on the audio-tape. to find the first two flow-augmenting paths from S to T in the basic network. (c) Consider the network N with lower and upper capacities as shown below, (i) Construct the corresponding basic network N*. (ii) Use the basic network N* to obtain a feasible flow in the original network, N. Show this flow on a diagram. (iii) Find a maximum flow and a corresponding minimum cut in N