17

设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 中实现我的解决方案。

提前致谢，

埃莉诺。

4

8 回答 8

13

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

反例：根据丹尼尔的回答，长度为 4 的路径将包含一个 4 循环（更不用说答案会暗示 P=NP，因为它会解决汉密尔顿循环问题）。

无论如何，这是另一种方法。一个图是非循环的当且仅当它是一个森林，即它有 c 个分量并且恰好有 nc 个边，其中 n 是顶点的数量。幸运的是，有一种方法可以使用拉普拉斯矩阵L 来计算分量的数量，它是将 -A 的 (i,i) 项替换为 A 的第 i 行中的项之和（即顶点的度数标记为 i)。则可知G的分量数为n-rank(L)（即0作为L的特征值的重数）。

所以 G 有一个循环当且仅当边数至少为 n-(n-rank(L))+1。另一方面，根据握手引理，边数正好是 trace(L) 的一半。所以：

G 是非循环的当且仅当 0.5*trace(L)=rank(L)。等效地，当且仅当 0.5*trace(L) >= rank(L)+1 时，G 有一个循环。

于 2014-08-27T21:13:54.910 回答
7

根据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
于 2013-05-08T10:32:26.457 回答
5

如果 A 是有向或无向图 G 的邻接矩阵，则该矩阵A^n（即 A 的 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
于 2013-05-08T09:40:00.647 回答
1

这种方法使用 DFS，但非常有效，因为我们不会在后续的 DFS 中重复节点。

高级方法：

将所有节点的值初始化为-1。

从每个未探索的节点执行 DFS，将该节点的值设置为从0.

对于这些 DFS，更新每个节点的值，previous node's value + i/n^k其中该节点是i前一个节点的第 th 个子节点并且k是探索的深度，跳过已经探索的节点（除了检查更大的值）。

所以，一个例子n = 10：

   0.1   0.11   0.111
   j   - k    - p
0 /    \ 0.12
i \ 0.2  l
    m

1   1.1
q - o
...

您还可以使用i/branching factor+1for 每个节点来减少数字的有效数字，但这需要额外的计算来确定。

所以上面我们做了一个 DFS i，它有 2 个孩子j和m。m没有孩子，j有 2 个孩子，....然后我们完成i并从下一个未探索的节点开始另一个 DFS q。

每当您遇到更大的值时，您就知道发生了一个循环。

复杂：

您最多检查每个节点一次，并且在每个节点上进行 n 次检查，因此复杂性是O(n^2)，这与查看矩阵中的每个条目一次相同（您不能做得比这更好）。

笔记：

我还要注意，除非它是一个非常密集的图，否则邻接列表可能会比邻接矩阵更快。

于 2013-05-08T10:05:57.570 回答
0

关于矩阵方法的更多想法......引用的示例是断开连接图的邻接矩阵（节点 1 和 2 连接，节点 3 和 4 连接，但没有一对连接到另一对）。当您计算 A^2 时，答案（如上所述）是单位矩阵。但是，由于 Trace(A^2) = 4，这表明有 2 个循环，每个循环长度为 2（这是正确的）。在正确识别并从矩阵中删除这些循环之前，不允许计算 A^3。这是一个涉及多个步骤的过程，RL Norman 很好地详细说明了这一过程，“A Matrix Method for Location of Cycles of a Directed Graph”，AIChE J, 11-3 (1965) pp. 450-452。请注意：作者不清楚这种方法是否能保证找到所有循环、唯一循环和/或基本循环。

于 2014-10-26T03:20:46.367 回答
0

这也是我发现的问题。我想，解释如下：
当我们谈论循环时，我们隐含的意思是有向循环。当您考虑有向图时，您所拥有的邻接矩阵具有不同的含义；它确实是一个长度为 2 的有向循环。因此，$A^n$ 的解决方案实际上是针对有向图的。对于无向图，我想解决方法是只考虑矩阵的上三角版本（其余部分用零填充）并重复该过程。让我知道这是否是正确的答案。

于 2014-01-08T14:32:28.300 回答
0

如果有向图 G 由其邻接矩阵 M 表示，则如果其中存在循环，则 M'=(I - M ) 将是奇异的。I : M 的同阶单位矩阵

于 2014-10-27T17:52:27.367 回答
0

我无法直接添加评论，但 Casteels (@casteels) 的评论不正确：

@Pushpendre我的观点是，如果丹尼尔的答案对于有向图是正确的，那么对于无向图也是正确的，它不是。我之前评论中的反例没有您写下的邻接>矩阵；我说用>每个方向的有向边缘替换每个边缘。这给出了与无向情况相同的邻接矩阵。>您确定您没有将循环与封闭步行混淆吗？– Casteels 2015 年 4 月 24 日 > 9:20

只要一个有向图有两个顶点在两个方向上都有弧，那么它就有一个长度为 2 的循环，以及它的邻接矩阵的平方（在上面提出的“构造”中，它确实等于底层无向图），将具有非零对角系数（与非空无向图的每个邻接矩阵的平方一样，因为边立即给出从顶点到自身的长度为 2 的（非基本）游走）。所以在那种情况下，丹尼尔的回答基本上正确地检测到了一个循环。上面的推理是不正确的。

丹尼尔的回答对于有向图确实是正确的。在有向图中，一条弧不能双向遍历，因此每个封闭的有向游走都必须包含一个有向环，这将在有向图的原始邻接矩阵的某个幂的对角线上创建一个非零系数。因此，人们可以继续计算矩阵的幂，从 1 增加到顶点的数量，一旦对角线系数非零就停止。

于 2021-03-23T08:29:44.470 回答