526
个编辑
更改
跳到导航
跳到搜索
第108行：
第108行： − +
→Kőnig's theorem and perfect graphs 柯尼希定理和完美图
In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.[16][17] An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices.[18] Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.[16][17] An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices.[18] Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
在二分图中，'''<font color="#ff8000"> 最小顶点覆盖Minimum vertex cover</font>'''（顶点数）等于'''<font color="#ff8000"> 最大匹配数Maximum matching</font>'''(边数)；这就是'''<font color="#ff8000"> 柯尼希定理Kőnig's theorem</font>'''。该定理的另一种等效形式是，'''<font color="#ff8000"> 最大独立集Maximum independent set</font>'''（顶点数）加上最大匹配数等于顶点的数量。在任何没有孤立顶点的图中，'''<font color="#ff8000"> 最小边覆盖Minimum edge cover</font>'''（边数）加上最大匹配数等于顶点数。于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。
在二分图中，'''<font color="#ff8000"> 最小顶点覆盖Minimum vertex cover</font>'''（顶点数）等于'''<font color="#ff8000"> 最大匹配数Maximum matching</font>'''(边数)；这就是'''<font color="#ff8000"> 柯尼希定理Kőnig's theorem</font>'''。该定理的另一种等价形式是，'''<font color="#ff8000"> 最大独立集Maximum independent set</font>'''（顶点数）加上最大匹配数等于顶点的数量。在任意没有孤立顶点的图中，'''<font color="#ff8000"> 最小边覆盖Minimum edge cover</font>'''（边数）加上最大匹配数等于顶点数。于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。