Moore graphとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Moore graphの意味・解説 

ムーアグラフ

(Moore graph から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/02/09 13:53 UTC 版)

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

次数3,直径2のムーアグラフ(ピーターセングラフ)。幅優先探索木においてi番目の階層の頂点数はd(d-1)iになる。

Gを次数d、直径kの任意のグラフとする。頂点vをルートとして幅優先探索木を構成する。この木は0階層に1つの頂点(v自身)、1階層に高々d個の頂点がある。次の階層には高々d(d-1)個の頂点がある。というのは、2階層において、1階層目の頂点は0階層のvと隣接しているため2階層目と高々d-1の頂点と隣接する。同様の議論によって一般的に、i階層目(1 ≤ ik)には高々d(d-1)i 個の頂点が存在する。よって各階層の頂点数を足し上げると次式を得る。

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

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

ケージとしてのムーアグラフ

ムーアグラフは最大次数と直径が与えられたときに最大頂点数のグラフとして定式化されるが、類似の議論によって最小次数と内周が与えられたときに最小頂点数のグラフとしても定式化されうる(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 ≤ ik)には少なくともd(d-1)i 個の頂点が存在する。よって各階層の頂点を足し上げれば頂点数の下限として次式を得る。

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

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

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

具体例

ホフマン-シングルトンの定理によれば、内周が5のムーアグラフの次数は2, 3, 7あるいは57のいずれかである。

  • n > 2 の完全グラフ  (直径1, 内周3, 次数n-1, 頂点数n)
  • 奇数頂点のサイクル . (直径n, 内周2n+1, 次数2, 頂点数2n+1)
  • 直径2、内周5、次数57、頂点数3250のグラフが存在しうる。しかしいまだ構成されておらず、否定的な証明もされていない。

他の知られているムーアグラフと異なり、次数57のムーアグラフは頂点推移グラフとはならないことがHigmanによって証明されている。またMačajとŠiráňによれば、そのようなムーアグラフの自己同型群位数は高々375である。

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

参考文献

関連項目

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Moore graph」の関連用語

Moore graphのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Moore graphのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのムーアグラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS