A weighted and directed network diagram is shown.
- What is the outflow from vertex \(C\) ? (1 mark)
--- 2 WORK AREA LINES (style=lined) ---
- Calculate the maximum flow through the network. (2 marks)
--- 5 WORK AREA LINES (style=lined) ---
- The capacity of ONE saturated edge is to be increased in order to produce a new network with the maximum possible flow.
- State an edge which could have an increased capacity AND find the new maximum flow through this new network. (2 marks)
--- 3 WORK AREA LINES (style=lined) ---
a. \(\text{Inflow of \(C\) = Outflow of \(C\) = 14}\)
b. \(\text{Method 1:}\)
\(\text{Minimum cut through}\ \ sC-Bt-At:\)
\(\text{Maximum flow} = 14+20+11=45\)
\(\text{Method 2:}\)
\(sAt\ \ 11\ \text{(leaving an excess flow capacity of } s A=11 \text { )}\)
\(sABt\ \ 11\ \text{(leaving an excess flow capacity of } AB=7 \text { and } B t=9 \text { )}\)
\(sBt\ \ 9\ \text{(leaving an excess flow capacity of } s B=7 \text { )}\)
\(sCt\ \ 14\ \text{(leaving an excess flow capacity of } C t=3)\)
\(\text{Maximum Flow} = 11+11+9+14=45\)
c. \(\text{Answers could include one of the following:}\)
\(\text{B} t \ \text{could be increased (by 7) leading to a maximum flow of 52.}\)
\(\text{A} t \ \text{could be increased (by 11) leading to a maximum flow of 52.}\)
a. \(\text{Inflow of \(C\) = Outflow of \(C\) = 14}\)
b. \(\text{Method 1:}\)
\(\text{Minimum cut through}\ \ sC-Bt-At:\)
\(\text{Maximum flow} = 14+20+11=45\)
\(\text{Method 2:}\)
\(sAt\ \ 11\ \text{(leaving an excess flow capacity of } s A=11 \text { )}\)
\(sABt\ \ 11\ \text{(leaving an excess flow capacity of } AB=7 \text { and } B t=9 \text { )}\)
\(sBt\ \ 9\ \text{(leaving an excess flow capacity of } s B=7 \text { )}\)
\(sCt\ \ 14\ \text{(leaving an excess flow capacity of } C t=3)\)
\(\text{Maximum Flow} = 11+11+9+14=45\)
c. \(\text{Answers could include one of the following:}\)
\(\text{B} t \ \text{could be increased (by 7) leading to a maximum flow of 52.}\)
\(\text{A} t \ \text{could be increased (by 11) leading to a maximum flow of 52.}\)