1

我正在使用 Ruby 和 Ruby 图形库 http://rgl.rubyforge.org/

如何在图中找到所有派系（完整子图）？

具体来说，我正在寻找一个涉及两个特定顶点的 5 集团。

我真正在做什么 - Project Euler Problem 60

素数 3、7、109 和 673 非常了不起。通过取任意两个素数并以任意顺序连接它们，结果将始终为素数。例如，取 7 和 109，7109 和 1097 都是素数。这四个素数之和 792 表示具有此属性的一组四个素数的最低和。

找到一组五个素数的最小总和，其中任何两个素数连接起来产生另一个素数。

如果十进制连接“pq”和“qp”都是素数，我的图有顶点素数，边从 p 到 q。

4

1 回答 1

0

具体来说，我正在寻找一个涉及两个特定顶点的 5 集团。

假设这两个顶点是first和second

common = ug.adjacent_vertices(first) & ug.adjacent_vertices(second)

for triple in common.combination(3)
    a,b,c = triple
    if ug.has_edge?(a,b) && ug.has_edge?(a,c) && ug.has_edge?(b,c)
        return [first,second,a,b,c]
于 2012-11-10T23:13:55.780 回答