1

图是图的子图，其中任何顶点与其余顶点相连。

在 k- 问题中，输入是一个无向图和一个数字 k，如果存在，则输出是一个大小为 k 的 clof（或者，有时，所有大小为 k 的 cl）

4

2 回答 2

3

假设不失一般性，图的节点由 0 到 N-1 之间的整数标识（不失一般性，因为如果每个节点需要携带其他信息，您可以拥有 N 个节点对象的数组/向量/列表，并且将这些整数作为相关数组的索引）。例如，可以用从每个节点到作为该节点的直接邻居的集合的映射来指示图的连通性。

要检查连接，而不是直接邻接，您需要一个不同的映射——直接邻居映射的传递闭包。当然有很好的算法（例如，参见networkx包的 Python 源代码），但是一个蛮力算法会简单地从将直接邻接映射复制到连接映射开始，然后迭代地扩展集合直到一次迭代不再扩展任何集合。

例如，一个 Python 2.6 蛮力示例：

import copy

def transitive_closure(immediate_neighbors):
  result = copy.deepcopy(immediate_neighbors)
  changes = True
  while changes:
    changes = False
    for node in result:
      newset = set(result[node])
      for neighbor in result[node]:
        newset.update(result[neighbor])
      if newset != result[node]:
        changes = True
        result[node] = newset
  return result

immediate = {0:[1,2], 1:[0], 2:[0], 3:[4], 4:[3]}
connections = transitive_closure(immediate)
for node in sorted(connections):
  print node, sorted(connections[node])

印刷：

0 [0, 1, 2]
1 [0, 1, 2]
2 [0, 1, 2]
3 [3, 4]
4 [3, 4]

有了connections字典，我们要做的就是检查k节点的每个组合（例如，在 Python 2.6 或更好的版本中，itertools.combinations(range(N), k)为我们提供了这些组合）：如果它是一个子集（不一定是当然）连接到其任何一个成员的一组项目。

因此，例如上面的代码可以继续，以显示所有 2-cliques：

import itertools
cliques = set()
for somenodes in itertools.combinations(range(5), 2):
  if set(somenodes) <= connections[somenodes[0]]:
    cliques.add(somenodes)
print '%d cliques:' % len(cliques)
for c in sorted(cliques): print ' ', c

使用上一个示例中使用的数据打印：

4 cliques:
  (0, 1)
  (0, 2)
  (1, 2)
  (3, 4)

对于非暴力方法，我建议再次研究networkx我之前指出的源代码。

于 2010-01-01T19:03:02.523 回答
0

好的，编号顶点 1 ... n 并将图转换为布尔邻接矩阵 - 1 在 (i,j) 表示 i 和 j 是连接的。在无向图中，矩阵应该是对称的。现在你的任务减少到找到一个大小为 kxk 且全为 1 的“子正方形”。“子正方形”很有趣，因为行和列不必彼此相邻。要获得一些子正方形，您从 n 行、n 列开始，消除 (nk) 行和列 - 瞧！你说对了。

现在，所有 1 的每个唯一子方格将对应一个派系。要检查唯一性，请将子方表示为不可变元组 ((i1,j1), (i2, j2) ... (ik,jk))（Python 表示法）。

在 Python 中，您可以将元组添加到无序集合中，并询问该集合是否已经包含我们寻找的元素。

于 2010-01-01T17:47:56.967 回答