NetworkXと学ぶグラフ理論 その1

概ね次のものを参考にしている

離散数学への招待・上

グラフの定義

数学に限らず、ある概念を説明するためにはまず言葉の定義を行わなければならない。言葉の定義がわからないと何もわからない。まず表題にもあるグラフを定義する。

定義 集合$V$と$V$の2元部分集合族$E$の順序対$(V,E)$をグラフという。
$V$の元を頂点、$E$の元を辺という

定義としてはこれでよいが、何を言っているのか分からない人も多いかもしれない。そこでイメージして欲しい。集合$V$は例えば人間や駅、端末、回路素子などを想像してほしい。辺は例えば友達関係、線路、配線を思い浮かべるとよい。いずれも人間同士が友達同士であるかどうか、駅がつながっているのかどうか、そして電気回路そのものを表すことになる。いずれも共通しているのは何と何がつながっているか、またはつながっていないか、ということである。グラフとはどのような形でつながっているのかを一切気にせず単に点と点がつながっているかどうかを表した数学的なモデルである。以下のNetworkXでもグラフの定義に従って集合とその2元部分集合族でグラフを作っているのがわかる。集合であればよいので様々な社会モデルをグラフに表すことができる。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_nodes_from([0,1,2,3])
G.add_edges_from([(1,2),(1,3)])
nx.draw_circular(G)
plt.savefig("graph.png")
plt.close()

有名なグラフ

グラフ理論は他の数学と比べて絵で簡単に表せることあって取っ付き易い。絵にする、つまり平面などにグラフを描画するのもグラフ理論の大事な研究対象の1つであるがここでは触れない。ここでNetworkXで有名なグラフを描画する。名前の由来はグラフを見てもらえれば一目瞭然である。

import networkx as nx
import matplotlib.pyplot as plt

# 完全グラフ
k5 = nx.complete_graph(5)
nx.draw_circular(k5)
plt.savefig("K5.png")
plt.close()

# 閉路グラフ
c6 = nx.cycle_graph(6)
nx.draw_circular(c6)
plt.savefig("C6.png")
plt.close()

# 道グラフ
p4 = nx.path_graph(4)
nx.draw_circular(p4)
plt.savefig("P4.png")
plt.close()

# 完全2部グラフ
k3_3 = nx.complete_bipartite_graph(3,3)
nx.draw_circular(k3_3)
plt.savefig("K3_3.png")
plt.close()

グラフの同型

2つのグラフ$G=(V,E), G'=(V', E')$が等しいとは $V=V'$かつ$E=E'$であるときをいう。このとき$G=G'$と表す。だが頂点集合の元が違うだけで同じ構造を持つグラフは存在したとしてもこれでは違うものになる。そこで構造が同じグラフは見かけが違っていても同じとみなすためにグラフの同型を定義する。

定義 2つのグラフ$G=(V,E), G'=(V', E')$が同型であるとは$V$から$V'$への全単射$f$が存在して、すべての辺$uv$について、$uv \in E(G) \Leftrightarrow f(u)f(v) \in E(G')$ が成り立つときをいう。

グラフの不変量とは同型写像によっても値が変わらないものである。例えば頂点数、辺数がそれに当たる。同型なグラフは同じグラフであると見なすのでグラフの不変量を調べることはグラフを調べる上で不可欠である。幾何学と同様に上手い不変量を定義してそれを調べることで面白い性質を見出していくのである。

NetworkXで2つのグラフが同型であるかどうかを判定するには nx.is_isomorphic 函数を用いればよい。

import networkx as nx

G = nx.complete_bipartite_graph(2,2) # 完全2部グラフ
H = nx.cycle_graph(4) # 閉路グラフ

print(nx.is_isomorphic(G, H))

こう書くとグラフの同型判定が簡単にできるように思えてしまうがそれは大きな間違いである。例えば定義に従って$n$頂点をもつ2つのグラフが同型でないと判定するには$n!$個ある頂点間の同型写像1つ1つをチェックしなければならない。勿論、辺の本数が異なれば直ちに同型でないと判定できるが一般的な方法は知られていない。関連して、頂点数$n$の同型でないグラフは何個存在するのかを考える。同型判定が難しいのにどうやって考えればよいのか。まず、頂点数$n$のグラフの総数は$2^{\binom{n}{2}}$個ある。これは辺の候補が$\binom{n}{2}$個あり、それぞれあるかないかを考えるので$2^{\binom{n}{2}}$ある。これは同型なグラフもすべて違うものとして考えているので互いが同型で無いグラフの個数はこれよりも少ない。次に考えるのが同型写像の個数の上限である。同型写像$f: V \to V$の総数高々$n!$であるのでそれで割れば同型でないグラフの下限が求めることが出来る。難しいと分かっているからこそこのように工夫して面白いことを知ることが出来る。