1

グラフは、任意の頂点が残りの頂点と接続されているグラフのサブグラフです。

k-問題では、入力は無向グラフと数値 k であり、出力は、存在する場合はサイズ k の clof (または、サイズ k のすべての cl) です。

4

2 に答える 2

3

一般性を失うことなく、グラフのノードが0からN-1までの整数で識別されると仮定します（各ノードが他の情報を運ぶ必要がある場合は、N個のノードオブジェクトの配列/ベクトル/リストを持つことができるため、一般性を失うことはありません。問題の配列へのインデックスとしてそれらの整数を取ります）。グラフの接続性は、たとえば、各ノードからノードのすぐ隣にあるセットへのマッピングで示すことができます。

接続を確認するには、即時隣接ではなく、別のマッピングが必要になります。つまり、即時隣接マッピングの推移閉包です。もちろん、そのための優れたアルゴリズムはありますが（たとえば、networkxパッケージのPythonソースコードを参照）、ブルートフォース攻撃では、隣接マッピングを接続マッピングにコピーすることから始めて、1回の反復までセットを繰り返し拡張します。セットを展開しなくなります。

たとえば、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クリークを表示できます。

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

OK、頂点の数を 1 ... n にして、グラフをブール隣接行列に変換します - (i,j) で 1 は、i と j が接続されていることを意味します。無向グラフでは、行列は対称でなければなりません。ここで、タスクはすべて 1 のサイズ kxk の「サブスクエア」を見つけることになります。「サブスクエア」は、行と列が互いに隣接している必要がないという点で面白いです。サブスクエアを取得するには、n 行、n 列から始めて、行と列の (nk) を削除します。了解しました。

これで、すべて 1 のすべての一意のサブスクエアがクリークに対応します。一意性をチェックするには、サブスクエアを不変のタプル ((i1,j1), (i2, j2) ... (ik,jk)) (Python 表記) として表します。

Python では、順序付けられていないセットにタプルを追加し、シークする要素が既に含まれているかどうかをセットに問い合わせることができます。

于 2010-01-01T17:47:56.967 に答える