用于在具有以下属性的无向图中找到 3 色三角形的分治算法？

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

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