（环的最大匹配方式有多种这里不予讨论） 设最大匹配数为K ，点数为N 最小点覆盖集：
就是用最少的点集G，使这个图上的所有线段的左端点或右端点属于G 证明： 由于所有最大匹配的线段都不相交，只要取左端点或右端点就可以,所以最大匹配的每一个线段都对应了一个点，一共有K个 因为是最大匹配，不存在增广路，当某两条线段的要取的端点相交时，可以知道那一定不是最大匹配。 最大点独立集：就是用最少
阅读背景：
关于二分图结论的一些证明
来源：互联网
分享到：
