r - 将网络分解为具有相同顶点数的组件

Question

我需要将一个简单的图分解成具有相同固定顶点数的组件。对于每个组件，所有顶点都应该连接。

例如，对于上面的网络，如果我们将这个网络分解为 n=3(每个组件中的顶点数)的组件，那么结果应该是 125;123;124;234。如果我们将这个网络分解成 n=4 的组件，那么结果应该是 1253;1254;1234,5234。

最简单的解决方案是列出所有可能的组合(C(n,m)，m 是网络中的顶点数，n 是每个组件中的顶点数)，然后测试每个组合的连通性。但是，当网络稀疏时效率不高。

那么，有什么想法吗？我的主要语言是 R，但其他语言也可以。

Answer 1

给定所有 n 元组连接节点子集的集合 Sn，通过遍历所有 s={a1,a2,. ..an} 并遍历所有 ai 以找到不在 s 中的连接节点 ax。构建 s'={a1,a2,...an,ax} 并添加到 Sn+1(作为集合操作消除重复)。

取 125;123;124;234;235，我们会得到

从 125: 1235;1245

从 123: 1234, (1235)

从 124:(1234)，(1245)

从 234: (1234), 2345

从 235: (1235), (2345)

我不了解 R，但 Java 的集合运算(给定一组合理的元素)足以使该算法在稀疏矩阵中具有竞争力。

差点忘了:S1 是微不足道的 ;-)