## Short Answer - Maximum Flow

We are using the flow augmenting path algorithm for the maximum flow
problem. We use a labeling algorithm to find flow augmenting paths. The
source is node *s* and the sink is node *t*. The labeling algorithm
terminates and the sink is not labeled. We find that the nodes in the set
*S* are labeled and the nodes in the set *T* are
not labeled. We identify four sets of arcs: {*S*, *S*},
{*T*, *T*}, {*S*, *T*},
{*T*, *S*}. Say as much as you can about the flows
in each of the four sets of arcs.

The notation {*A*, *B*} means the set of arcs
that have origin nodes in the set *A* and terminal nodes in
the set *B*.

Consider arc *k* (*i*, *j*) such that *i* is a node
in *S* and *j* is in *T*. What can you say
about this arc. Prove the result is general.

Consider arc *k* (*i*, *j*) such that *i* is a node
in *T* and *j* is in *S*. What can you say
about this arc. Prove the result is general.

Say you have identified a minimal cut using the flow-augmenting algorithm.
How can you find out if this is the only minimum cut?

Say the network has several minimum cuts. You wonder if there are two
disjoint cuts (no arcs in common). How could you use your labeling algorithm
to test if there are two disjoint cuts?

Say we have arc flows that determine a maximum flow through a network.
We enumerate all arcs that have flow at capacity. Are all these arcs in
the minimal cut? Are all these arcs in some minimal cut?

Say we divide the nodes of the network in two disjoint sets of nodes
*A* and *B* such that *s* is in *A*
and *t* is in *B*. Is {*A*, *B*}
a cut? Flows have been assigned to the arcs that deliver the maximum flow
from *s* to *t*. Define *f* (*A*, *B*)
as the sum of the flows on arcs that pass from *A* to *B*.
Is there any relation between *f* (*A*, *B*)
and the value of the maximum flow?

In the naïve flow-augmenting algorithm we start with 0 flows on
all arcs and use the labeling algorithm to find augmenting paths. At each
iteration we erase all the labels. We take the first path we discover as
the flow-augmenting path. Can you suggest any ways to speed up this process?

Say a network has *n* nodes. Allowing only one arc between any pair
of nodes there could be as many as *n* (*n *- 1)/2 arcs in the
network. We know the values of the capacities on all the arcs. Can you give
an order statement on the number of steps to perform the algorithm?

Say you have a computer program find the shortest path between any two
nodes in a directed network. Say you have some set of flows that provides
a flow *v* from *s* to *t*. The flow may or may not be the
maximum flow. How could you use this algorithm to find a flow-augmenting
path?