论文标题
将匹配映射到最小顶点封面：重新审视Kőnig的定理
Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited
论文作者
论文摘要
在早期组合学中，这是一个著名的结果，在两部分图中，最大匹配的大小等于最小顶点盖的大小。 Kőnig证明了这一事实提供了一种算法，可从最大匹配中找到最小顶点盖。在本文中，我们重新审视了这种算法在两种类型的结构之间诱导的联系。我们发现，可以通过将此算法应用于某些匹配，然后在将此算法应用到它们时，可以找到所有最小顶点盖，然后将此匹配范围分类为最小的顶点盖。
It is a celebrated result in early combinatorics that, in bipartite graphs, the size of maximum matching is equal to the size of a minimum vertex cover. Kőnig's proof of this fact gave an algorithm for finding a minimum vertex cover from a maximum matching. In this paper, we revisit the connection this algorithm induces between the two types of structures. We find that all minimum vertex covers can be found by applying this algorithm to some matching and then classify which matchings give minimum vertex covers when this algorithm is applied to them.
