Type:

Other

Description:

The famous blossom algorithm due to Jack Edmonds (1965) finds a maximum matching in a graph. The problem is relatively easy in bipartite graphs through the use of augmenting paths, but the general case is more difficult. The algorithm starts with a maximal matching, which it tries to extend to a maximum matching. The key theorem is that a matching is maximum iff the matching does not admit an augmenting path. The blossom algorithm checks for the existence of an augmenting path by a tree search as in the bipartite case, but with special handling for the odd-length cycles that can arise in the general case. Such a cycle is called a blossom. The blossom can be shrunk and the search restarted recursively. If an augmenting path in a shrunken graph is ever found, it can be expanded up through the blossoms to yield an augmenting path in the original; that alternating path can be used to augment the matching by one edge. And if the recursive process runs into a state where there is no augmenting path, then there is none in the original graph. This Demonstration shows two cases of how blossom-shrinking leads to an augmentation of a maximal matching (red) to a maximum matching (blue).

Subjects:

    Education Levels:

      Keywords:

      EUN,LOM,LRE4,work-cmr-id:262664,http://demonstrations.wolfram.com:http://demonstrations.wolfram.com/TheBlossomAlgorithmForMaximumMatching/,ilox,learning resource exchange,LRE metadata application profile,LRE

      Language:

      Access Privileges:

      Public - Available to anyone

      License Deed:

      Creative Commons Attribution 3.0

      Collections:

      None
      This resource has not yet been aligned.
      Curriki Rating
      'NR' - This resource has not been rated
      NR
      'NR' - This resource has not been rated

      This resource has not yet been reviewed.

      Not Rated Yet.

      Non-profit Tax ID # 203478467