As shown in this example, the greedy method does not apply to this problem. The third most valuable item is too heavy to be added to the knapsack. Maximal Matching Problem Assume we have a graph made up of two groups of nodes. Every node in Group I is connected to at least one node in Group II and vice versa. However no two nodes in the same group are connected.
Any node can be a member of, at most one pairing.
Graphs of the type described here are called bipartite graphs . Start with a bipartite graph. Choose arbitrary pairings until no additional matches are possible. In this example nodes C, R and S cannot be matched. We exchanges the matched and unmatched edges in this augmenting path to create an additional match.