NetworkXと学ぶグラフ理論その2 - 何かを書き留める何か

前回、グラフの定義を行いその同型も定義した。今回は部分グラフについて書きたい。

部分グラフ

あるグラフが別のグラフに含まれるとか含むという概念をまず定義する。

$G,G'$をそれぞれグラフとする。$V(G') \subset V(G)$ かつ $E(G') \subset E(G)$ であるとき、$G'$は$G$の部分グラフであるという。また、$V(G')$の頂点を両端点に含む辺をすべて含む部分グラフを$V(G')$から誘導される$G$の誘導部分グラフであるという。

誘導部分グラフは頂点集合$V(G')$に対して辺集合が極大であるような部分グラフであるとも言える。普通は誘導部分グラフを考えることが多い（と私は思っている）。
NetworkXでも簡単に部分グラフを作ることが出来る。以下は頂点数4の閉路グラフから頂点集合$[0, 1, 2]$から誘導される道グラフを作成している。

import networkx as nx

G = nx.Graph()   
G.add_path([0,1,2,3])
H = G.subgraph([0,1,2])
H.edges()

部分グラフに関する話で面白いのが、ある程度大きいグラフには必ずある部分グラフを含む、という話である。以下にその例を見ていきたい。

import networkx as nx

G = nx.fast_gnp_random_graph(6,0.4)

if sum(nx.triangles(G).values()):
    print("G has a triangle")

if len(nx.maximal_independent_set(G)) >= 3:
    print("G has at least three independent points")
else:
    print("Unbelievable!!!")

上記のプログラムは頂点数6のランダムグラフを作り、三角形が1つでも存在するか独立点集合の位数が3以上ならばそれらしいメッセージを出力し、それ以外では"Unbelievable!!!"と返す。なお独立点集合とは互いに隣接していない、辺でつながっていない点の集合である。
実は、"Unbelievable!!!"と返すことは無い。つまり、頂点数6以上のグラフには三角形か位数3以上の独立点集合が存在するのである。人数が増えるとある種のトラブルが発生するのと同じで、グラフも頂点数が増えると必ずある構造を含んでしまうのである。