誘導部分グラフ

グラフ理論において、誘導部分グラフ（ゆうどうぶぶんグラフ、）とは、部分グラフの一種であり、あるグラフから、一部の頂点を取り出し、その頂点対の辺の有無が元のグラフと一致するグラフである。部分グラフは元のグラフから任意の頂点と任意の辺を選択して取り出したグラフであるが、誘導部分グラフは任意の頂点のみを選択し、その頂点間の辺の有無は元のグラフと全て同じであるグラフである。生成部分グラフとも呼ばれる。
定義.
正式には、任意のグラフ "G" = ("V", "E") と頂点の任意の部分集合 "S" ⊂ "V" に対して、誘導部分グラフ "G"["S"] は頂点集合が "S" であり、辺集合が "E" の辺で両端点が "S" に含まれるものすべてとされる。この定義は無向グラフと有向グラフだけでなく、同じ頂点対に複数の辺が存在するものを認めたマルチグラフに対しても同様である。
誘導部分グラフ "G"["S"] はグラフ "G" をもとにした "S" による誘導部分グラフや、（"G" が曖昧ではない場合は）単に S による誘導部分グラフなどとも呼ばれる。
具体例.
誘導部分グラフの重要な例を紹介する
計算.
誘導部分グラフ同型問題は部分グラフ同型問題の一種であり、与えられたグラフがあるグラフの誘導部分グラフとして存在するかを判定する問題であるこの問題は最大クリーク問題を含む問題であるため、NP完全問題である。