Network Flow: Bipartite graph Bipartite definition from the dictionary: involving or made by two separate parties. Suppose we want to match army officers with available assignments on different bases in different states. There are five officers available and five available assignments. We ask each officer to list the assignments acceptable to them. There is an edge between an officer node and an assignment node if that assignment is acceptable to the officer. A bipartite graph is a graph with two sides T (for top) and B (for bottom) such that all edges go between nodes in T to nodes in B. A matching is a set of edges with no endpoints in common. Ideally, we would want a perfect matching: a matching that connects every point in T with a point in B. Suppose there is no perfect matching, then we would want a maximum matching: a matching with the maximum possible number of edges. We can solve this as follows: (a) Set up a fake start node s connected to all vertices in T. Connect all vertices in B to a fake sink node T. Orient all edges top-to-bottom and give each edge a capacity of 1. (b) Find a max flow from s to t (or minimum cut). (c) Output the edges between T and B that were not cut when determining your minimum cut as the desired matching. This process finds a legal matching because edges from T to B have capacity 1. For a bipartite graph, max flow=min cut is Knig's theorem and Hall's marriage theorem. Now that you understand the process, answer the question is on the next page. Network Flow: Bipartite graph Bipartite definition from the dictionary: involving or made by two separate parties. Suppose we want to match army officers with available assignments on different bases in different states. There are five officers available and five available assignments. We ask each officer to list the assignments acceptable to them. There is an edge between an officer node and an assignment node if that assignment is acceptable to the officer. A bipartite graph is a graph with two sides T (for top) and B (for bottom) such that all edges go between nodes in T to nodes in B. A matching is a set of edges with no endpoints in common. Ideally, we would want a perfect matching: a matching that connects every point in T with a point in B. Suppose there is no perfect matching, then we would want a maximum matching: a matching with the maximum possible number of edges. We can solve this as follows: (a) Set up a fake start node s connected to all vertices in T. Connect all vertices in B to a fake sink node T. Orient all edges top-to-bottom and give each edge a capacity of 1. (b) Find a max flow from s to t (or minimum cut). (c) Output the edges between T and B that were not cut when determining your minimum cut as the desired matching. This process finds a legal matching because edges from T to B have capacity 1. For a bipartite graph, max flow=min cut is Knig's theorem and Hall's marriage theorem. Now that you understand the process, answer the question is on the next page
