图论 杂..

    xiaoxiao2021-03-25  151

    二分图

    最小顶点覆盖等于最大匹配 证明:

    所有的边分为匹配的(A)边和不是匹配的边(B),最小点覆盖的点集就是要每条匹配的边两端顶点中的一个,

    比如现在有x1-y1属于A,x1-y2属于B,对于x1-y1这条匹配边取x1而不取y1,这样就能覆盖到x1-y2,即B也能覆盖到。

    例题:poj3041

    转载请注明原文地址: https://ju.6miu.com/read-7360.html

    最新回复(0)