QUESTION $3$

Complete the pseudocode for Max$-$Bipartite$-$Matching. The input is a bipartite graph $G=(V,E)$ with vertex partition $V=LR.$ Use inf for $$ if needed.

Max$-$Bipartite$-$Matching$($L$,$R$,$E$)$

Construct the graph $G^{\text{'}}$ as follows.

Let $V^{\text{'}}=LR\{s,t\},E^{\text{'}}=\frac{O}{?}$ and $M=\frac{O}{?}$

for each vertex vinL

add $(s,)to{E}^{\text{'}}$ with capacity

for each vertex vinR

add $($

$,$ t$)$ to $E^{\text{'}}$ with capacity

for each edge $\{u,v\}inE,$uinL,vinR

add $($

to $E^{\text{'}}$ with capacity

Compute the max flow in $G^{\text{'}}$

for each edge in $E^{\text{'}}$ with flow equal to $()$ add its equivalent to $M$

return $M$