# Data Structures: Graph Theory- Bipartite Matching

Page 1 of 1

## 0 Replies - 38071 Views - Last Post: 23 December 2012 - 07:52 PMRate Topic:     //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=304719&amp;s=7bee8d76d0d01f2ffb2965520cf388e5&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• 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

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
v.child = 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

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }