The Unfounded Moore Graph

Abstract

　グラフ理論で60年くらい前から研究されてきている "Degree Diameter Problem" という問題があります. 本記事ではこれについて簡単な説明を与えます. そしてこの問題の最適解の一つである "Moore Graph" について書いていきます. しかし今現在もなお, とある Moore Graph は今もなお見つかっておらず, 存在しないのではないかとさえ言われています. (存在性の否定も肯定も2017年2月2日現在未解決です). 

　未だにみつかっていない Moore Graph の存在性はいわばパズルのようなものであり, 電車の暇な時に考えてると時間を簡単につぶせるような, 面白い問題だと思ってます. 

　この記事では特に事前知識を仮定しません. グラフ理論やアルゴリズムの基本的な用語(幅優先探索, 次数, 最短経路) が分かっていれば誰でも理解できると思います. この記事を読んでチャレンジしてみようという気が起きる方が少しでも増えてくれたら嬉しいです.

Introduction

　連結な無向グラフ $G=(V,E)$ が与えられたとき, $D:=\max_{s,t\in V} \mathrm{dist}(s,t)$ を $G$ の直径と呼びます. ここで $\mathrm{dist}(s,t)$ は二頂点間の最短経路長と定義します.

言い換えると, どの二頂点を選んでも $D$ ステップあれば必ず互いに到達できるような $D$ のうち最小の値が直径といえるわけです. 直径 $L$ の円 $C$ を考えるときに, 任意の二点 $x,y\in C$ に対し, $|x-y| \leq L$ となるわけなので, いわゆる円に対する直径のアナロジーとしても自然な定義だと思います.

　少し余談になりますが, しばしば直径が小さいということが話題になることがあります. 特に有名なのが複雑ネットワークの「スモールワールド性」です. これは Facebook や 論文のcitation が構成するネットワークを考えるとその直径が小さいということを意味しています. なぜ直径が小さくなるのか？といった疑問に対し, 複雑ネットワークを生成するようなモデル(有名なものとしてBAモデルがあります)を考え, そのモデルによって生成されたグラフの直径を考察する, というような研究が多くあります.

　さて, 今回も小直径なグラフの話題になります. 頂点数 $n$ のグラフ $G$ のうち, 直径が最小のものを見つけよ, という問題を考えます, 考えるまでもないことですが, $G$ を $n$ 頂点の完全グラフとすれば明らかに $D=1$ で最小となるので, 自明な答えが得られます.

　一方で, 「各頂点の次数が $d$ 以下」 という制約条件を付加することにより, 問題は格段と難しくなります. この問題は Order Degree Problem と呼ばれる問題で, 非常に難しい問題であることが知られていて, NIIがこの問題に関するコンペティションを年一回開いています(Graph Golf). このコンペティションでは, $n,d$ が与えられるので, 出来るだけ直径が小さいグラフを作れというようなコンテストです. 詳細はページを見てください.

一方で, 「各頂点の次数は $d$ 以下」 かつ 「直径が$D$以下」 となるようなグラフのうち, 頂点数が最大のものを求めよ, という問題も考えられると思います. この問題は Degree Diameter Problem と呼ばれ, こちらの問題も難しいとされているのですが, 実はグラフ理論ではこの問題は有名問題で, 色んな研究があります.

Moore Bound

Edward F. Moore

　それらの研究の中でも最も基本的なワードの一つが "Moore Bound" です. Moore とは Edward F. Moore のことで, オートマトンの分野で知られている「エデンの園定理」を示した人物です.

　例として直径2, 各頂点の次数が3であるようなグラフ $G$ の持ちうる頂点数の上界について見ていきます. $G$の頂点 $r$ を任意に一つ選び, $r$を始点として幅優先探索を行うことを考えます. $G$ の直径は2なので, 幅優先探索は深さが高々2までしか探索しないので, 次のような図が出てくるはずです.

　したがって, 次数の制約から, 頂点数を最大にしようとすると次のようなグラフを考えることになります:

