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.

Question image 1Question image 2Question image 3Question image 4Question image 5Question image 6Question image 7Question image 8Question image 9Question image 10Question image 11Question image 12Question image 13Question image 14Question image 15Question image 16Question image 17