解説

Ｐ１課題：部分グラフ抽出

具体例を用いて説明する。 いま、図１に示すグラフＧが与えられたとする。 　　
図１　グラフＧとその隣接行列

ノード１に注目すると、これに隣接する（＝パスの長さ１で 到達できる）ノード集合は｛２, ６, ７｝である。 これに対応する部分グラフは次のようになる。 　　

Ｖ（Ｓ（１, １））＝｛1, 2, 6, 7｝, Ｅ（Ｓ（１, １））＝｛(1,2), (1,6), (1,7)｝
図２　ノード１を中心としたサイズ１の部分グラフ

ここで、Ｓ（ｉ, ｊ）は、 ノードｉを中心（出発ノード）とした、 サイズ（パスの長さ）ｊ の部分グラフを表わすものとする。

中心をノード１, ２, ..., １０としたときの、 サイズ１の部分グラフを図３（上段）に示す。

同様に、サイズ２のときの部分グラフの例を２段目に示す。

さらに続けていくと、例えば、Ｓ（１, ５）は「Ｇ」そのものとなる。 （ノード１を中心としたとき、これ以上のサイズの部分グラフは存在しない） Ｓ（１, １） ＝ 　　 Ｓ（２, １） ＝ 　　 ・・・ 　　 Ｓ（１０, １） ＝

Ｓ（１, ２） ＝ 　　 Ｓ（２, ２） ＝ 　　 ・・・ 　　 Ｓ（１０, ２） ＝

・・・ 　　

Ｓ（１, ５） ＝ 　　 Ｓ（２, ４） ＝ 　　 ・・・ 　　 Ｓ（１０, ６） ＝

図３　抽出される部分グラフの例

図４　ノード１を中心とした場合の部分グラフの抽出イメージ

補足説明

本課題の部分グラフ抽出では、 ある注目するノード（出発ノード）から、 指定されたサイズ（パスの長さ） 内に含まれるノードを探索し、 エッジについては、元のグラフ中でこれらのノード集合が持っている 隣接関係をそのまま抽出すれば良い。

例えば、図５の場合、ノード２を中心として、サイズ２で到達 できるノード集合は｛１, ２, .., ６｝の全てであり、結果として 得られる部分グラフは、元のグラフそのものとする。

ノード４と６との間のエッジは、ノード２を出発点とする 長さ２のパスには含まれないが（図５の左）、 これをわざわざ除外する必要はない。 　　 ─×→ 　　
図５　ノード２を中心としたサイズ２の部分グラフ
（ここで想定しているのは、右の元のグラフそのもの）

※ このように、一口に「部分グラフ」と言っても、その定義は 複数考えられる。 （例えば、ノード１のみ（エッジを含まない）ものも部分グラフの一つで あるし、また非連結グラフ（分離グラフ）となるようなものも考慮すると その組み合わせは爆発的に増える）
余力があれば、このような部分グラフの特徴と、その抽出アルゴリズムに ついても考えてみると良い。