BFS-tree

　これ以上頂点を多くしようとすると, 直径または次数の制約どちらかが破られてしまうので, 直径2次数3のグラフの頂点数は高々10であるということが分かると思います. 即ちこの10という値は頂点数の上界を与えています.

　このように考えると, 直径 $D$ , 次数 $d$ であるようなグラフの持ちうる頂点数の上界は

$1+d+d(d-1)+d(d-1)^2+\cdots+d(d-1)^{D-1}$.

で与えられます. この上界は Moore Bound と呼ばれます.

Moore Graph

ここで, Moore Bound はタイトなのかという疑問が自然に生じてきます. Moore Boundの導出の際に頂点 $r$ を一つ固定して幅優先探索を考えていましたが, どの頂点を始点にしても同じBFS木が生成されるようなグラフでなければならないので, タイトであるかどうかは非自明な問題となってきます. 実は上の例で紹介した $D=2, d=3$ ではこの上界を達成する (即ち頂点数10)ようなグラフが存在します. 次の図で示すグラフが該当します:

Petersen Graph

　実際, 各頂点の次数は3に等しく, しかもどの二頂点を選んでも二歩以内に互いに到達することが出来ることが確認できると思います. この図に示したグラフは Petersen Graph と呼ばれる非常に有名なグラフで, $D=2, d=3$の場合はこのグラフのみが Moore Bound を達成するグラフであることが示せます. (即ち, uniqueです) このように, Moore Bound と等しい頂点数を持つようなグラフのことを Moore Graph と呼びます.

When do Moore Graphs exist?

$D \geq 2$ のときにMoore Graph が存在するかどうかという問題について, 結果から言うと

• $D>2$のときは存在しない.
• $D=2$ かつ $d\neq 2,3,7,57$ のときは存在しない.

ことが示されます. 2番目の事実は隣接行列の固有値を考えることで示すことが出来ます[1].

2番目の事実ついて, $D=2$の場合:

• $d=2$ : 長さ5の閉路
• $d=3$ : Petersen graph
• $d=7$ : Hoffman-Singleton graph
• $d=57$ : unknown

です. $d=57$のときは "Moore graph が存在するかもしれない" という可能性はあるのですが, 未だに見つかっておらず, その存在性は2017年2月2日現在でも未解決問題です.

また一方で, Moore bound に近い頂点数を持つようなグラフを構成するという研究も存在します. これらの分野では, グラフのCartesian product などを考えて構成していくというもので, 僕はあまり詳しくはないのですが, Algebraic Graph Theory などの分野だと思っています. 詳しくは[1]にあります.

面白い事実としては, 頂点数$n$が次数$d$に対して $n=d^2$となるようなグラフの中で直径が2であるようなものは, $d=2$を除いて他には存在しないという定理が知られています[2]. しかし$n=d^2+1$の場合はMoore Graph そのものなので, いかにMoore Graph が珍しいグラフであるかが分かると思います.

Some Characteristics of the UNFOUNDED Moore Graph

頂点数を$n$, 次数を$d$とし, $n=d^2+1$のケースを考えます.

Moore graph の満たす性質を幾つか挙げていきます.

- No Triangles, No squares

三角形と四角形を含まない. $\iff$ Moore graph である $\iff$ 直径が2である.

を示すことが出来ます.

証明は簡単で, 三角形や四角形を含むグラフに対し, その三角形(または四角形)に含まれる頂点を一つ選んで $r$ とし, $r$を始点として幅優先探索を行うと, 次の図のようになります.

橙色の頂点は四角形

　すると$n \leq d^2$となってしまうので矛盾します. 逆向きも簡単に示すことが出来ます.

- Equation for Adjacency Matrix

次に, Moore graph の隣接行列を $A$ と書くと, 次の方程式が成り立ちます:

$A^2+A = (d-1)I + J$.

　ここで $I$ は単位行列, $J$ は全ての成分が1の行列です. これも簡単に分かります.　

