**Modeling: Practice V: Minimum Cost Matchings**

Prepared by:

Joseph Malkevitch

Department of Mathematics and Computer Studies

York College (CUNY)

Jamaica, New York 11451

email:

__malkevitch@york.cuny.edu__

web page:

__http://york.cuny.edu/~malk/__

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.