如何从八度中的邻接矩阵中找到三角形的节点

Question

我知道如何在邻接矩阵中找到三角形的数量。

tri = trace(A^3) / 6

但是我需要找到节点，以便最终可以从邻接矩阵中找到边的值，因为它是一个符号图。是否已经存在执行该功能的功能？

Answer 1

获得邻接矩阵的幂会丢失有关中间节点的信息。而不是二维矩阵，我们需要3维。

给出图表：

及其邻接矩阵：

A =

  0  0  0  0  1  1  0  1  0  0
  0  0  0  1  0  1  0  0  0  0
  0  0  0  1  0  0  0  1  0  1
  0  1  1  0  1  0  1  0  0  0
  1  0  0  1  0  0  1  0  0  0
  1  1  0  0  0  0  0  1  1  0
  0  0  0  1  1  0  0  0  1  0
  1  0  1  0  0  1  0  0  0  0
  0  0  0  0  0  1  1  0  0  0
  0  0  1  0  0  0  0  0  0  0

计算3d矩阵T，以便在图形T(i,j,k) == 1中存在路径的情况下计算i=>j=>k=>i。>>

T = and(A, permute(A, [3 1 2]))
这等效于对邻接矩阵进行平方运算，但保留路径信息。在and是加权邻接矩阵的情况下，此处使用A代替乘法。如果沿第二维求和，将得到A^2：

>> isequal(squeeze(sum(T,2)), A^2)

ans = 1
现在我们有了长度为2的路径，我们只需要过滤，所以我们只保留返回其起点的路径。

T = and(T, permute(A.', [1 3 2]));   % Transpose A in case graph is directed
现在，如果为T(i,j,k) == 1，则存在一个三角形，该三角形从节点i开始，经过节点j和k，然后返回到节点i。如果要查找所有此类路径：

[M,N,P] = ind2sub(size(T), find(T));
P = [M,N,P];
P将是所有三角形路径的列表：

P =

   8   6   1
   6   8   1
   7   5   4
   5   7   4
   7   4   5
   4   7   5
   8   1   6
   1   8   6
   5   4   7
   4   5   7
   6   1   8
   1   6   8
在这种情况下，我们获得12条路径。无向图中的所有路径均具有6个重复项：一个重复项始于每个三角形点，乘以2个方向。与trace的结果相同：

>> trace(A^3)
ans =  12
    

Answer 2

这里是使用矩阵乘法的解决方案：