Science!: Difference between revisions
Created page with "Standard bipartite graph construction. Binary search on the maximum possible flow which can be met (chaning capacity from source->people, and from button->sink)> This is not necessarily tight bound? Have to demonstrate that even with this value, that we can actually construct a valid assignment. Remove unused edges with no loss of generality. Consider node A and B which should be paired with W, X in round one, and X, Y in round two. Then consider they are paired with W,..." |
No edit summary |
||
| Line 1: | Line 1: | ||
Standard bipartite graph construction. Binary search on the maximum possible flow which can be met (chaning capacity from source->people, and from button->sink)> | Standard bipartite graph construction. Binary search on the maximum possible flow which can be met (chaning capacity from source->people, and from button->sink)> | ||
This is not necessarily tight bound? | This is not necessarily tight bound? If we remove unused edges, the resulting graph of n matches is n regular. it is a "well known" result that an n-regular bipartite graph has n perfect matchings. Finding any one of them leaves us with an n-1 regular bipartite graph, which must have n-1 perfect matchings. | ||
Proof: | |||
1. Let G be a bipartite graph with all degrees equal to k. Show that G has a perfect matching. | |||
Solution: Fix any set X, and consider N(X). The number of edges coming out of X is exactly | |||
k|X|, but each vertex in N(X) can only absorb ≤ k many of them. So |N(X)| ≥ |X|, and we have | |||
Hall’s condition. | |||
https://www.math.cmu.edu/~lohp/docs/math/mop2009/graph-theory-more.pdf | |||
https://www.math.cmu.edu/~ | |||
[[Category:ICPC Problems]] | [[Category:ICPC Problems]] | ||
Latest revision as of 06:27, 27 February 2024
Standard bipartite graph construction. Binary search on the maximum possible flow which can be met (chaning capacity from source->people, and from button->sink)>
This is not necessarily tight bound? If we remove unused edges, the resulting graph of n matches is n regular. it is a "well known" result that an n-regular bipartite graph has n perfect matchings. Finding any one of them leaves us with an n-1 regular bipartite graph, which must have n-1 perfect matchings.
Proof: 1. Let G be a bipartite graph with all degrees equal to k. Show that G has a perfect matching. Solution: Fix any set X, and consider N(X). The number of edges coming out of X is exactly k|X|, but each vertex in N(X) can only absorb ≤ k many of them. So |N(X)| ≥ |X|, and we have Hall’s condition.
https://www.math.cmu.edu/~lohp/docs/math/mop2009/graph-theory-more.pdf