二分图 二分图 奇数圈

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://www.413yy.cn/a/25101016/304325.html

更多阅读

qq被限制登录怎么办 解除查找限制客服

qq被限制登录怎么办——简介QQ被限制登录一般是被举报或者QQ号被盗的原因。QQ在被限制登录后,登录的时候就会出现乱码。(如图)qq被限制登录怎么办——工具/原料能上网的电脑。qq被限制登录怎么办——方法/步骤qq被限制登录怎么办 1、

娱乐圈演而优则唱的十大女星(组图) 娱乐圈十大美胸女星

演而优则唱是时下流行的趋势,也是演艺界的一个规律,内地当红女星中,有很多人也在尝试用不同的方式去演驿属于自己的歌曲,当然因为本人条件的各异和公司打造推广的方式不同,效果也截然不同,给观众带来全新感受并且让人能够记住的,自然是成功

iphone4怎么升级ios7 苹果4s怎样升级ios系统

方法适用于iphone4 iphone4S iphone5 升级ios7第一步,先去搜个ios7的固件下载 下载最新的,新的优化了,不会那么卡需要在电脑上安装itunes,然后iphone4链接上电脑。点开图上圈里边的东西会显示如下图,我的手机渣渣才ios5呢,现在一步到

悉数娱乐圈十大禁欲明星(组图) 娱乐圈十大渣男

与一些纵欲过度, 靠卖色相的明星不同, 娱乐圈里也不乏过着有爱无性生活的情侣, 究其禁欲原因, 不外乎是:有的是教徒, 有的是为了事业, 有的为健康着想, 而有的只是为了生个男丁, 有的甚至说是为了减肥, 当然有的本身就属于性无能,

声明:《二分图 二分图 奇数圈》为网友夜夜承欢分享!如侵犯到您的合法权益请联系我们删除