|
グラフ理論においてムーアグラフとは、次数''d''、直径''k''の正則グラフで、頂点数が以下の上限に一致するものである。 : 直径''k''、内周2''k''+1のグラフで頂点数が最小のもの、とムーアグラフを定義することもできる。また内周が2''k''+1のときに長さ''g''のサイクルをちょうど個含むようなグラフと定義することもできる。ここでnは頂点数、mは辺の数である。実際、内周に一致するサイクルを上記の条件のように含むグラフが頂点数最小のグラフとなる (Azarija & Klavžar 2014)。 ムーアグラフという名前はエドワード・F・ムーアにちなんで1960年にホフマンとシングルトンによって名付けられた。 次数と直径が与えられたとき最大の頂点数を持つものがムーアグラフであるが、これは次数と内周が与えられたときに最小の頂点数をもつグラフでもある。すなわちムーアグラフはケージ(Erdős, Rényi & Sós 1966)である。通常の定義ではムーアグラフの内周は必ず奇数になるが、ムーアグラフの頂点数、次数、直径の満たす関係式から出発して内周を偶数を許すように拡張することができる。そのような拡張されたムーアグラフはまたケージとなる。 == 次数と直径が与えられたとき頂点数の上限 == ''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)''i'' 個の頂点が存在する。よって各階層の頂点数を足し上げると次式を得る。 : ムーアグラフはホフマンとシングルトンによってこの上限に頂点数が一致するグラフとして定義された。ムーアグラフは次数''d''、直径''k''のグラフのうち頂点数が最大のものである。 その後、Singleton (1968) によって、ムーアグラフは直径k、内周2k+1を満たすグラフと同値であることが示された。直径と内周の条件によってグラフは正則となる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ムーアグラフ」の詳細全文を読む スポンサード リンク
|