D2 OCR Notes - Matching Problems and Alternating Paths
- Created by: Goonerginge
- Created on: 05-03-15 20:44
Fullscreen
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.
…
Comments
No comments have yet been made