检测邻接矩阵中的循环

Question

我们A是该图的邻接矩阵G = (V,E).A(i,j) = 1如果节点i和j边连接,A(i,j) = 0否则.

我的目标是了解是否G是非循环的.循环定义如下:

• i并j连接:A(i,j) = 1
• j并k连接:A(j,k) = 1
• k并i连接:A(k,i) = 1

我已经实现了一个解决方案,它按如下方式导航矩阵:

• 从边缘开始 (i,j)
• 选择O传出的边缘集合j,即j第 - 行中的所有1A
• O以DFS方式导航
• 如果从该导航生成的路径之一通向该节点i,则检测到循环

显然这个解决方案非常慢,因为我必须评估矩阵中的所有路径.如果A非常大,所需的开销非常大.我想知道是否有一种导航邻接矩阵的方法,以便在不使用昂贵的算法(如DFS)的情况下找到周期.

我想在MATLAB中实现我的解决方案.

提前致谢,

Eleanore.

Answer 1

在回答这个math.stackexchange问题时,我遇到了这个问题.对于未来的读者,我觉得我需要指出(正如其他人已经知道的那样)Danil Asotsky的答案是错误的,并提供了另一种方法.Danil所指的定理是A ^ k的(i,j)条目计算从G到i的长度为k 的步数.这里的关键是允许步行重复顶点.因此,即使A ^ k的对角线条目是正的,每个步行条目的计数可能包含重复的顶点,因此不会计为循环.

反例:根据Danil的答案,长度为4的路径将包含一个4周期(更不用说答案意味着P = NP,因为它可以解决Hamilton循环问题).

无论如何,这是另一种方法.当且仅当它是森林时,图是非循环的,即它具有c个分量和正好nc个边,其中n是顶点的数量.幸运的是,有一种方法可以使用拉普拉斯矩阵 L 计算分量的数量,拉普拉斯矩阵 L是通过将A的(i,i)条目替换为A的行i中的条目之和(即顶点的程度)而获得的.标记为i).然后,已知G的分量数是n-rank(L)(即,作为L的特征值的0的多重性).

因此,当且仅当边数为至少n-(n-rank(L))+ 1时,G才有一个周期.另一方面,通过握手引理,边数正好是迹线(L)的一半.所以:

当且仅当0.5*trace(L)= rank(L)时,G是非环状的.等价地,当且仅当0.5*trace(L)> = rank(L)+1时,G才有一个周期.

Answer 2

根据对Danil的观察,你需要计算A^n,这样做的效率稍高一些

n = size(A,1);
An = A; 
for ii = 2:n
     An = An * A; % do not re-compute A^n from skratch
     if trace(An) ~= 0
        fprintf(1, 'got cycles\n');
     end
end

Answer 3

如果A是有向图或无向图G的邻接矩阵,则矩阵A^n(即,n个n个副本的矩阵乘积)具有以下属性:第i行和第j列中的条目给出(有向或无向)的数量从顶点i到顶点j的长度为n的行程.

例如,如果对于某个整数n矩阵A ^ n包含至少一个非零对角线条目,则图形具有大小为n的循环.

最简单的方法是检查矩阵的非零对角线元素是计算矩阵trace(A) = sum(diag(A))(在我们的例子中,矩阵幂的元素将始终是非负的).

Matlab解决方案可以是:

for n=2:size(A,1)
   if trace(A^n) ~= 0
      fprintf('Graph contain cycle of size %d', n)
      break;
   end
end