文档章节

二分图

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

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

鉴客
2012/11/03
1K
0
司机乘客匹配中的距离和最小问题

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

necther
05/03
0
0
二分图算法模板以及相关知识

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

Anxdada
2017/06/22
0
0
【算法篇】二分图匹配之匈牙利算法

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

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

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

myjs999
2017/12/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java Lock接口分析之ReentantReadWriteLock

ReentantReadWriteLock读写锁,在读线程多余写线程的并发环境中能体现出优异的性能,相比于synchronized与ReentrantLock这种独占式锁的模型,ReentantReadWriteLock采用独占式写锁与共享式读...

我爱春天的毛毛雨
30分钟前
1
0
EFK (Fluentd ElasticSearch Kibana) 采集nginx日志

本文描述如何通过FEK组合集中化nginx的访问日志。本人更喜欢按顺序来命名,所以使用FEK而不是EFK. 首先在nginx服务器上执行以下操作. 安装ruby http://blog.csdn.net/chenhaifeng2016/artic...

xiaomin0322
32分钟前
1
0
一键下载:将知乎专栏导出成电子书

老是有同学问,学了 Python 基础后不知道可以做点什么来提高。今天就再用个小例子,给大家讲讲,通过 Python 和爬虫,可以完成怎样的小工具。 在知乎上,你一定关注了一些不错的专栏(比如 ...

crossin
41分钟前
2
0
synchronized 之 对象锁 和 类锁

一、synchronized(object) 如果object没有被加锁,则获取object的锁;如果object已经被加锁则等待object的锁被释放。 二、需要加锁的情景 多线程共享同一资源会引起线程安全的情况下,才需要...

MyOldTime
42分钟前
7
0
tomcat 单机/多机 部署多应用

一.单机部署多应用: 1.在 linux 下解压安装两个 tomcat:tomcat1, tomcat2; 2.修改 /etc/profile, 增加 tomcat 环境变量: path 中加上 重新加载配置文件 source /etc/profile 3.修改 tomc...

imbiao
53分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部