Search for question
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