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.
