0%

图流算法之 Bipartiteness Check

什么是二分图

定义:设 G=(V, E) 是一个无向图,如果顶点 V 可分割为两个互不相交的子集{U}、{V},并且图中的每条边 (i, j) 所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集 i∈ U,j∈ V,则称图 G 为一个二分图。二分图的一个等价定义是:不含有「含奇数条边的环」的图

二分图(Bipartite Graph)是指图中的顶点可以划分到两个不相交的集合中,同一个集合中的顶点不相邻,即同一个集合中的两个顶点之间不存在边。如下图,我可以将左侧的蓝色和紫色构成的图转化为右图的二分图,集合 A 中全由紫色顶点构成,集合 B 中全由蓝色顶点构成,只存在蓝-紫紫-蓝)边,同色顶点间不存在边。

bab01ea393c68a26dee629ce0d7e4de3.png

所以二分图又可以等价于二色图(Two-colorable Graph),以下是一些二分图的常见示例,如星状图、网格图、齿轮图等。

14bf3a04408d7eacdf1b4dc323acf58c.png

Bipartiteness Check

批处理

那么如何检测一个图是否为二分图呢?在批处理情形下,即一个图的所有顶点和所有边的信息都已明确,我们借助于二色图的思想,可以通过染色法来判断一个图是否为二分图。算法可以通过 BFS 广度优先算法来实现,具体步骤如下:

  1. 从任意一个顶点出发,将该顶点染成黑色。
  2. 遍历该顶点的所有相邻顶点,将其染成白色。
  3. 采用 BFS 依次遍历各个顶点的相邻顶点,将其染成与自身颜色相反的颜色。
  4. 当出现已访问过的相邻顶点颜色与自己相同,则该图不是二分图。否则,该图为二分图。

流处理

在流处理情形下,我们无法预知图的所有信息,取而代之的是,图的边(Edge)作为输入持续不断的流入我们的系统中。在这种情况下,考虑如何实时地判断当前所有边构成的图是否为二分图?

我们可以参考 GitHub 上的 Gelly Streaming 项目,该项目是 Flink 的一个轻量级图流处理 API,提供了一些图流分析接口,并实现了部分图的流处理算法。

Gelly Streaming 的算法核心思想仍然是染色法,具体步骤如下:

  1. 在一条边进入系统时,如果该边是已经存在的边,则丢弃;如果该边的两个顶点均不存在,则将其染成两个不同的颜色;如果该边有且仅有一个顶点已存在(已染色),则将另一个顶点染成相反的颜色。
  2. 如果该边的两个顶点均已存在,则可能出现三种情况:
  • 新边的加入使原先的图构成了「含奇数条边的环」,如下图此时若到来一条 2 - 47 - 8 的边,均破坏了二分图的性质。此时的判断条件是:两个顶点同属于一个 Component 且两个顶点的颜色相同
  • 新边的加入使原先的图构成了「含偶数条边的环」,则图依然保持二分图的性质。此时的判断条件是:两个顶点同属于一个 Component 且两个顶点的颜色相异
  • 新边的两个顶点分属不同的 Componets,如下图此时若到来一条 1 - 4 边,图依然保持二分图的性质。我们可以做简单的证明:由于之前的两个单独的 Components 均是二分图,则我们可以分别将它们的顶点划分到两个不相交的集合中{U1}、{V1}和{U2}、{V2}中且令新边(i,j)的顶点i∈ U1,j∈ V2,由此可得出由{U1}、{U2}构成的集合{U}与{V1}、{V2}构成的集合{V}不相交,未破环二分图的性质。此时的判断条件:两个顶点分属于不同的 Components。在算法实现时,我们需要将两个 Components 合并为一个 Component,即 Gelly 算法中的 merge 操作。需要注意的是,此时若两个顶点(已染色)颜色不同,则直接合并,若两个顶点颜色相同,则需要将其中的一个 Component 颜色反转

2bb51c94931f8c2b1ec93c3162d54501.png

参考