誘導部分グラフ

誘導部分グラフについて

概要

誘導部分グラフ（ゆうどうぶぶんグラフ）は、グラフ理論における重要な概念の一つです。このグラフは、元のグラフから特定の頂点を選び、その選ばれた頂点間の辺が元のグラフの構造をそのまま引き継ぐ形態です。部分グラフ自体は元のグラフから任意の頂点および辺を選ぶことで作成できますが、誘導部分グラフは特にその選ばれた頂点だけに基づいており、その頂点間の辺の存在が元のグラフと一致する必要があります。これにより、誘導部分グラフは特定の頂点の相互関係を保持したものとなります。

定義

誘導部分グラフを定義すると、任意のグラフ G = (V, E) と任意の頂点の部分集合 S ⊂ V に基づいて、誘導部分グラフ G[S] は次のように表されます。頂点の集合は S であり、辺の集合は、元のグラフ G の辺 E の中で端点が両方とも S に含まれるものから構成されます。この定義は無向グラフ、有向グラフだけでなく、同一の頂点間に複数の辺が存在する多重グラフにも適用されます。

このように、誘導部分グラフ G[S] は、特定の頂点集合 S によって誘導された部分グラフであるため、単に「S による誘導部分グラフ」と呼ばれることもあります。

具体例

誘導部分グラフの実際の用途を理解するために、いくつかの重要な例を挙げます。

• - 誘導パス: これは、選ばれた頂点間を結ぶ経路のことで、エッジに重みが付いていない場合には、任意の2頂点間の最短経路になります。新たなエッジを追加すると、最短経路という条件が崩れるため、誘導パスとしての定義が失われます。距離遺伝グラフの場合、すべての誘導パスが最短経路となります。

• - 誘導サイクル: これは、閉路を形成する誘導部分グラフの一種で、グラフ内の最も短い閉路の長さとして定義されます。この閉路は常に誘導サイクルになります。また、強いパーフェクトグラフ定理においては、誘導サイクルとその補グラフはパーフェクトグラフの特性を示す重要な要素です。

• - クリークと独立集合: それぞれ、完全グラフや空グラフの誘導部分グラフと関連しています。これにより、クリークや独立集合の理解も深まります。

• - 頂点の近傍: 指定された頂点と、称点に直接つながっている頂点間で形成される誘導部分グラフが含まれます。

計算

誘導部分グラフ同型問題は、特定のグラフが他のグラフの誘導部分グラフであるかどうかを判断する問題に該当します。この問題は、他の計算問題に比べて複雑であるため、NP完全問題とされています。特に、最大クリーク問題を内包しているため、解決することが非常に難しいとされています。

まとめ

誘導部分グラフは、グラフの構造や頂点間の関係を理解する上で非常に有力なツールです。特定の条件を持つ部分グラフの概念は、さまざまなグラフ理論の問題解決にも応用されるため、その理解は重要です。特に、計算問題としての特徴も学ぶことで、グラフ理論の深い知識に繋がります。

もう一度検索