ケージとしてのムーアグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:43 UTC 版)
「ムーアグラフ」の記事における「ケージとしてのムーアグラフ」の解説
ムーアグラフは最大次数と直径が与えられたときに最大頂点数のグラフとして定式化されるが、類似の議論によって最小次数と内周が与えられたときに最小頂点数のグラフとしても定式化されうる(Erdős, Rényi & Sós 1966).。Gを最小次数dと内周2k+1をもつ任意のグラフとしよう。任意の頂点vから始めて幅優先探索木を構成する。0階層にはちょうど1つのv自身が存在する。また1階層には少なくともd個の頂点が存在する。 2階層（k > 1）には, 少なくともd(d-1)個の頂点が存在する。なぜなら1階層の異なる2頂点は内周の制約から2階層に共通の近傍を持たないからだ。同様にして一般的に任意の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}.} ムーアグラフのこの下限に頂点数が一致する。幅優先探索木においてある階層の異なる2頂点が下の階層で共通の近傍を持つとすると、内周の制約を破る短いサイクルが発生するため、任意のムーアグラフは内周は2k+1となる。よってムーアグラフは次数d、内周2k+1のグラフのうち頂点数が最小のもの、すなわちケージとなる。 偶数の内周2kについては、任意の一辺から幅優先探索木を構成することで同様の式を得る。最小次数がdでこの内周を満たすグラフの頂点数の下限は次式で与えられる。 2 ∑ i = 0 k − 1 ( d − 1 ) i = 1 + ( d − 1 ) k − 1 + d ∑ i = 0 k − 2 ( d − 1 ) i . {\displaystyle 2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0}^{k-2}(d-1)^{i}.} ムーアグラフの定義を拡張して偶数内周を許した場合にも、そのようなグラフはケージとなる。
※この「ケージとしてのムーアグラフ」の解説は、「ムーアグラフ」の解説の一部です。
「ケージとしてのムーアグラフ」を含む「ムーアグラフ」の記事については、「ムーアグラフ」の概要を参照ください。
- ケージとしてのムーアグラフのページへのリンク
