5
4

4 に答える 4

5

問題はNP-Complete 1です。

クリーク問題2からの還元。クリーク問題のインスタンス (グラフ) が与えられた場合、 のようなG=(V,E)完全なクリーク を作成します。G'=(V,E')E' = {(u,v) | u != v, for each u,v in V)

最大クリーク問題の解は、G と G' の最大部分グラフ問題の解と同じです。クリーク問題は NP 困難であるため、この問題も同様です。

したがって、この問題に対する既知の多項式解はありません。

正確なアルゴリズムを探している場合は、徹底的な検索アプローチや分岐限定アプローチを試して解決できます。悪いニュースで申し訳ありませんが、少なくとも (おそらく) 存在しないものを探してはいけません (もちろんP=NPでない限り)。

編集：問題に対する指数関数的なブルートフォースソリューション：
可能なすべてのサブセットをチェックし、それが実行可能なソリューションであるかどうかを確認できます。
疑似コード:

findMCS(vertices,G1,G2,currentSubset):
  if vertices is empty: //base clause, no more candidates to check
      if isCommonSubgraph(G1,G2,currentSubset):
         return clone(currentSubset)
      else:
         return {}
  v <- vertices.pop() //take a look at the first element
  cand1 <- findMCS(vertices,G1,G2,currentSubset) //find MCS if it is NOT in the subset
  currentSubset.append(v)
  if isCommonSubgrah(G1,G2,currentSubset): //find MCS if it is in the subset
     cand2 <- findMCS(vertices,G1,G2,currentSubset)
  currentSubset.remvoe(v) //clean up environment before getting back from recursive call
  return (|cand1| > |cand2| ? cand1 : cand2) //return the maximal subset from all candidates

上記の複雑さはO(2^n)(すべての可能なサブセットをチェックする) であり、次のように呼び出します: findMCS(G1.vertices, G1, G2, [])(ここで[]は空のリストです)。

ノート：

  • isCommonSubgrah(G1,G2,currentSubset)currentSubsetがG1 と G2 の共通部分グラフである場合にのみ true と答える、計算が簡単な方法です。
  • |cand1| と |cand2| これらのリストのサイズです。

(1) 最大部分グラフは、それぞれが含まれている場合にのみ含まれる部分集合でUあると仮定します(直観的には、2 つのグラフでまったく同じエッジを共有する頂点の最大部分集合)。Vu1,u2U (u1,u2)E1(u1,u2)E2

(2) クリーク問題: for each in :またはis inのようなG=(V,E)最大部分集合の検索のインスタンスが与えられた場合。UVu1,u2Uu1 = u2(u1,u2)E

于 2013-02-01T10:22:17.970 に答える
0

主な問題は、元のグラフのノード間の対応を見つけることです (基本的に頂点の再番号付け)。たとえば、グラフg1にノードpがあり、グラフg2にノードqがあり、 pとqが等しい場合、それらを共通サブグラフcのノードsにマッピングしたいと思います。

クリーク問題が非常に難しい理由は、異なるグラフの 2 つのノードが実際に同じノードを参照しているかどうかを確認する方法がないため、ノードのペアの可能なすべての組み合わせを試して、各ペアが一貫しており、 「最高」の対応。

これらのグラフのノードは地理的な位置を表すため、あるグラフのノードが他のグラフのノードと同じである可能性を示す妥当な距離メトリックを考え出すことができるはずです。2 つのノードの GPS 座標はおそらく同一ではないため、この問題に基づいていくつかの仮定を行う必要があります。

  • グラフmとして表される、データ ポイントが発生する領域のマップがある場合、 g1およびg2のノードの番号を変更したり名前を変更したりして、 mの最も近いノードに対応させることができます。
  • 距離 (元のグラフとmの間、またはg1とg2の点の間) は、グラフにとってより意味のあるものに応じて、ユークリッド距離またはマンハッタン距離のいずれかになります。
  • 2 つのノードがどれだけ離れていて、同等と見なされるかを慎重に判断する必要があります。小さすぎると一致しません。大きすぎると、グラフ全体が 1 つのノードに凝縮される可能性があります。
  • 元のグラフの 2 つ以上のノードがすべてcの同じノードにマップされる可能性があります。たとえば、ノード間の距離に関連して位置データが頻繁に更新される場合。
  • 逆に、元のグラフの連続するノードのペア間のエッジは、距離に比べて更新頻度が低い場合、複数のエッジを含むパスにマッピングすることもできます。したがって、これらの中間ノードを共通グラフに導入するか、パス全体を単一のエッジとして扱うことが理にかなっているのかを判断する必要があります。

ノードの再番号付けを取得したら、Jens が提案する方法を使用して、再番号付けされたグラフの交点を見つけることができます。あなたの具体的な問題についてはあまり詳しくないので、これはすべて非常に一般的なものですが、うまくいけば、あなたが始めるのに十分です.

于 2013-02-04T23:25:13.077 に答える
0

あるグラフが他のグラフのサブグラフであるかどうかを確認することさえできません。これは、NP完全であることが知られているサブグラフ同型問題です。これにより、同形プロパティを（多項式時間で）チェックできないため、最大サブグラフを見つけることができません。

于 2013-02-01T13:07:21.147 に答える