第02回 隣接行列と接続行列(2)

「グラフ」と言っても、前回のような単純なものばかりではない。たとえばこんなグラフはどうだろう。

上のグラフで、e1・e2のように2点を結ぶ2つ以上の辺を多重辺、e4のように同一の点を結ぶ辺をループといい、多重辺やループを持つグラフのことを多重グラフという。これに対して、多重辺やループを持たないグラフを単純グラフという。単純なネーミング（´д｀）

それでは、これらのグラフを行列で表してみよう。はてなダイアリーでは数式表示の機能があるみたいなので、今回はそれを使ってみる。

隣接行列

接続行列

この2種類の行列を見ると、ある特徴に気付く。両者に共通するのは、各行（横一列のこと）の数字の合計が、各点から伸びている辺の数（これを次数という）と一致している。また、接続行列の各列（たて一列ね）の合計は必ず2になっている。

しかし、こんのことで「ほー」とか「ふーん」とか言っていてはいけない。よく見ればこの行列、無駄な要素が多い。隣接行列は、対角成分（左上から右下にかけての数の並び）を軸として対称になっているので、n*nの配列であれば、(n^2-n)/2個の要素がダブってしまうし、接続行列に至っては各列の1,2箇所以外はすべて0になっている。

また、接続行列を実際のプログラミングに利用しようとすると配列のサイズをどれくらい確保するかに悩まなければならない。点がn個のグラフを考えたとき、すべての点がつながっていると考えると、辺の数がn(n-1)/2。ということは、単純グラフに限ったとしても、最大n*n(n-1)/2のサイズになる可能性がある。点が1000個あったとすると、隣接行列では1000×1000の配列。接続行列だと、1000×(0〜499500)←不定。

一見隣接行列の方がよさそうに見えるが、点が100000000（1億）個くらいになると、隣接行列と言えども大変なサイズになってしまう。

隣接行列や接続行列はデータ構造の基本だが、実際にプログラムを作成するときはグラフのサイズについてよく考え、問題に応じ最適なデータ構造を作らなければならない。

つづく