Matchings

Question 1

What is a matching?

Answer 1

A one to one pairing of elements from one set to another set

Question 2

What is a complete matching?

Answer 2

A matching in which every vertex from both sets is paired with another vertex

Question 3

What is a maximal matching?

Answer 3

A matching in which the number of edges is as large as possible

Question 4

Describe the maximal matching algorithm

Answer 4

Start at an unmatched vertex from set X, and find an alternating path which ends at an unmatched vertex from set Y—a path whose edges alternate between not being in the initial matching and being in the initial matching. Once this has been found, swap the state of each edge in the alternating path. Repeat this entire process until either a complete matching is found, or no alternating path exists, indicating a maximal matching has been found

Question 5

How is an alternating path represented?

Answer 5

A “—” is used to mean a vertex can become matched with another vertex, while a “=” is used when a vertex is already matched with another vertex. If there are multiple choice of vertices to go to, the path simply splits into multiple branches