Question $6.$

$($a$)$ Find the maximum flow of the network in Figure $3$ using the Ford$-$Fulkerson algorithm. You should show clearly the augmenting path and the resulting residual network after each step, and the final maximum flow $($both the total value and the flow on each edge$).$

$($Note: you must draw the residual networks and you must use the same notations as in the lecture notes. Any alternative notations, textual description of the network, or any textbased "drawings" will not be accepted.$)$

$[13$ marks$]$

$($b$)$ Consider again the network in Figure $3.$ State the value of the cut $\{s,a,b,c\}\{d,e,t\}($they are the set of vertices on the two sides of the cut$).$

$[2$ marks$]$

$($c$)$ The employees of a company are all going to take part in a training event. There are multiple identical sessions of that event taking place in different days. Each employee only need to attend one of the sessions. Each session can only accommodate a certain maximum number of employees to attend. The employees are asked about their availabilities, and you are tasked to assign the employees to one of these sessions based on their availabilities, so that ideally all of them can attend the training.

The following tables shows the availability of the different employees and the dates and capacities of the sessions. $($No sessions are offered on Tuesday and Thursday.$)$

$\backslash$table$[[$Employee$,$Available days$],[$Alice$,$Monday, Tuesday$],[$Bob$,$all days$],[$Carol$,$Wednesday$],[$Dave$,$Tuesday, Thursday, Friday$],[$Eve$,$Wednesday, Thursday, Friday$],[$Fred$,$Monday, Wednesday, Friday$]]$

$\backslash$table$[[$Day$,$Capacity$],[$Monday$,2],[$Wednesday$,2],[$Friday$,2]]$

Version $1$

Page $8$ of $9$

CO$3002/$CO$7002$R

All candidates

Transform this problem into a network flow problem, so that the best allocation can be found from a maximum flow of the transformed network. You only need to draw the transformed network for the particular instance shown in the tables above. There is no need to give a general description, or find the maximum flow or allocation.

$($Note: you must draw the transformed network. Any textual description of the network or the transformation, or any text$-$based "drawings" will not be accepted.$)$

$[5$ marks$]$