Suppose I had a complete bipartite graph with edges each given some numerical "cost" value. Is there a way to select a subset of those edges such that each vertex on each side of the graph is mapped to each vertex on the other (one to one) and the total "costs" is maximized (or minimized)?


Has anyone ever formulated something equivalent to this?



"Bipartite" Travelling Salesman Problem?
You are looking for the max-flow-min-cut theorem: <http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem>


