文档章节

二分图

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

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

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

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

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

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

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

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

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

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

myjs999
2017/12/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
12
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部