graph - グラフ内のサブグラフの検索

Question

ここにグラフが表示されています。ノード B_0、B_1 がタイプ B、C_0、C_1 のノードに属しているノードにだけ。C_2、C_3 はタイプ C のノードに属します。ここで、この例で定義されているような基準を満たすことができる複数のサブグラフを見つけたいと思います -

基準 -

1. サブグラフには、タイプ A のノードが 1 つ、タイプ B のノードが 1 つ、タイプ C のノードが 1 つ、タイプ D のノードが 1 つ含まれます。
2. サブグラフには、タイプ A のノードからタイプ B の 1 つのノードへの 1 つのエッジ、タイプ B とタイプ C を接続する 1 つのエッジ、およびタイプ C とタイプ D を接続する 1 つのノードがあります。
3. サブグラフには、サブグラフからタイプ B ノードに向かうタイプ A からのエッジが 1 つ、タイプ B からタイプ C ノードの外側に向かうエッジが 1 つ、タイプ D からタイプ E の外側に向かうエッジが 1 つ含まれます。

今、この説明は次のように結果を与えるはずです-

1. サブグラフ :: A_0、B_0、C_1、D_1
2. サブグラフ :: A_0、B_0、C_0、D_0
3. サブグラフ :: A_0、B_1、C_2、D_2
4. サブグラフ :: A_0、B_1、C_3、D_3

そのようなサブグラフを見つけることができるアルゴリズムがあるかどうか知りたいですか? 可能な組み合わせをすべて作ってアルゴリズムを考えてみました。ただし、これはサブグラフのノード数に対して指数関数的になります。したがって、それを計算する効率的な方法が存在するかどうかを知りたいです。または、グラフ理論に同様の性質の問題が存在する場合は?

Answer 1

まず、タイプ A のすべてのノードにアクセスすることから始めます。各 A ノードについて、それに接続されているタイプ B のすべてのノードを調べます。そこからタイプ C のすべてのノードを調べ、アクセスしたノードを追跡します。最後の A ノードから。次に、検索基準を満たすサブノードに到達するたびに、A ノードから現在のポイントまでのノードのすべてのリストを追加します。基本的に、ノードが何に従うべきかの基準を満たしている限り、グラフをトラバースし続ける深さ優先検索を行っており、有効なノード (つまり、有効なサブグラフを生成する) がなくなるたびにバックトラックします。現在のノード。