Modeling: Practice V: Minimum Cost Matchings
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York 11451
1. For the complete graphs on 4 vertices below, find the "perfect" matching of minimum total cost. The cost of a matching is the sum of the weights on the edges of the matching. (A "perfect" matching is a collection of edges which have no vertex in common but includes all the vertices of a graph. Only graphs with an even number of vertices have perfect matchings.)
2. For the complete bipartite graph on 6 vertices below, find the matching of minimum total cost.