| course |
course_year |
question_number |
tags |
title |
year |
Optimization |
IB |
64 |
|
Paper 2, Section I, H |
2013 |
Given a network with a source $A$, a sink $B$, and capacities on directed arcs, define what is meant by a minimum cut.
The $m$ streets and $n$ intersections of a town are represented by sets of edges $E$ and vertices $V$ of a connected graph. A city planner wishes to make all streets one-way while ensuring it possible to drive away from each intersection along at least $k$ different streets.
Use a theorem about min-cut and max-flow to prove that the city planner can achieve his goal provided that the following is true:
$$d(U) \geqslant k|U| \text { for all } U \subseteq V,$$
where $|U|$ is the size of $U$ and $d(U)$ is the number edges with at least one end in $U$. How could the planner find street directions that achieve his goal?
[Hint: Consider a network having nodes $A, B$, nodes $a_{1}, \ldots, a_{m}$ for the streets and nodes $b_{1}, \ldots, b_{n}$ for the intersections. There are directed arcs from $A$ to each and from each $b_{i}$ to $B$. From each $a_{i}$ there are two further arcs, directed towards $b_{j}$ and $b_{j^{\prime}}$ that correspond to endpoints of street $i .]$