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?


Return To Problems