Search code examples
algorithmnetwork-flow

Network Flow : True or False


In a directed graph with at most one edge between each pair of vertices, if we
replace each directed edge by an undirected edge, the maximum flow 
value remains unchanged.

Why is it false?

Why and how will flow change?

Thank you.


Solution

  • Because the edge could be the wrong way around. There are more interesting cases, but consider this trivial one:

    S <- T
    

    The flow is zero regardless of the capacity of the edge. If you make it undirected, the flow will be whatever the capacity of the edge is.