[Solved] CSDS455 Homework 16-Maximum bipartite matching

Problem 1: Prove that you can reduce the maximum bipartite matching problem to the network flow problem. (Given a bipartite graph, turn it into a flow problem such that the value of the flow equals the maximum matching of the bipartite graph.)

Problem 2: Prove that you can reduce Menger’s Theorem to the network flow problem. (Given a graph, turn it into a flow problem so that the flow size gives the number of vertex disjoint paths of the graph.)

Problem 3: Suppose we have a network (directed graph) D with edge weights (capacities) and with source node s and sink node t. Let S ⊂ V (D) and T ⊂ V (D) be subsets of nodes such that s ∈ S,T but t /∈ S,T. (S,S) is a cut of the network, and cap(S,S) is the sum of weights of edges with their tail in S and head in

1. S. Prove that cap(S ∪ T,S ∪ T) + cap(S ∩ T,S ∩ T) ≤ cap(S,S) + cap(T,T).