Max Flow / Min Cut (undirected graph)

[goraemon]

Homework Statement

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

Designate G = (V, E) as an undirected graph that has at least two vertices. Every edge e on this graph has capacity c_e. Pick two arbitrary vertices from G and label them s and t respectively.

Now, we'll let P* be the set of s-t paths in the graph, and let C* be the set of s-t cuts -- meaning, C* refers to the subset of edges in G that constitute all possible s-t cuts.

Demonstrate that the following equality is true:

max_P∈P* min_e∈P c_e = min_C∈C* max_e∈C c_e

Homework Equations

Size of Max Flow = Min. Capacity of an s-t Cut

The Attempt at a Solution

My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.

Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.

 

[Ray Vickson]

Homework Statement

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

Designate G = (V, E) as an undirected graph that has at least two vertices. Every edge e on this graph has capacity c_e. Pick two arbitrary vertices from G and label them s and t respectively.

Now, we'll let P* be the set of s-t paths in the graph, and let C* be the set of s-t cuts -- meaning, C* refers to the subset of edges in G that constitute all possible s-t cuts.

Demonstrate that the following equality is true:

max_P∈P* min_e∈P c_e = min_C∈C* max_e∈C c_e

Homework Equations

Size of Max Flow = Min. Capacity of an s-t Cut

The Attempt at a Solution

My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.

Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.

For a given path $P$, the largest flow that can be transmitted along that path equals the smallest arc capacity along the path. This is readily apparent: to send $f$ units of flow along the path, you must send $f$ units along each arc in the path, so $f$ cannot be bigger than the smallest arc-capacity in that path. You can actually achieve a flow equal to the smallest arc capacity, so you have a true minimum, not just a lower bound.