Multiple sources and sinks, restricted capacities and optimal flow Quiz

1. Sources P and Q can supply at most $10$ and $7$. What capacities go on the super source arcs?

• A. Both $17$
• B. $10$ on SP and $7$ on SQ
• C. $7$ on SP and $10$ on SQ
• D. Both infinite

2. Vertex $C$ can pass at most $12$ units in total. How is this modelled?

• A. Reduce one arc into $C$ to $12$
• B. Reduce one arc out of $C$ to $12$
• C. Add a super sink
• D. Split $C$ into two vertices joined by an arc of capacity $12$

3. An arc has $[3, 8]$ and carries a flow of $5$. What are its labels (forward, backward)?

• A. $3$ and $2$
• B. $5$ and $3$
• C. $8$ and $5$
• D. $3$ and $5$

4. How is the capacity of a cut with lower capacities found?

• A. Sum of upper capacities from $X$ to $Y$ only
• B. Sum of all lower capacities
• C. Upper capacities from $X$ to $Y$ minus lower capacities from $Y$ to $X$
• D. Upper capacities from $Y$ to $X$ minus lower capacities from $X$ to $Y$

5. Arcs from $X$ to $Y$ have upper capacities $9$ and $6$; an arc from $Y$ to $X$ has lower capacity $2$. What is the cut capacity?

• A. $17$
• B. $15$
• C. $11$
• D. $13$