“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

本文是对集智百科中“二分图”词条的摘录，参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！

目录

一、案例
二、属性
三、算法
四、其他应用
五、编者推荐
六、百科项目志愿者招募

在图论的数学领域中，二分图 Bipartite graph（或二部图）是一个曲线图，其所有顶点可以分为两个互不相交且独立的集合U和集合V，并且邻边（无向或有向）的两个顶点分别属于集合U和集合V。通常集合U和集合V被称为该二分图的子集。同时，二分图中不包含任何形式的奇数环，即：集合U和集合V构造的点集所形成的循环圈边数不为奇数。


通常可以将集合U和集合V视为被着色的两个图集：如果其中一个所有顶点为蓝色，另外一类为绿色，那么每条连边的两端必须具有不同的颜色。这是二分图必须满足的条件。相反，在非二分图（例如三角形）的情况下，这种着色要求是不可能的：因为如果一个顶点为蓝色，另一个为绿色，那么其剩下的第三个顶点将需要同时连接这两个颜色，显然这是不成立的，因为它违背了初始要求：二分图中所有顶点必须分为两个不相交且独立的集合U和V。即第三个顶点必须与另外两个点中的任意一个颜色相同。


对于二分图常用的表达方式是G=(U,V,E)，其中U和V分别代表顶点子集，E代表二分图中的连边。如果有一个二分图内部不连通，那么它可能具有多个二分图；在这种情况下，(U,V,E)标注将有助于指定一个特殊的二分图。在实际的应用当中这一点是很重要的。如果|U|=|V|，即这两个子集具有相同的基数，此时G被称为均衡二分图 Balanced bipartite graph。如果在二分图中同一侧（同一个子集）所有的顶点都具有相同的度数，则G被称为双正则二分图 Biregular。

无环二分图示例

m=5和n=3的完全二分图示例





案例



在建立两类不同对象之间的关系时，人们常常会很自然地选择二分图。以建立足球运动员和俱乐部的关系图为例，如果该球员曾为该俱乐部效力，那么在运动员和俱乐部之间就形成了一条边。这是二分图在建立隶属关系网络中的应用示例。在社交网络分析中，隶属关系便形成一种二分图。


自觉选用二分图的另一个例子是（NP-完全问题）铁路优化问题，其中输入项是火车的时间表及其停靠点，目标是找到尽可能小的火车站集合，以便每个火车都可以停靠至少一个选定的火车站。我们可以运用建模将这个问题转化为一个二分图中的主导集合问题，该图中每辆列车和每个车站都被看作是一个顶点，而当某列车停靠在某车站的时候，它们所形成的关系可看作一条连边。


第三个例子涉及到货币金融学领域。古代的硬币被设计为正反两面，不同时期和地区的政府会使用不同的正反面组合，因此，将所有可能的组合画成图就是一个二分图的结构。


更多抽象的例子:

  • 每个树状图都是二分的。

  • 具有偶数个顶点的环图都是二分的。

  • 在平面图中，所有面都具有偶数条边，该图为二分图。特殊情况是网格图和方图，其中每个内面都有4个边，每个内顶点至少有4个相邻点。

  • 在一个完全二分图中，分别由m和n的顶点（用Km,n表示）组成的两个不相交的集合U和V，连边E由分别在集合U和V的两个顶点连接。该二分图表示为G =（U，V，E），并且具有mn条边。另外完全二分图还有一个特例，那就是 冠图 Crown graphs。冠图是将一个完全二分图中所有的完美匹配连边去掉后形成的。

  • 超立方体图 Hypercube graph， 局部立方体 Partial cube和 中位数图 Median graph均为二分图。判别方法是将这些图中的顶点用 位向量Bitvector（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树状图和方图都是中位数图，而所有中位数图都是局部立方体。





属性


‍

特征表述

二分图可以用以下几种不同的方式来描述其特征：

  • 当且仅当它不包含奇数环的时候，该图为二分图。

  • 当且仅当图是它是2-可着色的（即其色数小于或等于2）时，该图为二分图。

  • 一个图是二部图当且仅当它的顶点集V可分为2个集合 A和B，以至于

  • 任何由以下组成的二部图n顶点最多可以有n^2/4边缘。

  • 当且仅当它是二分图时，图的频谱是对称的。


柯尼希定理和完美图 Kőnig’s theorem and perfect graphs

在二分图中， 最小顶点覆盖 Minimum vertex cover（顶点数）等于 最大匹配数 Maximum matching(边数)；这就是 柯尼希定理 Kőnig’s theorem。该定理的另一种等价形式是， 最大独立集 Maximum independent set（顶点数）加上最大匹配数等于顶点的数量。在任意没有孤立顶点的图中， 最小边覆盖 Minimum edge cover（边数）加上最大匹配数等于顶点数。于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。


