誘導サブグラフ

グラフ理論では、グラフの誘導サブグラフは、グラフの頂点のサブセットと、そのサブセット内の頂点のペアを接続する元のグラフの すべてのエッジから形成される別のグラフです。

正式には、 を任意のグラフとし、 をGの任意の頂点の部分集合とします。すると、誘導部分グラフとは、頂点集合が であり、辺集合がの両方の端点を持つ 内のすべての辺から構成されるグラフです。^[1]つまり、任意の 2 つの頂点、、について、 が で隣接している場合に限り、 で隣接しています。同じ定義が、無向グラフ、有向グラフ、さらにはマルチグラフにも適用されます。 ${\displaystyle G=(V,E)}$${\displaystyle S\subseteq V}$${\displaystyle G[S]}$${\displaystyle S}$${\displaystyle E}$${\displaystyle S}$${\displaystyle u,v\in S}$${\displaystyle u}$${\displaystyle v}$${\displaystyle G[S]}$${\displaystyle G}$

誘導サブグラフは、によってに誘導されるサブグラフとも呼ばれ、または (文脈上 の選択が明確であれば) の誘導サブグラフとも呼ばれます。 ${\displaystyle G[S]}$${\displaystyle G}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$

誘導サブグラフの重要なタイプには以下のものがあります。

• 誘導パスは、パスである誘導サブグラフです。重みなしグラフ内の任意の2つの頂点間の最短パスは常に誘導パスです。これは、頂点のペア間の追加のエッジが誘導パスにならないようにすると、最短パスにもならないためです。逆に、距離遺伝グラフでは、すべての誘導パスが最短パスです。^[2]
• 誘導サイクルは、サイクルである誘導サブグラフです。グラフの内周は、その最短サイクルの長さによって定義され、それは常に誘導サイクルです。強い完全グラフ定理によれば、誘導サイクルとその補数は、完全グラフの特徴付けにおいて重要な役割を果たします。^[3]
• クリークと独立集合は、それぞれ完全グラフまたはエッジのないグラフである誘導されたサブグラフです。
• 誘導マッチングは、マッチングである誘導サブグラフです。
• 頂点の近傍は、その頂点に隣接するすべての頂点の誘導サブグラフです。

誘導部分グラフ同型問題は、あるグラフが別のグラフの誘導部分グラフとして見つかるかどうかをテストすることを目的とした部分グラフ同型問題の一種である。クリーク問題を特別なケースとして含んでいるため、 NP完全である。^[4]