精华内容
下载资源
问答
  • 二部图

    2020-08-28 21:52:24
    二部图

    定义6.1 二部图

    在这里插入图片描述

    完全二部图

    在这里插入图片描述
    在这里插入图片描述

    定理 6.1

    一个无向图G为二部图,==》G中没有长度为奇数的回路
    在这里插入图片描述

    定义6.2 匹配

    在这里插入图片描述
    M中任意的不相邻的两条边为一个匹配,但是如果在加上一条边的话, 就不匹配了,这就是M的极大匹配
    而边数最多的匹配叫最大匹配

    完美匹配:占了所有顶点的最大匹配。

    在这里插入图片描述

    定义6.3 晚辈匹配,与完美匹配

    在这里插入图片描述

    定理6.2 Hall定理

    在这里插入图片描述

    定理6.3

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 二部图(二分图)总结

    万次阅读 多人点赞 2019-05-20 21:22:06
    1 二部图 二部图又叫二分图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in ...

    1 二部图

    二部图又叫二分图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为两个不相交子集 ,使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分,则此图为一个二分图,如下图所示的六个图全都是二分图:

           关于二部图有一个重要的定理:G为二部图的充要条件是G中的每一个圈的长度都是偶数。证明过程如下:

     

    2 匹配问题

    设G=<V, E>是二分图,而且E是V1和V2的笛卡尔乘积子集。若M包含于E,而且M中任何两条边不相邻,则称M是G的一个匹配;具有边数量最多的匹配称为最大匹配;若|V1|=|V2|=|M|,则称M为完美匹配。匹配M中的边e称为杆。

     

    最大匹配:图 4 是一个最大匹配,它包含 4 条匹配边。

    完美匹配:图 4 是一个完美匹配。显然,完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突)。但并非每个图都存在完美匹配。

     

    关于匹配问题还有以下四个重要的定义:

    设M是一个匹配,则:

    1. V1中的结点u和V2中的结点v称被M所匹配,当且仅当有杆e属于M,使得e=(u, v)
    2. 结点u被称为M的饱和点当且仅当有杆e属于M匹配结点u;否则结点u称为M的非饱和点
    3. 交错路P是一条分别交替的属于M和E\M的边构成的极大的初级路(或圈);
    4. 增广路P是一条起点为u以及终点为v且都是非饱和点的交错路。

     

    下图中左边的路都是交错路,也是增广路,其端点都是非饱和点,实线所表示的边都是匹配中的边。如果我们像右边的图那样,将左边路中的实线变成虚线边,将虚线边变成实线边就可以逐步增加匹配中的边,从而使得匹配达到最大匹配。接下来介绍的求最大匹配的算法就是基于这种思想。

     

    3 匈牙利算法

    匈牙利算法思想:通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时,达到最大匹配(增广路定理)。

     

    匈牙利算法计算步骤:

    No 1任取一匹配M (可以是空集或者只含有一条边的集合);

    No 2令S = {u|u∈V1∩u是M的非饱和点},若S为空集,则M已经是最大匹配,exit;

    No 3否则,S不为空,任取一非饱和点u0作为起点,从此起点走出几条交错路 Pil, Pi2,…;

    No 4如果它们中有某条路P是增广路(即P的终点也是非饱和点),则令M(M\P)U(P\M)(并且满足|M| (新)=|M| (旧)+1),回到No 3;

    No 5否则,如果它们中无一条是增广路(即终点全是饱和点),则令S=S\{u0}。如果S不为空,则回到No3; 否则S为空,则M就是最大匹配,exit

     

    [例子]有六位教师:张、王、李、赵、孙、周,要安排他们去教六门课程:数学、化学、物理、语文、英语和程序设计。张老师会教数学、程序设计和英语;王老师会教英语和语文;李老师会教数学和物理;赵老师会教化学;孙老师会教物理和程序设计;周老师会教数学和物理。应该怎么样安排课程才能使每门课都有人教,每个人都只教一门课而且不至于使任何人去教他不懂的课?

    这是一个工作分派问题,并且是图论中求二分图的完美匹配的典型问题:六个老师、六门课程的匹配。可以将教师和课程分别看做二分图中的两个互补的节点子集,当某教师会教某课程时就在相应的两个节点之间连接一条边,这样按照题目要求可以画出如下图。

     

    当S集合为空时,则匈牙利算法结束,得到最后的解。在二分图中,最大匹配和完美匹配并不唯一,例如上面的问题还存在这样一种完美匹配:

     

    4 KM算法

    二分图如果是没有权值的,求最大匹配,可以使用用匈牙利算法求最大匹配。如果带了权值,求最大或者最小权匹配(最佳匹配),则必须用KM算法。其实最大和最小权匹配都是一样的问题。只要会求最大匹配,如果要求最小权匹配,则将权值取相反数,再把结果取相反数,那么最小权匹配就求出来了。

     

    KM算法  Kuhn-Munkras算法用来解决带权二分图最优匹配问题。基本思想是通过引入顶标,将最优权值匹配转化为最大匹配问题。

    KM算法流程:

    (1)初始化可行顶标的值;

    (2)用匈牙利算法寻找完备匹配;

    (3)若未找到完备匹配则修改可行顶标的值;

    (4)重复(2)(3)直到找到相等子图的完备匹配为止。

     

    [例子]婚姻匹配问题时一个经典的带权二分图问题,现在有N男N女,有些男生和女生之间互相有好感,我们将其好感程度定义为好感度,我们希望将他们两两配对,并且最后希望好感度和最大。如何选择最优的配对方法呢?可以使用KM算法求解。

     

    首先,每个女生会有一个期望值,就是与她有好感度的男生中最大的好感度,男生的期望值为0.

    接下来开始配对,从第一个女生开始,为她找对象:因为女1+男3=4+0=4,满足“男女两人的期望等于两人之间的好感度”规则。

    给女2找对象,因为:女2+男3=3+0=3,满足要求,但是男3已经有对象了,因此给女2找对象失败。接下来需要修改期望值:将发生冲突的女1和女2的期望值降低1,而将冲突源男3的期望值增加1.如此一来女1和男3仍然满足匹配,与男1也满足匹配。女2与男1,男3均满足匹配。修改期望值之后,继续给女2找对象。此时女2-男1匹配,同时女1-男3也匹配。

    接下来给女3匹配对象,因为女3+男3=6!=5,因此无法给女3找到匹配。所以让女3的权值减1,此时女3和男3匹配了,但是又和女1冲突了。便去寻找女1,但是对于女1而言可匹配的男1已经和女2 匹配了,于是再去寻找女2。

    而此使对于女2而言,没有其他的边满足匹配规则了,因为现在的寻找路径为:

    女3->男3->女1->男1->女2,因此需要将左边的女1,2,3结点权值均减去1,将男1,3的权值均加1.

    此时对于女1,2,3而言,男1,2,3均已经满足他们的期望值,也就是说现在已经将带权图转换为了无权图。因此接下来的男女匹配问题就可以使用匈牙利算法来实现,下图给出了解。

    在这个问题中,冲突一共发生了三次,所以一共降低了3次效率值,但是每次降低的效率值都是最小的,所以完成的仍是最优匹配。这就是KM算法的整个过程。整体思路就是:每次都帮一个顶点匹配最大权重边,利用匈牙利算法完成最大匹配,最终完成的就是最优匹配。

     

    5 应用

    双聚类技术最早是为了满足分析基因表达数据的需要而提出的。基因是一个生命有机体向其后代传递特征的单元。典型的,基因驻留在一个DNA段中。对于所有生物,基因都是至关重要的,因为他们确定所有的蛋白质和功能RNA链。他们持有用来构建和维持生命有机体细胞和传递遗传特征到后代的信息。功能基因的合成产生RNA或者蛋白质,依赖于基因表达过程。基因型是细胞、有机体或者个体的基因组成。

    使用DNA图谱和其他生物工程技术,我们可以在大量不同的实验条件下,测量一个有机体的大量基因的表达水平。这些条件可能对应于实验中的不同时间点或者取自不同的器官的样本。粗略来说,基因表达数据或者DNA微阵列数据概念上是一个基因-样本/条件矩阵,其中每一行对应于一个基因,每一列对应于一个样本或条件。矩阵的每一个元素都是实数,记录一个基因在特定条件下的表达水平,如下图所示:

           生信方向的研究表明,在人体内存在一种机制:某些基因的表达能够抑制另一部分基因的表达,因此如何将这两种基因分别找出来在临床治疗上有重要的意义。可以将这个问题抽象成为一个二部图问题,最终尽可能的将这两部分基因划分成两个集合。每一个基因即可看作是一个G中的一个点。

    展开全文
  • 二、二部图

    2020-11-11 13:12:43
    图(graph)之二部图一、简介一、简介二、特征三、操作1. 向上筛选(sift up/bubble up)2. 向下筛选(sift down/bubble down)3. 初始化四、例题解析1. 题目描述2、代码二、特征三、操作1. 向上筛选(sift up/bubble up)...

    一、简介

    二部图又作二分图,是图中的特殊模型。设G=(V, E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A, B),并且图中每条边的(i, j)所关联的两个顶点i和j分别属于不同的顶点集(i in A,j in B),那么G就可以被称为二部图或二分图。
    二部图(来源于百度百科)

    来源于百度百科

    二、例题解析

    1. 题目描述

    给定一个无向图graph,当这个图为二分图时返回true。

    如果我们能将一个图的节点集合分割成两个独立的子集A和B,并使图中的每一条边的两个节点一个来自A集合,一个来自B集合,我们就将这个图称为二分图。

    graph将会以邻接表方式给出,graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边: graph[i] 中不存在i,并且graph[i]中没有重复的值。

    示例 :
    输入: [[1,3], [0,2], [1,3], [0,2]]
    输出: true
    解释: 
    无向图如下:
    0----1
    |    |
    |    |`
    3----2
    我们可以将节点分成两组: {0, 2} 和 {1, 3}。
    

    注意:

    • graph 的长度范围为 [1, 100]。
    • graph[i] 中的元素的范围为 [0, graph.length - 1]。
    • graph[i] 不会包含 i 或者有重复的值。
    • 图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

    本题引用自leetcode第785题,地址是:判断二分图

    2、代码

    from typing import List
    class Solution:
        def dfs(self, grip, i, colors, color, N) -> bool:
            colors[i] = color
            for j in grip[i]:
                if grip[i][j] == 1:
                    if colors[j] == color:
                        return False
                    if colors[j] == 0 and not self.dfs(grip, j, colors, -1 * color, N):
                        return False
            return True
    
    
    
        def isBipartite(self, graph: List[List[int]]) -> bool:
            N = len(graph)
            grip = [[0] * N for _ in range(N)]
            colors = [0] * N
            
            for i in range(N):
                for j in graph[i]:
                    grip[i][j] = 1
            
            for i in range(N):
                if colors[i] == 0 and not self.dfs(grip, i, colors, 1, N):
                    return False
            return True
    

    代码采用python3开发

    展开全文
  • 二部图定义+着色法判断二部图

    千次阅读 2018-11-17 11:16:34
    一、二部图定义:   1、 二分图又称双分图、二部图、偶图,指顶点可以分成两个不相交的集 和 ( U、V皆为独立集,使得在同一个集内的顶点不相邻(没有共同边)的图 2、 二分图又称作二部图,是图论中的...

    一、二部图定义:

     

    1、

    二分图又称双分图二部图偶图,指顶点可以分成两个不相交的集 UV ( U、V皆为独立集,使得在同一个集内的顶点不相邻(没有共同边)的图

    2、

    二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E) 是一个无向图,如果顶点 V 可分割为两个互不相交的子集 {\displaystyle (U,V)},并且图中的每条边 {\displaystyle (i,j)}  所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集 ( i in Uj in V),则称图 G 为一个二分图

    简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

    3、二分图图片

     

    4、性质:

    最小边覆盖集的基数等于最大独立集的基数

    最大独立集的基数与最大匹配的基数之和,等于顶点数目

    连通的二部图:最小顶点覆盖集的基数等于最大匹配的基数

     

    以上内容来源于维基百科


    二、判断是否为二部图 ?

    区分二分图,关键是看点集是否能分成两个独立的点集

    二部图的充分必要条件是:

    n(n>=2)阶无向图G是二部图当且仅当G中无奇圈

    二部图充分必要条件的证明

     


    三、区分二部图-点着色方法

    思路:- BFS

    我们从图中任选一个顶点s,并把它着为红色,接着s的邻居必须着为蓝色,然后s邻居的邻居再次作为红色,这样一层一层着色,直到整个图被着色为止;

    如果邻接的点有相同颜色的,则说明不是二分图(即某个点可能既被着成蓝色,也被着成红色,那么就不是一个二分图)

    或者可以这样理解:

    先找一个点为起点,然后把与它相连的点的颜色都变成与它相反的颜色,然后把这些点加入到队列中,如果这些点的颜色与父节点的不一样,就忽略,如果一样就证明了这个图不是二分图

     

     

     

     

     

    展开全文
  • 二部图(染色法判断二部图)

    千次阅读 2017-09-10 21:06:58
    二部图又叫二分图,我们不是求它的二分图最大匹配,也不是完美匹配,也不是多重匹配,而是证明一个图是不是二部图。证明二部图可以用着色来解决,即我们可以用两种颜色去涂一个图,使的任意相连的两个顶点颜色不相同...
  • 图论_二部图

    2020-04-09 15:54:31
    二部图的概念
  • 目录石墨笔记 PPT版1 二部图 偶图 双图 二分图 Ks,t G(V1,V2,E)2 欧拉图3 哈密顿图4 平面图欧拉公式推论: n-m+r = k+1m <=3n-6是平面图的必要条件m <= ((k-2)/k )*(n-2)是平面图的必要条件库拉图斯基定理: ...
  • 二部图匹配

    2018-03-19 13:49:40
    1、二部图2、km算法
  • 二部图的详解

    2019-10-19 23:16:27
    二部图的详解
  • 具有二部图的半监督深度哈希
  • 该程序实现了二部图的最优完备匹配,采用经典KM算法,程序操作性强。方便使用
  • 算法介绍 该算法来自于文献[1]该算法把二部图聚类问题转换为图划分问题而图划分问题通 过谱聚类算法解决该算法的主要创新在于解决了以前算法只能根据二部图其中一部图对 另一部图的点聚类而不能同时对所有点聚类的...
  • 针对网络推断(NBI)算法的二部图实现算法忽略二部图权重而导致实际评分值高的项目没有得到优先推荐这一问题,提出加权网络推断(WNBI)算法的加权二部图实现算法。该算法以项目的评分作为二部图中用户与项目的边权,按照...
  • 完全二部图的无圈边染色,丁伟,张埂,如果图 的正常边染色不包含 色圈,则称它是图 的无圈边染色.图 的无圈边色数表示图 的无圈边染色所需的最小颜色数.2001年,Alon等猜想任�
  • 【离散数学】二部图

    2021-03-02 11:45:34
    介绍图论中的二部图
  • 基于曲面二部图匹配的3D模型相似性研究
  • KM算法用于求二部图最大权匹配,该程序的输入是二分图两边节点的数和一个矩阵 矩阵的行和列应该相等,当二分图的两边节点数不一样时,以数值大的节点为准,不存在的边的权赋值为0。 比如:一边是2个点(v1,v2),...
  • 二部图和匈牙利算法

    2019-08-11 11:01:51
    二部图 二部图的定义:设GGG是一个图,若V(G)V(G)V(G)有一个划分:V(G)=V1⋃V2V(G)=V_1 \bigcup V_2V(G)=V1​⋃V2​,使得<V1V_1V1​><V2V_2V2​>都是空图,那么称图GGG是一个双图,或二部图,或二分图...
  • 二部图总结

    千次阅读 2013-09-08 21:55:47
    今天总结一下二部图,那么首先谈一下二部图的用处,首先谈一下二部图的最大匹配一下是代码模型#include #include #include #define Max 100 bool match[Max][Max]; int pre[Max]; bool vi[Max]; int find(int x);...
  • 6.1 二部图 本节大多都是概念的引入,我就用我自己的话去记录了。 二部图(偶图):我们将图里的点分为两个集合V1V_1V1​,V2V_2V2​后,每一条边的端点分别属于V1V_1V1​,V2V_2V2​。我们将二部图记做GGG = <V1V...
  • 二部图
  • 二部图 Hall定理

    千次阅读 2018-12-06 21:31:20
    hall定理是判定二部图是否存在完备匹配的定理 定理内容 设二分图中G=&amp;amp;amp;lt;V1,V2,E&amp;amp;amp;gt;中 |V1|=m&amp;amp;amp;lt;=|V2|=n,G中存在从V1到V2的完备匹配当且仅当V1中任意k(k=1,2,…,...
  • 关于二部图D(k,q)的周长的猜想
  • 图论算法-二部图匹配

    2009-10-30 18:43:23
    图论算法-二部图匹配图论算法-二部图匹配图论算法-二部图匹配
  • 基于学习的二部图匹配,用于基于视图的3D模型检索
  • 具有给定匹配数的二部图中的某些拓扑指数的极值

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,546
精华内容 1,818
关键字:

二部图