另一类相关特性与 完美图 Perfect graph有关：每个二分图及其补图、线图、线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（它们的色数为2，最大的团数同样为2），但是二分图的补图完美性的判定更简单些，且可以看作是柯尼希定理的另一种表述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。同时完美图线图的补图完美性也是作为柯尼希定理的另一种表述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。


根据 强完美图定理 Strong perfect graph theorem，完美图具有类似于二分图的 禁止图特征 Forbidden graph characterization：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为 导出子图Induced subgraph时，图才是完美的。二分图及其线图、补图占据了完美图五种基本类别中的四个，它们可以用于证明了强完美图定理。


度相关问题

对于一个顶点，其相邻顶点的数量称为该顶点的度数，并表示为deg(v)。二分图的总度数和公式为：



一个二分图的度数序列是一对列表，每个列表包含两个部分U和V的度数。例如，完全二分图K3,5具有度数序列(5,5,5)，(3,3,3,3,3)。其同构二分图 Isomorphic bipartite graphs具有相同的度数序列。但是，度数序列通常不是定义二分图的唯一方法；在某些情况下，非同构二分图可能具有相同的度数序列。


二分实现问题 Bipartite realization problem是通过以已知的两组自然数序列作为度数序列，来查找简单的二分图的判定问题（数理逻辑）。（尾随零可以忽略，因为通过向图添加适当数量的孤立顶点可以实现尾随为零。）


与超图和有向图的关系

一个二分图(U,V,E)的双邻矩阵是大小为|U|×|A|的（0,1）矩阵，其分别代表了每对相邻顶点集合和非相邻顶点的集合（全零矩阵）。双邻接矩阵可用于描述二分图，超图和定向图之间的等价关系。


超图是一种类似于无向图的组合结构。它具有顶点和连边，但是其中的边可以是任意子集组的顶点，而不必具有两个端点。可以使用二分图(U,V,E)来建模超图，其中U是超图的其中一个顶点集，V是该超图的连边集（称为超边集），E包含的连边定义为：从一个超图顶点v到超图连边e恰好当v是e的端点集之一时。在这种对应关系下，二分图的双邻矩阵正好是其相应超图的关联矩阵。作为二分图和超图之间这种对应关系的特例，任何 多重图 Multigraph（即在相同两点之间可能存在的多条边的图）都可以解释为其中一些超边具有相同端点集的超图，并且由不具有多个邻接关系的二分图表示，其中二分图的同边顶点的度数均为2。



关于邻接矩阵的另一个相似解释可以被用于展示有向图和均衡二分图（二分子集顶点数相等）之间的一一对应关系（在给定数量的标记顶点上，允许自循环）。例如，具有n个顶点的有向图的邻接矩阵可以是大小为n×n的任何（0,1）矩阵，然后可以将其重新解释为：具有相同顶点数n的同边子集的二分图的邻接矩阵。通过这种构建方式，二分图可以被解释为是一个有向图的 二分双重覆盖 Bipartite double cover。





算法



二分性测试

可以使用 深度优先搜索 Depth-first search来测试图是否为二分图，并在线性时间内返回双色（如果是二分图）或奇数环（如果不是二分图）。其方法的主要思想是为每个顶点分配与 深度优先搜索林 Depth-first search forest中其上级颜色不同的颜色，并在其中进行全部选择。这必定会为生成林 Spanning forest提供两种颜色，包括将顶点连接到其上级的边。不过它可能无法为非林边正确着色。在深度优先搜索林中，每个非林边缘的两个顶点之一是另一个顶点的始源，并且当深度优先搜索发现这种类型的边时，应检查这两个顶点是否具有不同的颜色。如果不是，则林中从始源到后代的路径与颜色不同的边一起会形成一个奇数环，该奇数环会从算法中返回，并输出非二分图的结果。但是，如果算法在未检测到此类奇数环的情况下终止，则必须对每个边进行适当的着色，并返回双色以及得出该图形为二分图的结果。


又或者，可以使用 广度优先搜索 Breadth-first search来替代深度优先搜索进行检测。同样，在搜索林中，以广度优先的顺序为每个节点赋予与上级节点相反的颜色。如果在着色某个顶点时存在一条边，其连接了与先前着色的顶点相同的颜色。然后这条边沿着以广度优先搜索林中的路径，将其两个端点与其最低共有始源nLowest common ancestor相连，形成一条奇数环。当然，如果该算法最终没找到奇数环且终止，那么它肯定已经找到了正确的着色，可以安全返回并得出该图是二分图的结论。


对于n个线段的相交图或 欧几里得平面 Euclidean plane中的其他简单形状图，即使图本身可能具有多达O(n^2)个边缘，也可以测试其是否而二分图，并在时间O(nlogn)中返回双色（判定为二分图）或奇数环（判定为非二分图）。



奇环横贯

