matlab - 在邻接矩阵中形成循环的节点 (Matlab)

Question

我有一个带有有向边的邻接矩阵。计算 A^3，将帮助我检测矩阵中是否存在长度为 3(三角形)的循环。但是，我想知道哪些节点形成三角形。我怎样才能在Matlab中实现这一点？

谢谢

Answer 1

矩阵乘法的问题在于它将所有行相加。当您乘以矩阵的第一行P时按矩阵第一列Q ，它进行逐元素乘法，然后生成结果向量的总和，丢弃有关中间节点的所有数据。好吧，我们想要那个向量，所以让我们阻止它把它们相加。

假设我们有邻接矩阵 A :

A =

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

我们想找出从节点 x 是否有任何路径(还不是循环)到节点z穿过节点y 。行x告诉我们哪些节点具有 x 中的边至y ，和列z告诉我们哪些节点具有 y 中的边至z 。如果我们按元素进行 AND行数x和列z ，我们应该得到所有节点 y 的向量连接到x和z .

例如，如果我们 AND行1和列3对于这个邻接矩阵:

A =

   0   1   0   0   0
   x   x   1   x   x
   x   x   0   x   x
   x   x   0   x   x
   x   x   0   x   x 

>> A(1,:) & A(:,3).'   %// remember to transpose the column first...
ans =

   0   1   0   0   0 

我们看到它们通过节点2连接。太棒了，现在我们知道对于这种情况我们有一条路径 1->2->3 。但一般来说，1 可能有多个路径。至3 ，所以我们将使用整个向量。

现在我们要做的就是确保有一条来自节点 3 的路径返回节点1 。好吧，那就是 3 ，栏1在我们的邻接矩阵中。如果我们AND A(3,1)对于我们的向量，如果有来自 3 的边缘，我们应该返回相同的向量。至1如果不存在则返回零(因此没有循环)。

>> (A(1,:) & A(:,3).') & A(3,1)
ans =

   0   1   0   0   0 

概括这一点，来自 x 的每条路径的向量至z是

C(x,:,z) = (A(x,:) & A(:,z).') & A(z,x);

不幸的是，我一直无法找到一种方法来向量化它，所以一个双 for循环现在就足够了:

for x = 1:size(A,1)
   for z = 1:size(A,2)
      C(x,:,z) = (A(x,:) & A(:,z).') & A(z,x);
   end
end

生成的矩阵将有 C(x,y,z) = 1如果有一个从 x 开始的循环至y至z (和背面)，和 0否则。请注意，每个周期将列出 3 次:

C(x,y,z) == C(y,z,x) == C(z,x,y)