次数と直径が与えられたとき頂点数の上限
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:43 UTC 版)
「ムーアグラフ」の記事における「次数と直径が与えられたとき頂点数の上限」の解説
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 個の頂点が存在する。よって各階層の頂点数を足し上げると次式を得る。 1 + d ∑ i = 0 k − 1 ( d − 1 ) i . {\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i}.} ムーアグラフはホフマンとシングルトンによってこの上限に頂点数が一致するグラフとして定義された。ムーアグラフは次数d、直径kのグラフのうち頂点数が最大のものである。 その後、Singleton (1968) によって、ムーアグラフは直径k、内周2k+1を満たすグラフと同値であることが示された。直径と内周の条件によってグラフは正則となる。
※この「次数と直径が与えられたとき頂点数の上限」の解説は、「ムーアグラフ」の解説の一部です。
「次数と直径が与えられたとき頂点数の上限」を含む「ムーアグラフ」の記事については、「ムーアグラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「次数と直径が与えられたとき頂点数の上限」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 次数と直径が与えられたとき頂点数の上限のページへのリンク
