POJ3692 最大完全二分子图

    技术2024-10-05  62

    1 、最大独立集+最小点覆盖=顶点数

    1、 最大独立集=顶点数-最大匹配数

    2、最大完全二分子图=补图的最大独立集

    3、独立集:表示集合里任意两边都没有连接关系

    4、补图的独立集(没有连接),反过来正是一个完全图

     

    最新回复(0)