文档章节

二分图

Airship
 Airship
发布于 2017/09/08 10:01
字数 663
阅读 11
收藏 0

0 定义

    设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。也就是说在二分图中,顶点可以分为两个集合X和Y,每一条边的两个顶点都分别位于X和Y集合中。如下图所示:

二分图

1 最大匹配
    在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数.如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。如果在左右两边加上源汇点后,图G等价于一个网络流,二分图最大匹配问题可以转为最大流的问题。解决此问的匈牙利算法的本质就是寻找最大流的增广路径。上图中的最大匹配如下图红边所示:

二分图

2 最优匹配

最优匹配又称为带权最大匹配,是指在带有权值边的二分图中,求一个匹配使得匹配边上的权值和最大。一般X和Y集合顶点个数相同,最优匹配也是一个完备匹配,即每个顶点都被匹配。如果个数不相等,可以通过补点加0边实现转化。一般使用KM算法解决该问题。

 

3 最小覆盖

二分图的最小覆盖分为最小顶点覆盖和最小路径覆盖:

①最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联,二分图的最小顶点覆盖数=二分图的最大匹配数;

②最小路径覆盖也称为最小边覆盖,是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数=|V|-二分图的最大匹配数;

 

4 最大独立集

    最大独立集是指寻找一个点集,使得其中任意两点在图中无对应边。对于一般图来说,最大独立集是一个NP完全问题,对于二分图来说最大独立集=|V|-二分图的最大匹配数。如下图中黑色点即为一个最大独立集:

二分图



 

本文转载自:http://blog.sina.com.cn/s/blog_60707c0f010105yd.html

共有 人打赏支持
Airship
粉丝 38
博文 908
码字总数 19854
作品 0
南京
高级程序员
私信 提问
复杂网络分析库NetworkX学习笔记(5):二分图

二分图又称二部图,是图论中的一种特殊模型,它的顶点可分割为两个互不相交的子集,并且图中的每条边所关联的两个顶点分别属于这两个不同的顶点集。二分图在复杂网络分析中有很多应用,例如科...

鉴客
2012/11/03
1K
0
二分图算法模板以及相关知识

说说二分图,其实图论的题难点不在用算法,难在如何建图,只有图建好了,剩下的就简单了,在这说说求二分图的算法,即匈牙利算法,其实一点都不难,也很好理解拿笔写写就行了. //板子, 直接套就行 //...

Anxdada
2017/06/22
0
0
司机乘客匹配中的距离和最小问题

这个是在工作中遇到的一个实际的算法问题,问题描述如下,当前有m个司机,n个乘客,每个司机和每个乘客的距离由经纬度可以计算得到,如何匹配可以使其去接乘客的距离和最小?(只能一个司机接...

necther
05/03
0
0
【算法篇】二分图匹配之匈牙利算法

二分图匹配,自然要先从定义入手,那么二分图是什么呢? 二分图: 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图...

沧海无雨
07/26
0
0
12.15~12.16培训总结

图论我在九月份打了很多板,基础较熟练,但对二分图匹配和网络流、费用流以及各种模型不太熟练。 二分图主要有这些模型 (部分参考lrj) 二分图最小覆盖(选择尽量少的点,使得每条边至少有一...

myjs999
2017/12/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JavaScript 继承使用解析

继承,通俗地说,之前你写过一些类,这些类中有一些是而你现在要写的类的功能的子集或者基本相同,那么你不用完全重新写一个新的类,你可以把之前写的类拿过来使用.这样的一种代码重用过程就叫做继...

前端攻城小牛
8分钟前
0
0
深入解析JavaScript 原型继承

JavaScript 原型继承,学习js面向对象的朋友可以看看。十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 Object.prototype JavaScript是...

前端攻城老湿
9分钟前
0
0
2018阿里云双12——年末钜惠,低至2折

活动链接地址:https://m.aliyun.com/act/team1212/?params=N.JlJCGqQNL4

城市之雾
10分钟前
0
0
VMware前路难测,多个厂家群雄逐鹿

导读 以VMware为例,虚拟机巨头公布了第二财季报告所示,它第二财季收入同比增长13%,达到了21.7亿美元,而且该公司收入和每股收益均超出预期。 在人们高谈Salesforce、亚马逊等新兴云计算厂...

问题终结者
11分钟前
0
0
Vuex的初探与实战小结

1.概述 每一个 Vuex 应用的核心就是 store(仓库)。“store”基本上就是一个容器,它包含着你的应用中大部分的状态 (state)。 Vuex 和单纯的全局对象有以下两点不同: 1.Vuex 的状态存储是响...

peakedness丶
21分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部