Bipartite Graph Matching Algorithm
Bipartite Graph Matching Algorithm
The Marriage Problem and Matchings
Suppose that in a group of n single women and n single men who desire to get
married, each participant indicates who among the opposite sex would be
acceptable as a potential spouse. This situation could be represented by a
bipartite graph in which the vertex classes are the set of n women and the set of n
men, and a woman x is joined by an edge to a man y if they like each other. For
example we could have the women Ann, Beth, Christina, Dorothy Evelyn, and
Fiona, and the men Adam, Bob, Carl, Dan, Erik, and Frank. If Ann liked Adam and
Bob, (and vice-versa), Beth liked Adam and Carl, Christina liked Dan, Erik and
Frank, Dorothy liked Bob, Evelyn liked Adam and Dan, and Fiona liked Frank, we
would have the following bipartite graph. In this situation could we marry
everybody to someone they liked? This is one version of the Marriage Problem.
Since polygamy and polyandry is not allowed, every woman can be married to at
most one man, and every man to at most one woman. Therefore, a possible set of
marriages can be represented as a subset M of the edges, no two of which are
adjacent. Such a set of edges is called a matching in the Graph.
Know More About :- convert radians to degrees


Tutorcircle.com
PageNo.:1/4

---

In other words, a matching is a set of vertex-disjoint edges. A matching is called
perfect if every vertex is incident to an edge of the matching. Thus the marriage
problem can be stated in graph-theoretic terms as asking if a given bipartite graph
G has a perfect matching. (We could think of a perfect matching as perfect
because it maximizes marital bliss.)
In the example considered above indeed there is a perfect matching: we could
marry Ann to Adam, Beth to Carl, Christina to Erik, Dorothy to Bob, Evelyn to Dan,
and Fiona to Frank. But in some other situations a perfect matching may be
impossible. If that is the case, we still may be interested to nonetheless extend
the benefits of marriage to the largest number of people in the group. So we may
want to find a maximum matching, that is one with maximum cardinality. This
latter generalization of the Marriage Problem is called the Maximum Matching
Problem. It has the advantage that it could be applied even if the number of
women and men in the group were not the same. In this section we shall develop
an efficient algorithm for both the Marriage Problem and the Maximum Matching
Problem.
Hall's Theorem
We remark first that if there exists a perfect matching then it must be true that for
any subset of the women the number of men that they collectively like must be at
least as large as the number of women in the subset. For if this is not true then
clearly a perfect macthing is impossible. This is called Hall's condition, discovered
by Philip Hall in 1931. Hall proved that this obvious necessary condition is also
sufficient to insure a perfect matching.
Hall's Theorem: Given a bipartite graph G=(V,E) with vertex classes X and Y, G has
a perfect matching if and only if for every subset S of X, |Adj(S)| >= |S|, where
Adj(S) denotes the set of vertices adjacent to some vertex of S .
Learn More :- Algebraic Functions


Tutorcircle.com
PageNo.:2/4

---

We will present a proof of Hall's Theorem later. For now we just remark that it
does not directly give us an efficient algorithm, because to check Hall's condition
would require examining all 2n subsets of X. In fact, it seems that because Hall's
condition is both necessary and sufficient, it dooms any chance of finding an
efficient algorithm. Though this is certainly plausible, it turns out to be false.
In Dijkstra's algorithm we succeeded in finding an efficient algorithm by following
a strategy in which successive improvements to a partial solution lead to an
optimal solution. Could we apply a similar approach for the marriage problem? Let
us suppose that M is a matching, if M is not a maximum matching, how could we
improve it by finding a larger one?
For example, we might want to try this in the case we already discussed. So
suppose we have the matching Ann married to Bob, Beth to Adam, Christina to
Dan, and Fiona to Frank. Dorothy, Evelyn, Carl and Erik are unmatched. At first
sight it appears that we are stuck, because Dorothy only likes Bob, and he is
already matched, and Evelyn likes only Adam and Dan, both of whom are
matched. To make progress we must be willing to rearrange our existing
matchings, in order to increase their number. But how?
Let us start with a currently unmatched woman, say Dorothy. Now we could
reason as follows: to match Dorothy we must marry her to Bob; but Bob is
matched to Ann; maybe we could match Ann to someone else; well, we could
match Ann to Adam instead, but Adam is already matched to Beth; so if we do
that we must match Beth to someone else; we could match Beth to Carl. Carl is
currently unmatched so we found a better matching! The new matching then is
Dorothy to Bob, Ann to Adam, Beth to Carl, plus Christina to Dan, and Fiona to
Frank who weren't affected by our rearrangement.


Tut
Tu o
t rc
r i
c rc
r l
c e
l .
e c
. o
c m
Pa
P ge
g
e No
N ..::2/
3 3
/4

---

ThankYouForWatching
Presentation

---

Document Outline

• 
• ﾿
• 

---