特定のグラフが他のグラフの部分グラフであるかどうかを判断する簡単な方法はありますか?

StackOverflow https://stackoverflow.com/questions/2360468

質問

特定のグラフが別の特定のグラフの部分グラフであるかどうかを確認するアルゴリズムを探しています。

この NP 完全問題をもう少し実現可能にするための条件がいくつかあります。

  • グラフには約 20 未満の頂点があります。
  • グラフはDAGです。
  • すべての頂点には非一意のラベルが付けられており、メイン グラフとサブグラフの対応する頂点には同じラベルが付いている必要があります。正しい用語を使用しているかどうかはわかりません（グラフ理論のコースを受講していないため...）。それは次のようなものになります:

折れ線グラフ A--B は A-B--A の部分グラフですが、A--A は A-B-A の部分グラフではありません。

どのような提案でも結構です。ところで、これは宿題の質問ではありません。:D

役に立ちましたか？

解決

ラベルが一意である場合、

、サイズNのグラフのために、O(N^2)縁には自己ループまたは頂点の各対の間の複数のエッジが存在しないと仮定すると、があります。エッジの数についてましょう使用Eます。

あなたが親グラフのセットのエッジをハッシュした場合、

、あなたは（必要であれば、正しい量で）それぞれが、ハッシュテーブルにあるかどうかをチェックする、部分グラフのエッジを通過することができます。あなたは各エッジのために一度にこれをやっているので、O(E)ます。

レッツ・コール（Gの頂点を持つ）グラフNと（G_1の頂点を持つ）の可能な部分グラフM、あなたはG_1 is in Gを見つけたい。

ラベルは一意ではありませんので、

は、あなたは、動的なプログラミングでは、そのような代わりとして部分問題を構築することができます - 代わりにO(2^N)の部分問題、各部分グラフのための1つを有する、あなたはO(M 2^N)の部分問題を持っている - 1をG_1頂点とMの各頂点（のために）可能サブグラフの各々と

G_1 is in G = isSubgraph( 0, empty bitmask)

と状態は、次のような設定されています：

isSubgraph( index, bitmask ) =
   for all vertex in G
       if G[vertex] is not used (check bitmask)
          and G[vertex]'s label is equal to G_1[index]'s label
          and isSubgraph( index + 1, (add vertex to bitmask) )
               return true
   return false
ベースケースはindex = Mされた状態で

、あなたはビットマスク（および暗黙のラベルマッピング）与えられた、エッジの等価性をチェックすることができます。また、あなたはまた、if文の中にチェックを行うことができます - 。ちょうど現在index与えられ、現在の部分グラフG_1[0..index]は再帰前に（同じ暗黙のラベルマッピングで）G[bitmask]に等しいことを確認してください。

N = 20の場合、これは十分に速くする必要があります。

（自分のメモを追加するか、DPアップこの使用して底部を書き換えることができます）。

他のヒント

OK、私は明白な質問をしなければなりません。 1.あなたは20個の頂点を持っています。第1の深さにおける各グラフ、アルファベット順間を歩きます     兄弟は、文字列を取得します。 2. 1つのグラフ1つの文字列が他にある別のIFFのサブグラフである。

だから、他に何がこの実行不可能？

作るために、問題の仕様に隠れています

あなたは、アライメントの問題としてこれを見ることができます。基本的には、V_2で頂点にV_1内のすべての頂点をマップする A の単射写像を思い付くしたいです。配向マップ A は、以下のようにスコア付けすることができます。

S（）= \和_ {（V、W）\ E_1における} \シグマ（V、W、（V）、（）W）、

\シグマ（V、（V）、（）W、W）1、IF（（V）、（W））\でE_2それ以外の場合は0である。

を=

私はこれはプログラム線形整数の形で配合することができると思います。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top