algorithm - 用于在具有以下属性的无向图中查找三色三角形的分而治之算法？

Question

在无向图 G=(V,E) 中，顶点的颜色为红色、黄色或绿色。此外，存在一种将图划分为两个子集的方法，使得 |V1|=|V2|或 |V1|=|V2|+1，其中适用以下条件:要么 V1 的每个顶点都连接到 V2 的每个顶点，要么没有 V1 的顶点连接到 V2 的顶点。这递归地适用于 V1 和 V2 的所有导出子图

我可以通过将邻接矩阵与自身相乘三次并逐步增加与主对角线的非零项对应的节点来找到图中的所有三角形。然后我可以查看三角形的节点是否以正确的方式着色。 O(n^~2,8)!但是鉴于图形的独特属性，我想找到一个使用分而治之的解决方案来找到彩色三角形。 这是具有给定属性的示例图。我需要找到粗体三角形: 蓝色框表示分区完全连接，紫色框表示分区之间没有连接

Answer 1

它可以在 O(E*V) 中完成，而无需使用分区属性。 首先删除两个顶点上所有颜色相同的边，这可以在 O(E) 中完成。 在修改后的图 G' 中，每个三角形都是一个三色三角形。 查找图中的三角形:

for each edge e(u,v):
    for each vertex w:
        if e(v,w) and e(u,w) in G':
            add (u,v,w) to triangle list

如果保留邻接表和邻接矩阵，则可以通过仅检查 v 的邻接表中的 w 来缩短内循环的时间。 在这种情况下，复杂度为 O(E * max(deg(v))。