コンウェイの99グラフ問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > コンウェイの99グラフ問題の意味・解説 

コンウェイの99グラフ問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/09/20 07:57 UTC 版)

数学の未解決問題
パラメータ (99,14,1,2) を持つ強正則グラフは存在しますか?
9頂点からなるグラフで、全ての辺がただ一つの三角形の1辺となり、全ての隣接しない2頂点は、ただ一つの四角形の向かい合う頂点となっている。99問題は、同じ性質を持った99個の頂点からなるグラフの存在を問うものである。

コンウェイの99グラフ問題(コンウェイの99グラフもんだい、: Conway's 99-graph problem)はグラフ理論の未解決問題の一つであり、次の性質を持つ99個の頂点からなる無向グラフが存在するかどうかを問う。

任意の隣接する2頂点がちょうど1個の共通の隣接頂点を持ち、任意の隣接しない2頂点がちょうど2個の共通の隣接頂点を持つ。同じことだが、任意の辺がただ一つの三角形の1辺となり、任意の隣接しない2頂点がただ一つの4-閉路の向かい合う2頂点となる。

ジョン・ホートン・コンウェイはこの問題の解決に対して1000ドルの賞金を提示している[1]

性質

もしそのようなグラフが存在すれば、必ず局所線形グラフ英語版(locally linear graph)で、パラメータ (99,14,1,2) の強正則グラフである。1、3、4番目のパラメータはこの問題の条件をコード化したもので、グラフの頂点数が99個であること、どの隣接する2頂点もちょうど1個の共通する隣接頂点を持つこと、どの隣接しない2頂点もちょうど2個の共通する隣接頂点を持つこと、を表している。2番目のパラメータはグラフが14-正則グラフであることを表している[2]

もしこのようなグラフが存在すれば、それには位数11の対称性(グラフの自己同型)は存在せず、したがって任意の頂点が任意の頂点へ写るような対称性は持たないことがわかっている[3]。対称性に関してはこれ以外にも制約が課されねばならないことが知られている[4]

歴史

このようなパラメータを持つグラフが存在する可能性は、既に1969年にノーマン・L・ビッグス英語版によって示唆されており[5]、またその存在が未解決問題であることがコンウェイ以前に他の著者によって記されている[3][6][7][8]。コンウェイ自身はこの問題に 1975年から取り組み始めたが[6]、賞金を提示したのは2014年、DIMACS Conference on Challenges of Identifying Integer Sequences において提示された問題群の一部としてであった。この問題群には thrackle英語版予想、ダンツァー集合英語版での間隙の最小値に関するもの、sylver coinage英語版ゲームで16手後にどちらのプレイヤーが勝つかを問う問題が含まれている[1]

関連するグラフ

より一般に、任意の辺がただ一つの三角形の1辺となり、任意の隣接しない2頂点がただ一つの四角形の向かい合う頂点となるような強正則グラフには、5通りのパラメータの組しか許されない。そのうち存在がわかっているのは2通りの組だけであり、頂点数が9のペイリーグラフ英語版3-3 duoprism英語版 のグラフ)はパラメータが (9,4,1,2) 、バーレカンプ–ヴァン・リント–ザイデルグラフはパラメータが (243,22,1,2) である。99グラフ問題は、5通りのパラメータの組の中で存在がわかっていないもののうち最小のものである[4]

脚注

  1. ^ a b Conway, John H., Five $1,000 Problems (Update 2017), On-Line Encyclopedia of Integer Sequences, https://oeis.org/A248380/a248380.pdf 2019年2月12日閲覧。 . See also オンライン整数列大辞典の数列 A248380.
  2. ^ Zehavi, Sa'ar; David de Olivera, Ivo Fagundes (2017), Not Conway's 99-graph problem, arXiv:1707.08047 
  3. ^ a b Wilbrink, H. A. (August 1984), “On the (99,14,1,2) strongly regular graph”, in de Doelder, P. J.; de Graaf, de, J.; van Lint, J. H., Papers dedicated to J. J. Seidel, EUT Report, 84-WSK-03, Eindhoven University of Technology, pp. 342–355, https://research.tue.nl/files/2449333/256699.pdf 
  4. ^ a b Makhnev, A. A.; Minakova, I. M. (January 2004), “On automorphisms of strongly regular graphs with parameters



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

辞書ショートカット

すべての辞書の索引

「コンウェイの99グラフ問題」の関連用語

コンウェイの99グラフ問題のお隣キーワード
検索ランキング

   

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



コンウェイの99グラフ問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

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

©2025 GRAS Group, Inc.RSS