1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Max Flow / Min Cut (undirected graph)

  1. Mar 30, 2016 #1
    1. The problem statement, all variables and given/known data
    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 ce. 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:

    maxPP* mineP ce = minCC* maxe∈C ce

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

    3. 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.
  2. jcsd
  3. Mar 30, 2016 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted