更新时间：2024-09-21 13:17
二分图（英文：bipartite graph）又称二部图，是一类特殊的图。其定义为：如果一个图的顶点能分成两个集合V1和V2，并使得同一集合中的任何两个顶点都不邻接，则称此图为二分图。
图论发展至今已有200多年的历史，它最早起源于加里宁格勒七桥问题。1736年，瑞士数学家莱昂哈德·欧拉（Euler）在《关于位置几何问题的解法》的论文中，对哥尼斯堡七桥问题进行了论述，并将其形象地转化为一笔画问题，标志着图论的正式诞生。1878年，英国数学家西尔维斯特（Sylvester）在《自然》杂志上发表的著作《化学与代数》中首次使用了“图”的数学术语。1914年，匈牙利数学家柯尼希（Koenig）在著作《关于集合的一般理论和图论中的一个问题》中引入了二分图的概念，并称它为“偶回路图”，后改称为二部图。1935年，英国数学家霍尔（Hall）在其论文《论子集的代表元》中提出了著名的霍尔定理，给出了二分图存在完美匹配的充要条件。1957年，法国数学家贝尔热（C.Berge）提出了图存在最大匹配的充要条件，它可用于解决二分图中的最大匹配问题。
二分图有一些基本性质，如所有回路长度均为偶数。二分图可根据节点基数的大小进行分类，它与子图、完全图等概念密切相关。二分图的运算有匹配、覆盖、检验二分性等，其中匹配可以通过匈牙利算法来求解。图的每边最多只有两个顶点，如果推广至任意个，可得到超图的概念，二分图与超图之间可相互确定。此外，二分图在现实世界中具有广泛的应用价值，如生物学中，融合多生物数据的二分图聚类集成方法，能有效地处理蛋白质功能重叠问题。
二分图：设和是图的顶点子集，使，且的每一条边的一个端点在中，另一个端点在中，则称为二分图，记作。
完全二分图：如果中的顶点与的每个顶点都相连，则称为完全二分图。若(表示集合中元素的个数），则完全二分图记作。
图论发展至今已有200多年的历史，它最早起源于加里宁格勒七桥问题。1736年，瑞士数学家莱昂哈德·欧拉（Euler）向圣彼得堡科学院提交了一篇名为《关于位置几何问题的解法》的论文，在该论文中阐述了关于解决哥尼斯堡七桥的问题，并把该问题形象地转化为一笔画问题。该论文标志着图论的正式诞生，但其中并没有涉及图的概念，甚至不曾出现过现代意义的图。后来，1878年，英国数学家西尔维斯特（Sylvester）在《自然》杂志上发表了著作《化学与代数》，首次使用了“图”这一数学上的专门术语。
1914年，匈牙利数学家柯尼希（Koenig）在巴黎举行的数学哲学大会上提交了著作《关于集合的一般理论和图论中的一个问题》，引入了二分图的概念，并且称它为“偶回路图”，后来受到圣·拉盖（Saint Laggai）的著作影响而改用二部图这一名称。1935年，英国数学家霍尔（Hall）在论文《论子集的代表元》中提出了著名的霍尔定理，给出了二分图存在完美匹配的充要条件。1957年，法国数学家贝尔热（C.Berge）给出了图存在最大匹配的充要条件，它可用于解决二分图中的最大匹配问题。
例1 公用设施问题。代表住户的节点作为一组，代表公共设施（如水厂、电厂、香港中华煤气、电话公司等）的节点又是一组，两组的节点之间有边相连当且仅当对应的用户与公共设施之间存在隶属关系，所得的图为二分图。
例2 人员分配问题。某公司分配个工人做件工作，就可以用一个二分图来表示。代表人的一组顶点用表示，代表工作的一组用顶点表示。与相邻当且仅当工人能做工作，所得图是一个二分图。
例3 铁路优化问题。一个输入实例，如图，其中列火车（左侧）连接到各自的停靠站（右侧）。
输入：一个无向二分图，具有不相交的点集和以及边集。
任务：寻找最小的集合，使得中的每个顶点都有一条边将它连接到中的某些顶点。
（1）非平凡图是二分图当且仅当中不含有长为奇数的圈。
（2）当且仅当非空图不含回路或每个回路长度为偶数时，是二分图。
（3）图是点可着色的当且仅当为二分图。
（4）图的谱是对称的，当且仅当它是二分图。
度：在图中，与顶点关联的边的数目称为在中的度，记作。
度序列：是设图的顶点集为，则称为的度数序列。
设二分图的左、右部分的顶点的度数分别为和，那么
和
都等于边数，因此
。
二分图的节点可以分成两个集合，二分图的任意一条边的端点分别在这两个集合中。若二分图的节点集划分成的两个子集为和，设基数较大者为，则可将二分图分类如下：
（1）若，则称图为平衡的。
（2）若，则称图为准平衡的。
（3）若，则称图为偏斜的。
定义：设和是图，如果，且中边的重数不能超过中对应边的重数，则称图是的子图，写作。
导出子图：设是图的顶点集合的一个非空子集，以作为顶点集，以两端点均在中的边的全体为边集的子图，称为由导出的的子图，记为。
联系：二分图的任一子图（顶数不少于）仍为二分图。
定义：任意两个相异顶点都相邻的简单图称为完全图，阶完全图记作。其中，有向完全图的每对相同顶点间都有两个相反方向的弧。无向完全图的每一条边都是无向边，不含有平行边和环，每一对顶点间都有边相连。
联系：完全图可以被表示为个二分图的并当且仅当。
定义：图称为完美的，如果对任意诱导子图成立，与此等价的说法为：对任意成立。
联系：（1）二分图构成一个遗传图族，而且对于任意二分图成立，因此二分图都是完美的。
（2）二分图的补图、二分图的线图以及线图的补图都是完美的。
（3）根据强完美图定理，二分图的任何导出子图是二分图。
定义：在一个图中，若对每条边都指定一个方向，则称它为有向图。
联系：关于矩阵可约性中，通过利用邻接矩阵，二分图和有向图之间存在一一对应关系。设是一个阶由和组成二元矩阵，它可以表示为一个具有个顶点的有向图的邻接矩阵；同时，还可表示为一个二分图。由此，通过使用邻接矩阵的概念，每个有向图都关联一个二分图，反过来，每个二分图也都关联一个有向图。
匹配：设是图的边集的一个子集，如果中任意两条边在中都不邻接，则称是的一个匹配。
完美匹配与最大匹配：中的一条边的两个端点叫做在下是配对的。若匹配的某条边与顶点关联，则称饱和顶点，并且称是饱和的，否则称是不饱和的。如果的每个顶点是饱和的，则称匹配是完美的。如果中没有另外的匹配，使，则称是的一个最大匹配。显然，每个完全匹配都是最大匹配。
增广路：若是图中一条连通两个未匹配顶点的路径，并且中已匹配的边和待匹配的边在上交替出现，则称为相对于的一条增广路，即路径将两个不同集合的两个未匹配顶点通过一系列匹配顶点相连。
贝尔热（Berge）匹配定理：是图的最大匹配，当且仅当中不存在可增广路。
霍尔定理：又称婚姻定理，它给出了二分图存在完美匹配的充要条件。设是有二划分与的二分图，则含有饱和的每个顶点的匹配的充要条件是：，。
该算法由匈牙利数学家埃德蒙兹（Edmonds）提出，它以霍尔定理为理论基础，可应用增广路计算无权二分图的最大匹配。
基本思想：每次寻找一条关于匹配的增广路，通过使得中的匹配边数增加，其中称为边集与边集的环和。依次类推，直至二分图中不存在关于的增广路为止。此时得到的匹配就是的一个最大匹配。
步骤：（1）从一个初始匹配开始，若饱和的每个顶点，则停止，即为所求；否则，设是中非饱和的顶点。令及。
（2）若，则停止。因为，由霍尔定理，不存在饱和的每个顶点的匹配；否则，，故存在。
（3）若为饱和的，设，则用代替，代替，并转到（2）；否则，存在以为起点和为终点的可扩路，则用代替，并转到（1）。
覆盖：令为二分图的顶点子集，若对任意的，的两个端点中至少有一个属于，则称为的一个覆盖，如果覆盖在所有的覆盖中使得达到最小，则称为最小覆盖。
最小覆盖问题：图的覆盖问题包括边覆盖和点覆盖两种情况，边覆盖是用边控制点，点覆盖是用点控制边。最小覆盖问题研究的是用最少的点（或边）控制其它的边（或点）。
设为的一个匹配，和分别是，的子集，将和中的顶点称为已加标识的顶点，在下面两种情况下称弧边为可标识弧边，并且按照下面叙述的方式给弧边中的端点或者加标识。
①，并且弧边，此时给顶点实施加标识操作，即将标识为；
②，并且弧边，此时给顶点实施加标识操作，即将标识为。
标识算法可描述为：
图遍历主要有广度优先遍历与深度优先遍历两种，它们是对偶的遍历方法。广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索；深度优先遍历是将某一条枝上的所有节点都搜索到了之后，才转向搜索另一条枝上的所有节点。
一张无向图是二分图，当且仅当图中不存在奇环（长度为奇数的环）。该充要条件可用染色法进行判定，二分图染色一般基于深度优先遍历实现。
基本思想：尝试用黑白两种颜色标记图中的节点，当一个节点被标记后，它的所有相邻节点应该被标记与它相反的颜色。若标记过程中产生冲突，则说明图中存在奇环。
基于深度优先遍历，时间复杂度为，流程如下：
一个图是二分图等价于它是可以二着色的，基于二着色的定义，可用广度优先遍历来验证图的二分性。
基本思想：假设图为二分图，则可以从任意一个点开始对其进行二着色。算法在对每个点进行着色的过程中，将染为红色，则对于的每个邻居，可以确定它只能染为蓝色。而对于的每个邻居的邻居，可以确定其只能染为红色，如此往复，随着图遍历的推进，算法不断地发现新的边和点，进而确定所有点的正确着色。在红蓝着色过程中，如果算法发现一个顶点既应该被染成红色，又应该被染成蓝色，则可以证明该图一定不是二分图。如果始终未能找到图不是二分图的证据，则图为二分图。
定义：在图中，的每一个元素可以看作是的一个二元子集。考虑任意子集，设是一个非空有限集，令是的个子集的一个组，称二元组为一个超图。同样地，可以定义阶的概念，特别地，称为超图的秩。
（1）一个超图可确定一个二分图的点集（的分拆）定义为和的边集定义为。根据定义可得结论：超图的色数的充分必要条件是所确定的二分图是阿龙·拉姆齐的。
（2）把从超图确定二分图的过程反转过来，就可以从二分图确定一个超图，使得。这时定义的点集为，的每一点所关联的的点的集定义为的一边，所有如此得到的边的族是超图的边集。
生物体中多种生物大分子间的相互作用通常以网络模型的形式来描述。蛋白质相互作用网络以生物体内的蛋白质为结点，其间的相互关系为结点的边形成无向图。基于二分图聚类集成的方法，可设计一种融合多生物数据的二分图聚类集成方法以检测网络中的功能模块。该算法能处理蛋白质功能重叠问题，并能用二分图的表示方法来表现蛋白质与来自不同聚类方法的元聚类的从属关系。与传统方法对比，该算法更为有效。
由于知识决策、信息共享和科学研究等的需要，个人、企业、政府等数据收集者为了保证发布的数据不泄露隐私，要对收集到的信息进行隐私保护处理。基于表存储而发布的数据虽然可以实现隐私保护，但是个体间的关联信息在发布中缺失，会影响发布数据的效用。为此，可采用二分图的形式对数据进行发布，把带有标签的顶点按聚类方法进行分组，根据聚类分组结果对另外一个顶点集进行最大匹配分组，通过隐藏个体和顶点的映射关系，有效地保证了两类个体间关系的安全发布。
智能电网是工业化和信息化发展的重要组成部分，其具体场景主要有工业现场、智能园区、居民社区或办公楼宇等。随着电力业务种类的不断增多，在保证业务隔离性的前提下，还要同时考虑网络侧和电力终端用户的效用，为实际智能电网做出有效的资源分配策略。基于二分图匹配的网络切片资源分配算法。针对智能电网场景中的控制类和采集类业务，为电力终端分别制定相应的投标信息，可向多种类型的电力终端提供具有服务质量保证的服务并最大化系统效用。