Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
6 Cards in this Set
- Front
- Back
|
Bipartite Graph |
A graph that has two sets of nodes. Arcs may connect nodes form different sets but never connect nodes in the same set. NB: The number of nodes in each set does not have to be the same. |
|
|
Matching |
The 1 to 1 pairing of some, or all, of the elements of one set, X, with elements of a second set, Y. A matching 'pairs off' nodes. Each nodes can only be paired with one other. |
|
|
Maximal matching |
A matching in which the number of arcs is as large as possible. |
|
|
Alternating path |
A path that starts at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately 'not in' or 'in' the initial matching. |
|
|
Maximum matching algorithm |
1. Start with any initial matching 2. Search for an alternating path 3. If an alternating path can be found, use it to create an improved matching by changing the status of the arcs. If can alternating path cannot be found, stop. 4. List the new matchings, which consists of BOTH the result of applying the alternating path together with any unchanged elements of the initial matching. 5. If the matching is complete, stop. Otherwise return to step 2. |
|
|
How to reach your final matching... |
- Each time you apply the MMA and you find an alternating path, you increase the number of matched pairs by one. - If there is more than one pair of unmatched nodes you will need to find more than one alternating path. - Each subsequent application of the algorithm requires you to start from the current matching. |
