Question

# (a) In the network in Figure 3, it is known that there is a flow of 12. Explain how thatflow can be obtained. State whether that flow is a maximum flow. (b) Calculate \vec{D}\left(S_{2} \bar{S}\right) (c) Explain the difference between a s-t cut and the capacity of a s-t cut. (d) Determine whether the following sets of edges are s-t cut sets for the network inFigure 3. If any set is an s-t cut set then write its capacity. -\{(\mathrm{a}, \mathrm{c}),(\mathrm{s}, \mathrm{c}),(\mathrm{s}, \mathrm{d})\} \{(\mathrm{s}, \mathrm{a}),(\mathrm{s}, \mathrm{c}),(\mathrm{s}, \mathrm{d})\} \text { - }\{(\mathrm{s}, \mathrm{a}),(\mathrm{s}, \mathrm{c}),(\mathrm{d}, \mathrm{t})\} Figure 3: Q4(a),(d): The capacity of the edges (b) and the current flow (a) in each edge isgiven (alb) for each edge. (e) State whether the network in Figure 4 satisfies the two constraints in the net workflow problem. Explain your answer. Figure 4: Q4(e): The capacity of edges (b) and the current flow (a) in each edge is given(alb) for each edge State whether the network in Figure 5 has a perfect matching. Explain your answer. ) The network of Figure 6 (overleaf)has source S, sink T, a capacity on each edge anda capacity on certain vertices (denoted by circled numbers). Convert the network toa basic network with only edge capacities and then use the Ford-Fulkerson algorithm to find the maximum flow from S to T.  Fig: 1  Fig: 2  Fig: 3  Fig: 4  Fig: 5  Fig: 6  Fig: 7  Fig: 8  Fig: 9  Fig: 10  Fig: 11  Fig: 12  Fig: 13  Fig: 14  Fig: 15  Fig: 16  Fig: 17