ムーアグラフのソースを表示

[[グラフ理論]]において'''ムーアグラフ'''とは、[[次数 (グラフ理論)|次数]]''d''、[[直径]]''k''の[[正則グラフ]]で、頂点数が以下の上限に一致するものである。

:<math>1+d\sum_{i=0}^{k-1}(d-1)^i .</math>

[[直径]]''k''、[[内周 (グラフ理論)|内周]]2''k''+1のグラフで頂点数が最小のもの、とムーアグラフを定義することもできる。また内周が2''k''+1のときに長さ''g''のサイクルをちょうど<math> \frac{n}{g}(m-n+1) </math>個含むようなグラフと定義することもできる。ここでnは頂点数、mは辺の数である。実際、内周に一致するサイクルを上記の条件のように含むグラフが頂点数最小のグラフとなる ([[#CITEREFAzarijaKlav.C5.BEar2014|Azarija &#x26; Klavžar 2014]])。

ムーアグラフという名前は{{仮リンク|エドワード・F・ムーア|en|Edward F. Moore}}にちなんで1960年にホフマンとシングルトンによって名付けられた。

次数と直径が与えられたとき最大の頂点数を持つものがムーアグラフであるが、これは次数と内周が与えられたときに最小の頂点数をもつグラフでもある。すなわちムーアグラフは[[ケージ (グラフ理論)|ケージ]]([[#CITEREFErd.C5.91sR.C3.A9nyiS.C3.B3s1966|Erdős, Rényi & Sós 1966]])である。通常の定義ではムーアグラフの内周は必ず奇数になるが、ムーアグラフの頂点数、次数、直径の満たす関係式から出発して内周を偶数を許すように拡張することができる。そのような拡張されたムーアグラフはまたケージとなる。

== 次数と直径が与えられたとき頂点数の上限 ==
[[ファイル:Petersen-as-Moore.svg|thumb|次数3，直径2のムーアグラフ（[[ピーターセングラフ]]）。[[幅優先探索]]木において''i''番目の階層の頂点数は''d''(''d''-1)<sup>''i''</sup>になる。]]
''G''を次数''d''、直径''k''の任意のグラフとする。頂点''v''をルートとして[[幅優先探索]]木を構成する。この木は0階層に1つの頂点（''v''自身）、1階層に高々''d''個の頂点がある。次の階層には高々''d''(''d''-1)個の頂点がある。というのは、2階層において、1階層目の頂点は0階層の''v''と隣接しているため2階層目と高々''d''-1の頂点と隣接する。同様の議論によって一般的に、''i''階層目（1 ≤ ''i'' ≤ ''k''）には高々''d''(''d''-1)<sup>''i''</sup> 個の頂点が存在する。よって各階層の頂点数を足し上げると次式を得る。

:<math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>

ムーアグラフはホフマンとシングルトンによってこの上限に頂点数が一致するグラフとして定義された。ムーアグラフは次数''d''、直径''k''のグラフのうち頂点数が最大のものである。

その後、[[#CITEREFSingleton1968|Singleton (1968]]) によって、ムーアグラフは直径k、内周2k+1を満たすグラフと同値であることが示された。直径と内周の条件によってグラフは[[正則グラフ|正則]]となる。

== ケージとしてのムーアグラフ ==
ムーアグラフは最大次数と直径が与えられたときに最大頂点数のグラフとして定式化されるが、類似の議論によって最小次数と内周が与えられたときに最小頂点数のグラフとしても定式化されうる([[#CITEREFErd.C5.91sR.C3.A9nyiS.C3.B3s1966|Erdős, Rényi &#x26; Sós 1966]]).。''G''を最小次数''d''と内周2''k''+1をもつ任意のグラフとしよう。任意の頂点''v''から始めて幅優先探索木を構成する。0階層にはちょうど1つの''v''自身が存在する。また1階層には少なくともd個の頂点が存在する。 2階層（''k'' > 1）には, 少なくとも''d''(''d''-1)個の頂点が存在する。なぜなら1階層の異なる2頂点は内周の制約から2階層に共通の近傍を持たないからだ。同様にして一般的に任意の''i''階層（1 ≤ ''i'' ≤ ''k''）には少なくとも''d''(''d''-1)<sup>''i''</sup> 個の頂点が存在する。よって各階層の頂点を足し上げれば頂点数の下限として次式を得る。

:<math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>

ムーアグラフのこの下限に頂点数が一致する。幅優先探索木においてある階層の異なる2頂点が下の階層で共通の近傍を持つとすると、内周の制約を破る短いサイクルが発生するため、任意のムーアグラフは内周は2''k''+1となる。よってムーアグラフは次数''d''、内周2''k''+1のグラフのうち頂点数が最小のもの、すなわち[[ケージ (グラフ理論)|ケージ]]となる。

偶数の内周2''k''については、任意の一辺から幅優先探索木を構成することで同様の式を得る。最小次数が''d''でこの内周を満たすグラフの頂点数の下限は次式で与えられる。

:<math>2\sum_{i=0}^{k-1}(d-1)^i=1+(d-1)^{k-1}+d\sum_{i=0}^{k-2}(d-1)^i.</math>

ムーアグラフの定義を拡張して偶数内周を許した場合にも、そのようなグラフはケージとなる。

== 具体例 ==
ホフマン-シングルトンの定理によれば、内周が5のムーアグラフの次数は2, 3, 7あるいは57のいずれかである。
* n > 2 の[[完全グラフ]]<math> K_n </math>  (直径1, 内周3, 次数n-1, 頂点数n)

* 奇数頂点のサイクル <math> C_{2n+1} </math>. (直径n, 内周2n+1, 次数2, 頂点数2n+1)

* [[ピーターセングラフ]](直径2, 内周5, 次数3, 頂点数10)

* [[ホフマンシングルトングラフ]]（直径2, 内周5, 次数7, 頂点数50)

* 直径2、内周5、次数57、頂点数3250のグラフが存在しうる。しかしいまだ構成されておらず、否定的な証明もされていない。
他の知られているムーアグラフと異なり、次数57のムーアグラフは[[頂点推移グラフ]]とはならないことがHigmanによって証明されている。またMačajとŠiráňによれば、そのようなムーアグラフの[[自己同型群]]の[[位数]]は高々375である。

ムーアグラフの定義を内周が偶数も許容するように一般化すると、偶数内周のムーアグラフは[[一般化多角形]]の縮退した[[インシデントグラフ]]に相当する。例えば、内周4の偶数サイクル <math> C_{2n} </math>, [[完全二部グラフ]] <math> K_{n,n} </math> や 次数3, 内周6の[[ヒーウッドグラフ]]、次数3, 内周8の[[:en:Tutte–Coxeter graph|Tutte–Coxeter graph]]がある。より一般に前出の例以外のムーアグラフの内周は5, 6, 8あるいは12でなくてはならない{{harv|Bannai|Ito|1973}}{{harv|Damerell|1973}} 。内周8のケージは一般''n''角形の存在定理であるFeit-Higmanの定理より従う。

== 参考文献 ==
* <span class="citation" id="CITEREFAzarijaKlav.C5.BEar2014">{{Cite journal|和書|title=Moore graphs and cycles are extremal graphs for convex cycles |url=https://doi.org/10.1002/jgt.21837 |author=Azarija, Jernej and Klavžar, Sandi |journal=Journal of Graph Theory |volume=80 |issue=1 |pages=34-42 |year=2015 |publisher=Wiley Online Library |doi=10.1002/jgt.21837}}</span>
* <span class="citation">[[ベラ・バラバシ|Bollobás, Béla]] (1998), "Chap.VIII.3", ''Modern graph theory'', [[Graduate Texts in Mathematics]] '''184''', [[シュプリンガー・サイエンス・アンド・ビジネス・メディア|Springer-Verlag]]</span>.
* <span class="citation" id="CITEREFBannaiIto1973">{{Cite journal|author=Bannai, Eiichi and Ito, Tatsuro |journal=東京大学理学部紀要. 第1類A, 数学 |year=1973 |month=Aug |volume=20 |issue=2 |pages=191-208 |title=On finite Moore graphs |url=https://doi.org/10.15083/00039786}} {{MR|0323615}}</span>
* <span class="citation" id="CITEREFDamerell1973">Damerell, R. M. (1973), "On Moore graphs", ''Mathematical Proceedings of the Cambridge Philosophical Society'' '''74''': 227–236, {{doi|10.1017/S0305004100048015}}, {{MR|0318004}}</span>
* <span class="citation" id="CITEREFErd.C5.91sR.C3.A9nyiS.C3.B3s1966">[[ポール・エルデシュ|Erdős, Paul]]; [[:en:Alfréd Rényi|Rényi, Alfréd]]; [[:en:Vera T. Sós|Sós, Vera T.]] (1966), [http://www.math-inst.hu/~p_erdos/1966-06.pdf "On a problem of graph theory"], ''Studia Sci. Math. '' ''Hungar.'' '''1''': 215–235</span>.
* <span class="citation">[[:en:Alan J. Hoffman|Hoffman, Alan J.]]; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", ''IBM Journal of Research and Development'' '''5''' (4): 497–504, {{doi|10.1147/rd.45.0497}}, {{MR|0140437}}</span>
* <span class="citation">{{Cite journal|title=Search for properties of the missing Moore graph |author1=Martin Mačaj |author2=Jozef Širáň |journal=Linear Algebra and its Applications |volume=432 |issue=9 |pages=2381-2398 |year=2010 |publisher=Elsevier |url=https://doi.org/10.1016/j.laa.2009.07.018 |doi=10.1016/j.laa.2009.07.018}}</span>
* <span class="citation" id="CITEREFSingleton1968">Singleton, Robert R. (1968), "There is no irregular Moore graph", ''[[:en:American Mathematical Monthly|American Mathematical Monthly]]'' '''75''' (1): 42–43, {{doi|10.2307/2315106}}, {{MR|0225679}}</span>

== 関連項目 ==
* [[次数直径問題]]
** [[:en:Degree diameter problem|Degree diameter problem（英語）]]
* [[:en:Table of the largest known graphs of a given diameter and maximal degree| Table of the largest known graphs of a given diameter and maximal degree（英語）]]

== 外部リンク ==
* [[:en:Andries Brouwer|Brouwer]] and Haemers: [http://www.cwi.nl/~aeb/math/ipm.pdf Spectra of graphs]{{リンク切れ|date=2017年9月 |bot=InternetArchiveBot }}
* <span class="citation mathworld">[[:en:Eric W. Weisstein|Weisstein, Eric W]]., [http://mathworld.wolfram.com/MooreGraph.html "Moore Graph"], ''[[MathWorld]]''.</span>
* <span class="citation mathworld">Weisstein, Eric W., [http://mathworld.wolfram.com/Hoffman-SingletonTheorem.html "Hoffman-Singleton Theorem"], ''MathWorld''.</span>

{{DEFAULTSORT:むうあくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]