二分图&&匈牙利算法(二分图基本算法)

2019/03/01 22:01
阅读数 20

二分图

二分图又称作二部图,是图论中的一种特殊模型。

设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。

区别二分图,关键是看点集是否能分成两个独立的点集。如下图所示

image

二分图的最大匹配

给定一个二分图G,在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配. 选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) 如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。

求最大匹配的方法,常用的有匈牙利算法

匈牙利算法

主要思路就是枚举一个点集中的所有点x,对于每个点x,枚举以其为端点的所有点v,若v未被匹配则将x匹配给v,若v已有一点与其匹配,则判断原来匹配给它的点x1是否有其他的点v1可以匹配,就这样一直递归下去,当跑完整个流程时,得到的匹配成功的x数则是二分图的最大匹配!代码如下

//mk[x]表示点x所匹配的点,mark[x]表示x已被走过
bool sp(int x){
    for(int i=0;i<edge[x].size();i++){
        int v=eedge[x][i];
        if(mark[v])continue;
        mark[v]=1;
        if(mk[v]==-1||sp(mk[v])){
            mk[v]=x;
            return true;
        }
    }
    return false;
}
int solve(){
    int ans=0;
    memset(mk,-1,sizeof(mk));
    for(int i=1;i<=n;i++){
        memset(mark,0,sizeof(mark));
        if(sp(i))ans++;
    }
    return ans;
}

二分图的最小顶点覆盖

定理:二分图的最小顶点覆盖等于其最大匹配值

个人是用归纳去理解这理论,首先当只有一个点时,结论肯定成立,当有x个点的二分图时满足条件,假如多增了一个点连向另一点集中的若干个点时,若该点匹配成功,说明这条边是原来的点无法覆盖到的,必须把新增的点选入才能覆盖到新增的边,否则不许选入(自行理解)

二分图的最大独立集

定理:二分图的最大独立集=总点数-最小顶点覆盖

这个较好理解,假设把最小顶点覆盖的点移除图外,剩下的图中是不存在一条边的

二分图的最大团

定理:二分图的最大团=补图的最大团

补图的定义是:对于二分图中左边一点x和右边一点y,若x和y之间有边,那么在补图中没有,否则有。
这个方法很好理解,因为最大独立集是两两不相邻,所以最大独立集的补图两两相邻。

展开阅读全文
amp
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部