如何在图表中找到三角形？

Question

这是算法设计手册中的练习.

考虑确定给定的无向图G =(V,E)是否包含长度为3的三角形或周期的问题.

(a)给O(| V | ^ 3)找到一个三角形(如果存在).

(b)改进算法以及时运行O(| V |·| E |).你可以假设| V | ≤| E |.

观察到这些边界为您提供了在G的邻接矩阵和邻接列表表示之间进行转换的时间.

这是我的想法:

(a)如果图形作为邻接列表给出,我可以通过O(| V | ^ 2)将列表转换为矩阵.然后我做:

for (int i = 0;i < n;i++) 
   for (int j = i+1;j < n;j++) 
   if (matrix[i][j] == 1) 
      for (int k = j+1;k < n;k++) 
         if (matrix[i][k] == 1 && matrix[j][k] == 1)
             return true;

这应该给出O(| V | ^ 3)来测试三角形.

(b)我的第一个直观是如果图形作为邻接列表给出,那么我将做一个bfs.例如,每当发现交叉边缘时if y-x is a cross edge,我会check whether parent[y] == parent[x], if true, then a triangle is found.

谁能告诉我我的想法是否正确？

同样对于这个(b),我不确定它的复杂性.应该是O(| V | + | E |),对吧？

我怎么能在O(| V |*| E |)中做到这一点？

Answer 1

一个可能的O(|V||E|)解决方案,与(a)中的蛮力相同:

for each edge (u, v):
  for each vertex w:
     if (v, w) is an edge and (w, u) is an edge:
          return true
return false

检查所有边,而不是所有顶点对 - 与另一个形成三角形的顶点 - 确定边和顶点是否形成可行解是足够的信息.

BFS解决方案的反例:

       A
     / | \
    /  |  \
   B   C   D
   |   |   |
   |   |   |
   F---G---H
   |       |
   ---------
    (F, H) is also an edge

请注意father[F] != father[G] != father[H],因此算法将返回false - 但是,(F,G,H)是一个可行的解决方案!

Answer 2

如果您有邻接矩阵,则可以通过对矩阵求平方并查看原始矩阵和方阵在同一位置是否具有非零条目来查找三角形.

天真矩阵乘法需要时间O(n^3),但有快速矩阵乘法算法可以做得更好.其中最着名的是Coppersmith-Winograd算法,该算法O(n^2.4)及时运行.这意味着算法类似于:

• 使用O(V^2)时间转换为邻接矩阵.
• 使用O(V^2.4)时间计算邻接矩阵的平方.
• 使用O(V^2)时间检查矩阵是否重合非零条目.
• 您在其中找到重合非零条目的行和列的索引(如果有)告诉您两个涉及的节点.
• 使用O(V)时间缩小已知节点共有的第三个节点.

总的来说这需要O(V^2.4)时间; 更确切地说,需要长矩阵乘法.您可以在此算法和if-any-edge-end-points-have-a-common-neighbor算法之间动态切换,这些算法可以在他们的答案中解释,以便将其改进O(V min(V^1.4, E)).

这是一篇更深入探讨问题的论文.

这个问题是如何依赖理论发现的.如果关于矩阵乘法实际上是二次转出是真实的猜想,那么你会得到必然的一个非常好的时间O(V^2)或O(V^2 log(V))之类的东西.但是,如果量子计算机能够运行,我们将能够做得更好(类似O(V^1.3))!