Algorithms & Data Structures (Winter 2021) Graphs – Bipartite Graphs
• Introduction.
• Topological Sort. / Strong Connected Components
Copyright By PowCoder代写 加微信 powcoder
• Network Flow 1. • Introduction
• Ford-Fulkerson
• Network Flow 2. • Min-cuts
• Shortest Path.
• Minimum Spanning Trees. • Bipartite Graphs.
Bipartite Graphs – Problem
Vertices are partitioned into 2 sets. All edges cross the sets.
Bipartite Graphs – Examples
Courses Candidates People
registration employment
Have read/seen
Students Companies Books/Movies
Bipartite Graphs – Is it a bipartite graph?
Assuming G=(V,E) is an undirected connected graph.
1. RunDFSanduseittobuildaDFStree.
2. Colorverticesbylayers(e.g.red&black)
3. Ifallnon-treeedgesjoinverticesofdifferentcolor,thenthegraphisbipartite.
Bipartite matching
Consider an undirected bipartite graph.
A matching is a subset of the edges { (α, β) } such that no two edges share a vertex.
Perfect matching
Suppose we have a bipartite graph with n vertices in each A and B. A perfect matching is a matching that has n edges.
Note: It is not always possible to find a perfect matching.
Complete bipartite graph
A complete bipartite graph is a bipartite graph that has an
edge for every pair of vertices (α, β) such that α∈A, β∈B. 8
The algorithm of happiness
Resident matching program
• Goal: Given a set of preferences among hospitals and medical school students, design a self-reinforcing admissions process.
• Unstable pair: applicant x and hospital y are unstable if: o x prefers y to their assigned hospital.
o y prefers x to one of its admitted students.
• Stable assignment: Assignment with no unstable pairs.
o Natural and desirable condition.
o Individual self-interest will prevent any applicant/hospital deal from being made behind the scenes.
Stable matching problem
Goal: Given n elements of A and n elements of B, find a
“suitable” matching. Participants rate members of opposite set:
• Each element of A lists elements of B in order of preference from best to worst.
• Each element of B lists elements of A in order of preference from best to worst.
A’s preferences B’s preferences
Stable matching problem
• Context: Candidates apply to companies.
• Perfect matching: everyone is matched with a single company. o Each candidate gets exactly one company.
o Each company gets exactly one candidate.
• Stability: no incentive for some pair of participants to undermine assignment by joint action.
o In matching M, an unmatched pair 𝛂-𝛃 is unstable if candidate 𝛂 and company 𝛃 prefer each other to current match.
o Unstable pair 𝛂-𝛃 could each improve by “escaping”.
• Stable matching: perfect matching with no unstable pairs.
• Stable matching problem: Given the preference lists of n
candidates and n companies, find a stable matching (if one exists). 12
Stable matching problem – toy example 1
• Suppose we have a set of two applicants {a1, a2}, and a set of two
companies {c1, c2}. The preference list is as follows.
• a1 prefers c1 to c2
• a2 prefers c1 to c2
• c1 prefers a1 to a2
• c2 prefers a1 to a2
• The list represents complete agreement: the applicants agree on
the order of the companies, and the companies agree on the order
of the applicants.
• There is a unique stable matching, consisting of the pairs (a1, c1) and (a2, c2).
• The other perfect matching (a2, c1) and (a1, c2), would not be a stable
matching, because the pair (a1, c1) would form an instability with respect to this matching.
• Both a1 and c1 would want to leave their respective partners and pair up.
Stable matching problem – toy example 2
• Suppose we have a set of two applicants {a1, a2}, and a set of two
companies {c1, c2}. The preference list is as follows.
• a1 prefers c1 to c2
• a2 prefers c2 to c1
• c1 prefers a2 to a1
• c2 prefers a1 to a2
• The two applicant’s preferences mesh perfectly with each other
(they rank different companies first), and the two companies’ preferences likewise mesh perfectly with each other. But the applicant’s preferences clash completely with the companies’
preferences.
• There are two different stable matchings. 1) The matching consisting of the
pairs (a1, c1) and (a2, c2) and 2) the matching consisting of the pairs (a2, c1) and (a1, c2).
• In 1) both applicants are as happy as possible, so neither would leave
their matched company. In 2) both companies are as happy as possible.
Stable matching problem – toy example 3
Q: Is X-C, Y-B, Z-A a good assignment?
Candidates Y B Companies
Candidates’ preferences Companies’ preferences
Stable matching problem – toy example 3
Q: Is X-C, Y-B, Z-A a good assignment? A: No! Xavier and Baidu will hook up…
Candidates Y B Companies
Candidates’ preferences Companies’ preferences
16 Zoran 16
Stable matching problem – toy example 3
Candidates
Q: Is X-A, Y-B, Z-C a good assignment? A: ?
Y B Companies
Candidates’ preferences Companies’ preferences
Stable matching problem – toy example 3
Q: Is X-A, Y-B, Z-C a good assignment? A: Yes!
Candidates Y B Companies
Candidates’ preferences Companies’ preferences
Stable matching problem
Consider a complete bipartite graph such that |A|=|B|=n.
• Each member of A has a preference ordering of members of B.
• Each member of B has a preference ordering of members of A.
Algorithm for finding a matching:
• Each A member offer to a B, in preference order.
• Each B member accepts the first offer from an A, but then rejects
that offer if/when it receives an offer from a A that it prefers more.
In our example: Candidates applies to companies. Companies accept the first offer they receive, but companies will drop their applicant when/if a preferred candidate applies after.
Note the asymmetry between A and B.
Gale-Shapley algorithm
For each α∈A, let pref[α] be the ordering of its preferences in B For each β∈B, let pref[β] be the ordering of its preferences in A Let matching be a set of crossing edges between A and B
matching®
while there is α∈A not yet matched do
β¬pref[α].removeFirst() if β not yet matched then
matching¬matchingÈ{(α,β)}
return matching
γ¬β’s current match
if β prefers α over γ then
matching¬matching-{(γ,β)}È{(α,β)} 20
Gale-Shapley algorithm – Example
Candidates Y B Companies
Candidates’ preferences Companies’ preferences
Note: In practice, we inverse the roles. Companies makes offers…
Gale-Shapley algorithm – Example
Candidates Y B Companies
Candidates’ preferences Companies’ preferences
Gale-Shapley algorithm – Example
Candidates Y B Companies
Candidates’ preferences Companies’ preferences
Gale-Shapley algorithm – Example
Candidates Y B Companies
Candidates’ preferences Companies’ preferences
Gale-Shapley algorithm – Example
XA Candidates Y B
Candidates’ preferences
Companies’ preferences
Gale-Shapley algorithm – Example
XA Candidates Y B
Candidates’ preferences
Companies’ preferences
Gale-Shapley algorithm – Example
Candidates Y B Companies
Men’s preferences
Companies’ preferences
Gale-Shapley algorithm – Example
XA Candidates Y B
Candidates’ preferences
Companies’ preferences
Gale-Shapley algorithm – Example
Candidates Y B Companies
Candidates’ preferences Companies’ preferences
G-S algorithm – Correctness – Termination
Observations:
1. Candidatesapplytocompaniesindecreasingorderof preference.
2. Onceacompanyismatched,itneverbecomes unmatched; it only “trades up.”
Claim: Algorithm terminates after at most n2 iterations of while loop (i.e. O(n2) running time).
Proof: Each time through the while loop a candidate applies to a new company. There are only n2 possible matches. n
G-S algorithm – Correctness – Perfection
Claim: All candidates and companies get matched. Proof: (by contradiction)
• Suppose, for sake of contradiction, that Zoran is not matched upon termination of algorithm.
• Then some company, say Alphabet, is not matched upon termination.
• By Observation 2 (only trading up, never becoming unmatched), Alphabet never received any application.
• But, Zoran applies everywhere. Contradiction.n
G-S algorithm – Correctness – Stability
Claim: No unstable pairs. Proof: (by contradiction)
• Suppose Z-A is an unstable pair: they prefer each other to the association made in Gale-Shapley matching.
• Case 1: Z never applied to A.
⇒ Z prefers his GS match to A. ⇒ Z-A is stable.
• Case 2: Z applied to A.
⇒ A rejected Z (right away or later) ⇒ A prefers its GS match to Z.
⇒ Z-A is stable.
• In either case Z-A is stable. Contradiction. n
G-S algorithm – Correctness – Optimal
Definition: Candidate 𝛂 is a valid partner of company 𝛃 if there exists some stable matching in which they are matched.
Applicant-optimal assignment: Each candidate receives best valid match (according to his preferences).
Claim: All executions of GS yield an (the same) applicant- optimal assignment, which is a stable matching!
Note: the notation “Applicant-optimal” refers to 𝜶-optimality
Claim: Each element of (𝛽) receive the worst valid partner. GS
finds a company-worst stable matching!
G-S algorithm – Correctness – Optimal
Two stable matchings: and S = { Y-A, X-B, Z-C } and S’ = { X-A, Y-B, Z-C }
• Both X and Y are valid partners for A.
• Both X and Y are valid partners for B.
• Z is the only valid partner for C.
• In S, X Y Z match their best valid partner.
• Introduction.
• Topological Sort. / Strong Connected Components
• Network Flow 1. • Introduction
• Ford-Fulkerson
• Network Flow 2. • Min-cuts
• Shortest Path.
• Minimum Spanning Trees. • Bipartite Graphs.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com