概述
二分图(Bipartite)算法可以判断当前图是否为二分图,并返回判断结果。二分图的判断及划分在资源分配、优化分组等场景中有着广泛应用。
基本概念
二分图
二分图也称作二部图。如果将一张图中的所有节点划分成 A、B 两个集合后,图中每条边的两个端点 i、j 都分别属于这两个集合,即 i ∈ A 且 j ∈ B,或者 i ∈ B 且 j ∈ A,则称图 G 为一个二分图。
如上图所示,将图中节点划分为 “黄、红、紫” 和 “蓝、灰、绿” 两组后,组内没有边,所有边均为组之间的边,可知原图是一个二分图。
在一张图中画一条开放曲线,将节点分为两部分,并保证图中所有边都与该曲线相交一次,如果该图是二分图则能满足:将该曲线闭合时,图中每条边仍仅与该曲线相交一次。
观察上面的例子,图 A 的曲线画法满足二分图的条件,图 A 是二分图;图 B 的曲线在闭合时无法避免地与一条边相交了两次,图 B 不是二分图。
如果将含有偶数个点的环路称为偶数环,将含有奇数个点的环路称为奇数环,则由上例可以推知:二分图中的环路必为偶数环。因为当一条曲线依次穿过偶数环的各个边后,曲线的起点和终点会位于该环的同一侧(内侧或外侧);而奇数环会令曲线的起点和终点位于环的两侧,曲线为了闭合就必然会穿过同一条边两次。
染色法
染色法是判断二分图的一个基本方法。由于二分图要求把节点分为两个集合之后,任意一条边的两个端点都不能处于同一个集合中,于是可以用两种不同的颜色对全图节点进行染色,染色原则是相邻节点要染成不同的颜色,如果发现有相邻节点染成了相同的颜色,或某节点的多个邻居中出现了不同的颜色,就可以判断该图不是二分图。
上面的例子中,图 A、B 染色成功,图 C 染色失败。染色法从另一个角度证明了前面的 “偶数环” 推论:当沿着环路对点进行染色时,偶数环能保证各节点交替染成不同的颜色,而奇数环会将环上第一个进行染色的节点和最后一个进行染色的节点染成相同颜色。
特殊处理
孤点、不连通图
向图中引入纯粹的孤点(不含自环边)时,不改变原图的二分性。
分别考察不连通图中各个连通分量的二分性,只有当这些连通分量全部为二分图时,原图才是二分图。
自环边
由于自环边的两个端点是同一个节点,故图中含有自环边时,不满足二分图的条件。
有向边
对于有向边,二分图算法会忽略边的方向,按照无向边进行计算。
结果和统计值
以下面的图为例,运行二分图算法:
算法结果:无
算法统计值:二分图判断结果 bipartite_result
,1 代表是二分图
bipartite_result |
---|
1 |
命令和参数配置
- 命令:
algo(bipartite)
params()
参数无配置项
算法执行
任务回写
1. 文件回写
算法不支持文件回写。
2. 属性回写
算法不支持属性回写。
3. 统计回写
算法不支持统计回写。
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | KV | 二分图判断结果,0 代表否,1 代表是 | bipartite_result |
algo(bipartite).params() as result
return result
流式返回
算法不支持流式返回。
实时统计
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | KV | 二分图判断结果,0 代表否,1 代表是 | bipartite_result |
示例:判断当前图是否为二分图,将算法统计值定义为别名 result 并返回
algo(bipartite).params().stats() as result
return result