D2 OCR Notes - Matching Problems and Alternating Paths

?

This resource should help with the OCR spec for D2, in particular the area under "Matching Problems".

A bi-partite graph is used, with two sets of vertices containing an equal number of vertices.

A Matching on a bi-partite graph is a set of arcs with the max order of ANY node = 1

A Maximal Matching is a matching that contains the maximum possible number of arcs.

A Complete Matching is a maximal matching, where the number of arcs = number of vertices on one side. This is NOT ALWAYS possible.

This is an example of a Complete Maximal matching on a Bi-partite graph. (http://www.wikihow.com/images/c/ce/Bipartite_graph_6_920.jpg)

Comments

No comments have yet been made