二分图的最小顶点覆盖和最大独立集和最大团_证明顶点覆盖问题,最大团问题

作者：我家自动化 | 2024-04-07 12:38:40

踩

证明顶点覆盖问题,最大团问题

概念: 如果称选了一个点的话，就覆盖了所有与这点相连的边. 现在要选出最小的点，来覆盖二分图中所有边.

结论: 最小顶点覆盖 = 二分图最大匹配.
证明: Click

概念: 选出一些点，使两两之间没有边，包含顶点数最多的集合称之为最大独立集.

结论: 所有顶点数-最小顶点覆盖.
证明: 因为最小顶点覆盖后。剩下没匹配的点，相互之间一定没有边，否则就可以相连多一条匹配边，与最大匹配相矛盾. 同时因为最小顶点覆盖已经是最小，所以剩下的点一定是最大独立集.

概念: 选出一些点，使两两之间都有边，包含顶点数最多的集合称之为最大团.

结论: 所有顶点数-补图里的最小顶点覆盖.
证明: 由于是最大独立集的反概念，所以在补图中最大团就是最大独立集.
补图就是指原来没边的有边，原来有边的没边了.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/378658

二分图的最小顶点覆盖 和 最大独立集 和 最大团_证明顶点覆盖问题,最大团问题