[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 Mengers 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).