1

私はRubyとRubyグラフライブラリを使用しています http://rgl.rubyforge.org/

グラフ内のすべてのクリーク（完全なサブグラフ）を見つけるにはどうすればよいですか？

具体的には、2つの特定の頂点を含む5つのクリークを探しています。

私が本当にしていること-プロジェクトオイラー問題60

素数3、7、109、および673は非常に注目に値します。任意の2つの素数を取り、それらを任意の順序で連結することにより、結果は常に素数になります。たとえば、7と109をとると、7109と1097の両方が素数になります。これらの4つの素数の合計792は、このプロパティを持つ4つの素数のセットの最小の合計を表します。

任意の2つの素数が連結して別の素数を生成する5つの素数のセットの最小合計を見つけます。

私のグラフには素数の頂点があり、10進数の連結'pq'と'qp'が両方とも素数の場合、pからqまでのエッジがあります。

4

1 に答える 1

0

具体的には、2 つの特定の頂点を含む 5 クリークを探しています。

これらの 2 つの頂点が であると仮定する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 に答える