　$A^2$ の $ij$成分は 頂点$i$ から 頂点$j$ への長さ2のウォーク(同じ頂点を通っても良い)の個数になります. 三角形も四角形もないとき, $i \neq j$ ならば, $A_{ij}$ と $A^2_{ij}$ はどちらか一方のみが 1 となり, もう一方は 0 となります. 更に, $i=j$ならば, $A_{ii}=d$ となるので, 上に示した方程式が成り立つということになります.

　しかも, この性質を使えば$A$の固有値も求めることが出来ます. 今, $A$の固有値 $\lambda$ に対応する固有ベクトルを $x$ とすると,

$(A^2+A)x = (\lambda^2 + \lambda) x$

となるので, $x$ は $\lambda^2+\lambda$に対応する固有ベクトルになっています.

したがって, $(d-1)I+J$の固有値を求めると, そこから $\lambda$ を求めていくことが出来ます.

- Vertex Transitivity

　日本語で頂点推移性と呼ばれます. 結論から言うと, $d=2,3,7$の現在知られている Moore graph はどれも頂点推移性を満たしているのですが, もし$d=57$の Moore graph が存在するならば, そのグラフは頂点推移性は満たさない, ということが知られています.

　頂点推移性を定義するためにはまずグラフの自己同型群を定義しなければなりません。グラフ$G$の自己同型群$\mathrm{Aut}(G)$とは, $G$の自己同型写像の全体及び写像の合成による群のことです. $f:V(G) \to V(G)$が$G$の自己同型写像であるとは, $f$が全単射かつ

$\{x,y\} \in E(G) \iff \{f(x),f(y)\} \in E(G)$

を満たすことを言います. 直感的に言えば, 自己同型写像とは隣接関係を保存するような頂点上のpermutation (置換) であるということが出来ます.

　グラフ$G$が頂点推移性を満たすというのは, 任意の二頂点$u,v \in V(G)$に対し, $f(u)=v$となるような$f \in \mathrm{Aut}(G)$が存在することを言います.

　例えば $G$ として長さ 5 のサイクル ($V(G)=\{0,1,2,3,4\}$, $E(G)=\{01,12,23,34,40\}$) を考えると, 頂点のラベルを時計周りに一個ずつずらす ($f(v)=(v+1) \mathrm{mod} 5$) ような置換は自己同型写像になっていることが分かります. また, 任意の頂点を二個, 例えば0と3を選んだとすると, $f(v)=(v+3) \mathrm{mod} 5$ ととれば $f$ は $f(0)=3$ となるような自己同型写像になっているので, このサイクルは頂点推移性を満たすことが分かります.

Conclusion

　Moore graph について紹介しました. 特に$d=57$の場合における Moore graph の存在性についての問題は長い間未解決問題になっています. この問題は次のように言い換えることが出来ます.

「頂点数3250 (=$57^2+1$), 次数57 のグラフのうち, 三角形も四角形も含まないようなものが存在するか否か」

こう考えるとパズルのような問題で面白いと思います.

　しかしこのパズルのような問題でも, グラフ理論では長い間 (今なお) 未解決問題として知られているのです. ぜひ, 挑戦してみてはいかがでしょうか.

References

• [1] M. Miller and Jozef Siran : "Moore Graphs and Beyond : A survey of the Degree/Diameter Problem", The Electronic Journal of Combinatorics, 2013

Moore Graph に関するサーベイ論文で, 有向グラフバージョン, 二部グラフバージョンなど, 様々な関連問題のほかにも, キレイ(何らかの群や代数的操作によって生成されるよう)なグラフのつくり方なども載っていて非常に網羅的で良いサーベイ論文だと思います.

• [2] P. Erdos, S. Fajtolowicz and A. J. Hoffman : "Maximum Degree in Graphs of Diameter 2", Networks 10 (1980) 87-90

$n=d^2$かつ直径2 であるようなグラフは, 長さ4の閉路を除いて他に存在しないという定理を証明した論文です. 証明にはグラフの隣接行列の固有値を用いた議論が使われています.