python - 如何在图中搜索形状？

Question

我有一个 5 节点无向图的邻接矩阵 am，其中 am(i,j) = 1 表示节点 i 连接到节点 j。我生成了所有可能的通过以下代码生成此 5 节点图的版本:

import itertools
graphs = list(itertools.product([0, 1], repeat=10))

这会返回一个数组数组，其中每个元素都是矩阵的可能配置(请注意，由于矩阵是对称的，所以我只为上三角生成这些元素):

[ (0, 0, 0, 0, 0, 0, 1, 0, 1, 1),
  (0, 0, 0, 0, 0, 0, 1, 1, 0, 0),
  (0, 0, 0, 0, 0, 0, 1, 1, 0, 1),
  (0, 0, 0, 0, 0, 0, 1, 1, 1, 0),
  (0, 0, 0, 0, 0, 0, 1, 1, 1, 1),
....]

其中 (0, 0, 0, 0, 0, 0, 1, 1, 1, 1) 实际上对应于:

m =
     0     0     0     0     0
     0     0     0     0     0
     0     0     1     1     1
     0     0     0     0     1
     0     0     0     0     0

我想在此图中搜索所有可能的三角形。例如，这里 (2, 4)、(2,5) 和 (4, 5) 一起构成一个三角形:

m =
     0     0     0     0     0
     0     0     0     1     1
     0     0     0     0     0
     0     0     0     0     1
     0     0     0     0     0

是否有已知的算法可以在图中进行此类搜索？请注意，这里的三角形是一个示例，理想情况下我想找到一个可以搜索任何特定形状的解决方案，例如正方形或五边形。我如何编码这些形状以首先进行搜索？感谢任何帮助、引用、算法名称。

Answer 1

您对图形表示的解释不太好理解。

但是，当 k 是您的输入时，找到大小为 k 的循环是 NP 完全问题(因为它包括 NP 完全哈密尔顿循环问题)。如果是这样，那么您应该看看这些帖子:

Finding all cycles of a certain length in a graph

Finding all cycles in undirected graphs

但是，如果你有固定的大小长度，那么这个问题可以在良好的多项式时间内解决。这是一篇关于这个问题的文章:

Finding and Counting Given Length Cycles | Algorithmica