This is not the document you are looking for? Use the search form below to find more!

Report

# Bipartite Graph Matching Algorithm

Document Description
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.
File Details
Submitter
• Name: nishagoyal
• Documents: 327
Embed Code:

Related Documents

## Beyond Westermarck: Can Shared Mothering or Maternal Phenotype Matching Account for Incest Avoidance?

by: shinta, 21 pages

Westermarck’s Hypothesis (WH) is widely accepted amongst evolutionary scientists as the best explanation of human incest avoidance. Although WH may account for incest avoidance ...

## QUANTIFICATION OF ETHANOL'S ANTIPUNISHMENT EFFECT IN HUMANS USING THE GENERALIZED MATCHING EQUATION

by: shinta, 20 pages

Increases in rates of punished behavior by the administration of anxiolytic drugs (called antipunish- ment effects) are well established in animals but not humans. The present study examined

## QUANTIFICATION OF DRUG CHOICE WITH THE GENERALIZED MATCHING LAW IN RHESUS MONKEYS

by: shinta, 16 pages

The generalized matching law provides precise descriptions of choice, but has not been used to characterize choice between different doses of drugs or different classes of drugs. The current ...

## MATCHING UNDER NONINDEPENDENT VARIABLE-RATIO SCHEDULES OF DRUG REINFORCEMENT

by: shinta, 12 pages

Response-contingent deliveries of oral pentobarbital maintained responding of 3 rhesus monkeys during daily 3-hr sessions. Deliveries of pentobarbital were arranged under nonindependent ...

## Price-Quality Trade-Offs in Choice Versus Matching: New Insights Into the Prominence Effect

by: shinta, 21 pages

Seemingly equivalent preference assessment procedures (e.g., choose between a 400 Safeway brand cola and a 550 Coke) and matching (e.g., a Safeway brand cola costs 400; at what price ...

## graph

by: xcode, 36 pages

graph

## Algorithm

by: Armand Rochette, 1 pages

Algorithm

## sleep graph

by: Chivalry, 5 pages

apnea graph

## LeadFormix Publishes Study Report On The Impact of Google Algorithm Change On B2B Companies

by: merlinf, 2 pages

LeadFormix, a provider of next-generation marketing automation solutions which help align Marketing and Sales teams in B2B organizations announced today that it is making available its research ...

## Accu Chek Small Record Book With Graph

by: tegan, 24 pages

Accu Chek Small Record Book With Graph

Content Preview
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.

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 .

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
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

• ﾿

Bipartite Graph Matching Algorithm

Share Bipartite Graph Matching Algorithm to:

example:

http://myblog.wordpress.com/
or
http://myblog.com/

Share Bipartite Graph Matching Algorithm as:

From:

To:

Share Bipartite Graph Matching Algorithm.

Enter two words as shown below. If you cannot read the words, click the refresh icon.

Share Bipartite Graph Matching Algorithm as:

Copy html code above and paste to your web page.