Matchings
A matching is a bi-partite graph in which each vertex is connected to at most one other vertex.
A maximal matching is a matching in which the number of edges is as large as possible.
A complete matching is a matching when there are n vertices in each group, and n edges in the matching.
Alternating Path Algorithm
This algorithm is used for improving bi-partite matchings.
- Start with a reasonable [easy to spot] matching
- Choose a vertex that isn't in the matching
- Draw in edges from the original graph which aren't included in the matching [for this, use a black line]
- From these draw in edges which are in the matching [use a red line]
- Continue the alternating process until either:
- You reach a previously unconnected vertex, or
- You get stuck
- Include those new edges in your matching. Check if it is maximal, if not repeat algorithm
i) is called a breakthrough. In this case, you swap all the connections [on that arm of the linkage diagram].
ii) means there is no way of improving the current matching.
It is very important that you LABEL and ANNOTATE your matchings, otherwise you will get NO MARKS:
Remember!
You must label "Using the....from vertex C" and "change the status..." everytime you start a new link!
- Show initial matching and label "Initial Matching"
- Say "Using the Alternate Path Algorithm, starting from vertex A"
- Diagram of paths (include the colour key!)
- Must have labels of "breakthrough" / "stuck"
- (Breakthrough)Say: "Changing the status of the edges" and re-draw
- Draw diagram of improved matching