誘導部分グラフ
1. 序章
このチュートリアルでは、誘導部分グラフとは何かを説明します。 また、それを構築する方法、（サブ）グラフが誘導されているかどうかを確認する方法、および誘導されたグラフ同型を見つける方法も示します。
2. サブグラフ
グラフがあるとします。ここで、はノードのセットであり、ノード間のエッジを示します。 のサブグラフは、およびのような任意のグラフです。 言い換えると、
たとえば、これらすべてのグラフは次のとおりです。
次のサブグラフとしてリストできます。
3. 誘導部分グラフ
誘導部分グラフは、部分グラフの特殊なケースです。 がのノードのサブセットである場合、によって誘導されるのサブグラフは、頂点のセットとしてを持ち、に両方の端点を持つすべてのエッジを含むグラフです。 この定義は、有向グラフと無向グラフの両方を対象としています。 また、重み付けされていないものと同じように重み付けされたものもカバーします。
とが与えられると、誘導部分グラフは一意になります。 上のグラフで誘導されたサブグラフは1つだけです。
3.1. 違いは何ですか？
誘導部分グラフと通常の部分グラフの概念は非常に似ています。 違いは、誘導部分グラフには、誘導セットに両方の端点があるすべてのエッジが含まれているのに対し、通常のサブグラフでは一部が欠落している可能性があることです。
したがって、誘導部分グラフは、非隣接のみを保持する通常のサブグラフとは対照的に、誘導頂点の隣接と非隣接の両方を保持します。
4. 誘導部分グラフの問題とアルゴリズム
誘導部分グラフに関連するいくつかの問題を紹介しましょう。
4.1. 誘導部分グラフの構築
時間計算量は、グラフの表現方法によって異なります。 リンクリストを使用して、ノードに入射する各エッジを2回トラバースするため、時間計算量はです。 一方、 matrixes を使用する場合は、各誘導ノードのエントリの行全体をトラバースします。 したがって、複雑さはになります。
4.2. サブグラフが誘導されているかどうかを確認する方法
この問題では、グラフとそのサブグラフ（soと）があります。 私たちの目標は、が誘導部分グラフであるかどうかを確認することです。そうするために、で入射するエッジを反復処理します。 にないエッジが見つかった場合、隣接関係が保持されないため、誘導部分グラフではないと結論付けることができます。 それ以外の場合は、それが誘発されたと結論付けます。
以前と同様に、複雑さはグラフの表現方法によって異なります。
にないエッジが含まれているかどうかを確認する必要はありません。 これは、入力を定義した方法によるものです。 これはのサブグラフであることがわかっているため、にないエッジを含めることはできません。
4.3. グラフが誘導部分グラフであるかどうかを確認する方法
ただし、のいくつかのノードのグラフとして取得する場合は、サブグラフであるか、それが誘導されるかを確認する必要があります。
4.4. 誘導部分グラフ同型
誘導部分グラフ同型（ISI）は、あるグラフから別の誘導部分グラフへの単射マッピングです。 したがって、入力で取得し、前者から後者へのISIマッピングを見つけます。
前の2つの問題とは異なり、ノードに同じラベルを使用しないでください。 したがって、：の誘導部分グラフに変換されるマッピングを見つける必要があります。
正式には、それが以下を満たしている場合に限り、それはISIであると言います。
(1)
最初の条件は、それが単射関数であることを示しています。 2つ目は、ISIが隣接関係を保持することであり、3つ目は、非隣接関係も保持することです。
この問題はNP困難です。これは、これを解決するための多項式時間アルゴリズムが現在まで知られていないことを意味します。 制約充足問題（CSP）として扱い、他のCSPと同じように解くことができます。 方程式（ 1 ）は、CSPを定義し、それをユニバーサルソルバーに供給するために必要なすべての制約を示しています。 各forはCSP変数に対応し、各変数はそのドメインとしてセット全体を持ちます。
5. 結論
この記事では、誘導されたサブグラフと通常のサブグラフについて説明しました。 また、前のサブグラフに関連するいくつかの一般的な問題を提示しました。 それらは、誘導部分グラフの構築、検証、および同型です。