奇环横贯是一个 NP完全算法问题 NP-complete algorithmic problem（因不能用多项式算法而使问题无法解决的），在给定图形G=(V,E)和数字k的情况下，询问是否存在一组k个顶点，将其从G移除会导致生成为二分图。这个问题是 固定参数可解 Fixed-parameter tractable的，这意味着存在一种算法，其运行时间可以由图形大小的多项式函数乘以增大系数k来确定。奇环横贯的名称源于：当且仅当图没有奇数环时，该图是二分图。因此，为了从图中删除顶点来获得二分图，就需要“命中所有奇数环”或找到所谓的奇环横贯集合。例如在图示中，图中的每个奇数环都包含蓝色（最底部）顶点，因此删除这些顶点就相当于删除了所有奇数环并留下一个二分图。


边二分化问题 Edge bipartization problem是删除尽可能少的边以使其成为二分图的问题，也是图修改算法中的重要问题。此问题同样是固定参数可解的，可以在时间O(2^k m^2),内解决，其中k是要删除的边数，m是输入图中的边数。


匹配

一个图中的匹配是其边集的一个子集，其中任意两个边均不共享一个端点。 多项式时间算法 Polynomial time algorithms素以解决很多关于匹配的算法问题而得名，包括 最大匹配 Maximum matching（查找使用尽可能多的边的匹配）， 最大权重匹配 Maximum weight matching和 稳定婚姻问题 Stable marriage。在许多情况下，与非二分图相比，二分图上的匹配问题更容易解决，并且许多匹配算法（例如用于最大基数匹配的 Hopcroft-Karp算法）仅在二分图输入的时候才能正确运行。


举一个简单的例子，假设一组P  的所有人都在一组J的职位中寻找工作，但并不是所有人都适合所有职位。可以将这种情况建模为一个二分图(P,J,E)，其中当每个求职者找到其合适的工作时产生的关系就作为连边。一个完美的匹配描述的是所有求职者同时找到所有工作的情况； 霍尔的婚姻定理 Hall’s marriage theorem阐述的就是二分图允许完美匹配的特征。美国国民住院医师匹配项目采用的就是图形匹配法来解决美国医学生求职者和医院实习工作的匹配问题。


Dulmage–Mendelsohn 分解是二分图的结构分解，可用于寻找最大匹配。





其他应用



二分图广泛应用于现代编码理论中，尤其是在对从通道接收到的密码进行解码领域。例如因子图 Factor graphs和 坦纳图 Tanner graphs。Tanner图是二分图，其中二分的一侧顶点表示一个密码数字，另一侧顶点表示一个数字的组合，这些数字的总和期望为零且不存在误差。因子图与置信网络密切相关，可用于LDPC和Turbo码的概率解码。


在计算机科学中，Petri网是用于分析和模拟并发系统的数学建模工具。该系统被建模为具有两组点集的二分有向图：一组“库所”点集用于容纳资源，以及一组“事件”点集用于生成和（或）消耗资源。他们通过约束节点和连边的传递来进一步限制系统的行为。Petri网利用二分有向图的属性和其他属性来允许对系统行为进行数学证明，同时还可以轻松实现系统仿真。


在射影几何中，Levi图是二分图的一种形式，可用于对配置点和线之间的入射进行建模。结合点和线的几何特性，即每两条线最多相交于一个点，并且每两个点都由一条线连接，因此Levi图不一定包含任何长度为4的环，进而其周长必须为6或更大。





编辑推荐




集智课程

二分图神经网络(BGNN)与推荐系统

https://campus.swarma.org/course/1054

本课程来自集智学园图网络论文解读系列活动。本课程是对论文《Bipartite Graph Neural Networks for Efficient Node Representation Learning》的解读。

图网络算法目前主要用于同质化的图。这篇论文结合图网络算法和二分图的特点提出了BGNN算法，适用于二分图上的学习。该算法主要包括跨节点域的消息传递机制（inter-domain message passing）和同节点域的信息对齐(intra-domain alignment)机制. 通过采用GAN技术实现了无监督学习，又采用逐层训练的方法提升了算法效率，并在人工数据集和实际数据集上进行 试验，结果超越了现有的图表示学习方法。这些优势使BGNN有潜力应用于大规模推荐系统。


书籍领读：图论

https://campus.swarma.org/course/1790

本课程中，将讲解巴拉巴西网络科学书籍第一章图论。


漫谈图论的起源、发展与应用

https://campus.swarma.org/course/1745

本课程中，介绍了图论中的基本概念和网络科学使用的工具，可以帮助认识真实网络的关键性质。






百科项目志愿者招募




作为集智百科项目团队的成员，本文内容由Jie翻译，由CecileLi审校，薄荷编辑。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。


以上内容都是我们做这项目的起点，作为来自不同学科和领域的志愿者，我们建立起一个有效的百科团队，分配有审校、翻译、编辑、宣传等工作。我们秉持：知识从我而来，问题到我为止的信念，认真负责编撰每一个词条。


在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。


如果你有意参与更加系统精细的分工，扫描二维码填写报名表，我们期待你的加入！



集智百科报名表


来源：集智百科

编辑：王建萍


推荐阅读



点击“阅读原文”，阅读词条二分图原文与参考文献