Question
The Gallai-Edmonds decomposition partitions a graph into three sets based on the structure of these things. The size of these things is given by the Tutte-Berge formula. The first known algorithm for finding these things in polynomial time works by recursively contracting odd length cycles, which are called “blossoms”. It’s not flow, but most algorithms that find these things work by repeatedly finding alternating paths that begin and end at free vertices and augmenting those paths until there are none left. The Hopcroft-Karp algorithm finds these things, which are equivalent to minimum vertex covers by Kőnig's theorem. If all edges in a bipartite graph have capacity 1, then finding a (*) max flow is trivially equivalent to finding one of these things. For 10 points, give this term for the largest set of edges in a graph that shares no common vertex, which therefore pairs up the most possible vertices. ■END■
ANSWER: maximum cardinality matchings [prompt on “matchings”; accept maximal matchings; accept perfect matchings] (While perfect matchings are technically different from maximum matchings, we are accepting it because they are very similar concepts and the terms are sometimes used interchangeably for bipartite graphs.)
<AW>
= Average correct buzz position
| Conv. % | Power % | Average Buzz |
|---|
| 60% | 40% | 72.33 |
Back to tossups