Course Forum

Bipartite Matching relevant for the exam?

Re: Bipartite Matching relevant for the exam?

by Sofia Tirabassi -
Number of replies: 0

Bipartite matching is relevant (that is migh appear in some exams).

 
Even without exercise seesion it not difficult to reconduce the problem to a max flow min cut problem.
 
The idea is that you add a soource and a sink to the graph, the sorce connected with all the vertex in one set of the partition, the sink connected with all the veritices of the other set. The directions of edges is toward the sink. The capacity of edges is 1 from the soruce or to the sink, and big enough (you can set it infinity) for the other edges.
 
You get a complete matching (or a maximum matching) just by finding a max flow on the network above. The main difficulty is to find the  max flow. So for me bipartite matching exercise are just exercises on max flow/ min cut.