0 Replies - 17467 Views - Last Post: 23 December 2012 - 07:52 PM Rate Topic: -----

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10647
  • View blog
  • Posts: 39,542
  • Joined: 27-December 08

Data Structures: Graph Theory- Bipartite Matching

Posted 23 December 2012 - 07:52 PM

This tutorial will introduce the concept of bipartite matching, including an algorithm to find the maximal matching and minimal cover of a bipartite graph.

First, let's define some terms. A matching is a set of edges in a Graph that do not share vertices. A cover is a vertex set that touches every edge.

Next, let's examine a couple facts about matches and covers in bipartite graphs. The first fact is that |Matching| <= |Cover|. This can be proven by defining a one-to-one function f:Matching -> Cover. Suppose that there are two distinct edges (a and b) in the Matching. By the definition of a cover, at least one of the vertices incident to each edge is in the cover. If f(a) = f(b), then a and b share a common vertex. Thus, M isn't an actual matching. We have reached a contradiction. Thus, |Matching| <= |Cover|.

The second fact is that if the matching is maximal and the cover is minimal, then |Matching| = |Cover|. The proof for this is algorithmic. To explore this more, it is necessary to introduce an M-Augmenting path. An M-Augmenting path is a path where the end-point edges are unmatched, and every other edge is matched. Let a * mark a matched edge.

An M-Augmenting path looks like:
A -- B -*- C -- D



It has an interesting property. Take every unmatched edge and match it, and take every matched edge and unmatch it. The new path looks like:
A -*- B -- C -*- D



Notice that the new path is also a valid matching, as no matched edge shares a vertex. However, there is now an additional matched edge. This is the basis of the maximal matching algorithm.

Consider an initial matching in adjacency matrix form:
X/Y | 1 | 2 | 3 | 4 | 5 |
 A  | 1   1*   
 B  | 1*      1
 C  |     1       1*
 D  | 1               1



Here, the horizontal and vertical axes each represent a set of vertices in the bipartite graph.

The algorithm accepts an arbitrary initial matching, and returns the maximal matching. The first step is to iterate over each Y vertex (A, B, C, D) and create a forest containing Y vertices that aren't matched. The next step is, for each vertex in the forest, add the adjacent vertices from matched edges, so long as the vertices aren't already in the forest. Repeat the last step, except add adjacent, unmatched X vertices. This process repeats until no new vertices can be added to the tree. If there is an M-Augmenting path, use it to augment the matching, then create a new forest. This process continues until no more M-Augmenting paths can be created.

In Pseudo-Code:
boolean augmentMatching(Matching m)
   X <- m.X //the X vertex set
   Y <- m.Y //the Y vertex set

   forest <- new Tree[]
   lastVertices <- new Vertex[] 
   findMatchedEdges <- false
   
   for each vertex in X
       if vertex is unmatched
          tree <- new Tree
          tree.root = vertex
          forest.add(tree)

          lastVertices.add(vertex)
       end if
   end for

   while lastVertices.length > 0 
       lastVertices = new Vertex[] //reset the vertex set

       foreach vertex v in lastVertices
            foreach adjacent vertex r in v AND Y
              if r is NOT in forest AND 
                 findMatchedEdges == isMatchedAdjacency(r, v)
                     v.child = r
                     lastVertices.add(r)         
                  end if
            end foreach
       end foreach

       findMatchedEdges = NOT findMatchedEdges
   end while

   augmentingPath <- forest.getAugmentingPath()

   //if there is no M-Augmenting Path
   if augmentingPath is NULL
       return
   end if

   foreach edge in augmentingPath
       if edge.isMatched()
          edge.unmatch()
       end if

       else
          edge.match()
       end else      
   end

   augment(m)
end function



Now, let's work through an example, given the Matching:
X/Y | 1 | 2 | 3 | 4 | 5 | 6
 A  | 1   1   1*   
 B  | 1               1*
 C  |     1*      1       1
 D  |                 1   1*
 E  | 1                   1
 F  | 1               1   1



The only unmatched Vertex in the X set are E and F, so those are the only vertices in the forest.

Next, let's find the Y vertices that are adjacent to E and F. Note that the edges will be unmatched, but the vertices have matched edges. So the forest looks like:
           E          F
         /  \         |
        1    6        5



Next, let's find the matched edges of 1, 6, and 5 and add them to the tree. The vertices will be in the X set and cannot already be in the tree. The updated forest looks like:
           E          F
         /  \         |
        1    6        5
        *    *        *
        A    D        B



This process repeats, until the forest is flushed out to:

           E          F
         /  \         |
        1    6        5
        *    *        *
        A    D        B
       / \
      2   3
      *
      C



The only M-Augmenting path is E -- 1 -*- A --3. Inverting that increases the matching to, though the new path: E -*- 1 -- A -*- 3.
X/Y | 1 | 2 | 3 | 4 | 5 | 6
 A  | 1   1   1*   
 B  | 1               1*
 C  |     1*      1       1
 D  |                 1   1*
 E  | 1*                  1
 F  | 1               1   1



Running the algorithm again gives the forest:
        F
      / | \
     1  5  6
     *  *  *
     E  B  D



Thus, there are no additional M-Augmenting Paths, so the algorithm is complete. This means the maximal matching is as follows: {E1, C2, A3, B5, D6}. The minimal cover must also have 5 elements. The formula for the minimum cover is {Unmatched X Verices} + {Found Y Vertices}. So the found Y in the last forest were {1, 5, 6} and {A, C} were the unfound X vertices. So the minimal cover is {A, C, 1, 5, 6}.

Is This A Good Question/Topic? 0
  • +

Page 1 of 1