Problem $4.[15$pts$]($Max$-$Flow Problem$)$

There are four job applicants and three jobs, as shown in the table below.

Each applicant is only interested in a subset of the jobs. Each job can only

accept one applicant who is interested in the job, and one applicant can only

perform one job among the interested ones. Find a job$-$applicant matching

solution that maximizes the number of applicants getting jobs.

$($a$)$ Formulate the matching problem as a max$-$flow problem by identifying

a source, a sink, and the intermediate nodes, and then drawing the com$-$

plete network that shows the capacity of each link. $[10$pts$]$

$($b$)$ Solve the formulated max$-$flow problem using the augmenting path al$-$

gorithm or otherwise. It suffices to give the final solution and objective

value. $[5$pts$]$