文档章节

二分图

Airship
 Airship
发布于 2017/09/08 10:01
字数 663
阅读 8
收藏 0
点赞 0
评论 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
粉丝 34
博文 789
码字总数 18996
作品 0
南京
高级程序员
复杂网络分析库NetworkX学习笔记(5):二分图

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

鉴客 ⋅ 2012/11/03 ⋅ 0

司机乘客匹配中的距离和最小问题

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

necther ⋅ 05/03 ⋅ 0

二分图算法模板以及相关知识

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

Anxdada ⋅ 2017/06/22 ⋅ 0

12.15~12.16培训总结

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

myjs999 ⋅ 2017/12/17 ⋅ 0

二分图知识点总结

最大匹配:在二分图中,最多的没有公共顶点的边的数量。(用匈牙利算法) 最小点覆盖:在二分图中,所有边至少有一个顶点在一个点集

wang3312362136 ⋅ 02/01 ⋅ 0

[BZOJ2663][Beijing wc2012]灵魂宝石(二分+二分图匹配)

传送门 因为问题是单调的,R小肯定匹配的少,R大肯定匹配的多,所以一眼可以二分+二分图匹配。 难点就在要求最小值和最大值,最小值好求,但是最大值呢? 因为二分图匹配算法是求得最大匹配,...

cabi_zgx ⋅ 03/23 ⋅ 0

二分图匹配

一、二分图匹配 定义: 1、给定一个二分图G,在G的一个子图M中,M的边集{E}中的任何一条边都不依附于同一个节点。 (实际上也可以理解为,集合内没有点相连,集合间有点相连,且每个点只有一...

luodanyu_ ⋅ 2017/12/17 ⋅ 0

优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆 ⋅ 2011/12/03 ⋅ 0

网络流&二分图 12 - 05

二分图匹配 有向图的最小路径覆盖 把每个点拆成两个点,一个负责进边,一个负责出边,最小路径覆盖 二分图的最小点覆盖 二分图的最大独立点集 春天来了 Description 这里有 每个人都有一个腼...

aziint ⋅ 2017/12/17 ⋅ 0

二分查找判定树

5、二分查找判定树  二分查找过程可用二叉树来描述:把当前查找区间的中间位置上的结点作为根,左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树,称为描述二分查找的判...

天天顺利 ⋅ 2015/09/12 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

20.zip压缩 tar打包 打包并压缩

6月25日任务 6.5 zip压缩工具 6.6 tar打包 6.7 打包并压缩 6.5 zip压缩工具: zip支持压缩目录 zip压缩完之后原来的文件不删除 不同的文件内容其实压缩的效果不一样 文件内有很多重复的用xz压...

王鑫linux ⋅ 刚刚 ⋅ 0

double类型数据保留四位小数的另一种思路

来源:透析公式处理,有时候数据有很长的小数位,有的时候由在四位以内,如果用一般的处理方法,那么不足四位的小树会补充0到第四位,这样子有点画蛇添足的感觉,不太好看。所以要根据小数的...

young_chen ⋅ 7分钟前 ⋅ 0

Python 优化 回溯下降算法

使用sympy构造表达式,实现回溯下降算法 完整代码 from matplotlib import pyplot as pltimport numpy as npfrom mpl_toolkits.mplot3d import Axes3Dfrom sympy import *import mat......

阿豪boy ⋅ 12分钟前 ⋅ 0

Django配置163邮箱出现 authentication failed(535)错误解决方法

最近用Django写某网站,当配置163邮箱设置完成后,出现535错误即:smtplib.SMTPAuthenticationError: (535, b'Error: authentication failed') Django初始配置邮箱设置 EMAIL_HOST = "smtp.1...

陈墨轩_CJX ⋅ 13分钟前 ⋅ 0

用接口模拟可伸缩枚举(34)

1、枚举的可伸缩性最后证明都不是什么好点子 扩展类型的元素是基本类型实例,基本类型的实例却不是扩展类型的元素,很混乱 目前还没有很好的方法来枚举基本类型的所有元素,及其扩展 可伸缩性...

职业搬砖20年 ⋅ 17分钟前 ⋅ 0

Ubuntu18.04 IDEA快捷键无法使用

IDEA默认的回退到上一视图的快捷键是Ctrl + Alt + Left,在ubuntu中这个快捷键被占用了,在16.04中可以在界面中取消这个快捷键,但是18.04就看不到了,可以使用以下命令解决 gsettings set ...

Iceberg_XTY ⋅ 21分钟前 ⋅ 0

如何解决s权限位引发postfix及crontab异常

一、问题现象 业务反馈某台应用服务器,普通用户使用mutt程序发送邮件时,提示“postdrop warning: mail_queue_enter: create file maildrop/713410.6065: Permission denied”,而且普通用法...

问题终结者 ⋅ 33分钟前 ⋅ 0

Unable to load database on disk

由于磁盘空间满了以后,导致zookeeper异常退出,清理磁盘空间后,zk启动报错,信息如下: 2018-06-25 17:18:46,904 INFO org.apache.zookeeper.server.quorum.QuorumPeerConfig: Reading co...

刀锋 ⋅ 53分钟前 ⋅ 0

css3 box-sizing:border-box 实现div一行多列

<!DOCTYPE html><html><head><style> div.container{ background:green; padding:10px 10px;}div.box{box-sizing:border-box;-moz-box-sizing:border-box; /* Fir......

qimh ⋅ 58分钟前 ⋅ 0

Homebrew简介和基本使用

一、Homebrew是什么 Homebrew是一款Mac OS平台下的软件包管理工具,拥有安装、卸载、更新、查看、搜索等很多实用的功能。简单的一条指令,就可以实现包管理,而不用你关心各种依赖和文件路径...

说回答 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部