誘導部分グラフ

誘導部分グラフ（ゆうどうぶぶんグラフ、英: induced subgraph）とは、グラフ理論における部分グラフの一種であり、あるグラフから、一部の頂点を取り出し、その頂点対の辺の有無が元のグラフと一致するグラフである。部分グラフは元のグラフから任意の頂点と任意の辺を選択して取り出したグラフであるが、誘導部分グラフは任意の頂点のみを選択し、その頂点間の辺の有無は元のグラフと全て同じであるグラフである。生成部分グラフとも呼ばれる。

グラフ G における部分グラフの例。部分グラフ G₂、G₃ は誘導部分グラフであるが、部分グラフ G₁ は誘導部分グラフでない。

定義

正式には、任意のグラフ G = (V, E) と頂点の任意の部分集合 S ⊂ V に対して、誘導部分グラフ G[S] は頂点集合が S であり、辺集合が E の辺で両端点が S に含まれるものすべてとされる^[1]。この定義は無向グラフと有向グラフだけでなく、同じ頂点対に複数の辺が存在するものを認めた多重グラフ（英語版）に対しても同様である。

誘導部分グラフ G[S] はグラフ G をもとにした S による誘導部分グラフや、（G が曖昧ではない場合は）単に S による誘導部分グラフなどとも呼ばれる。

具体例

誘導部分グラフの重要な例を紹介する。

Snake-in-the-box問題とは、立方体グラフの最長の誘導パスを求める問題である。

• 誘導パスは、道である誘導部分グラフのことである。辺に重みがついていない場合にはグラフの任意の2頂点間の最短経路は誘導パスである。なぜなら、その経路に新たに辺を追加した場合、その辺が誘導パスを誘導パスでなくす場合には、経路が最短ではなくなるからである。逆に、距離遺伝グラフでは、全ての誘導パスは最短経路になる^[2]。
• 誘導サイクルは、閉路（サイクル）をなす誘導部分グラフのことである。グラフの内周は「最短閉路の長さ」と定義され、その閉路は常に誘導サイクルである。強いパーフェクトグラフ定理によれば、誘導サイクルとその補グラフはパーフェクトグラフの特徴付けにおいて重要な役割を担う^[3]。
• クリークと独立集合は、それぞれ完全グラフまたは空グラフの誘導部分グラフに対応する。
• 頂点の近傍とは、その頂点と、その頂点と辺で直接繋がっている全ての頂点の誘導部分グラフである。

計算

誘導部分グラフ同型問題は部分グラフ同型問題の一種であり、与えられたグラフがあるグラフの誘導部分グラフとして存在するかを判定する問題である。この問題は最大クリーク問題を含む問題であるため、NP完全問題である^[4]。