McGregorグラフ

TAOCPに「10次のMcGregorグラフ(McGregor graph of order 10)」という図があった. これには「Scientific Americanの1975年4月号で, Martin Gardnerがこの図の塗り分けには5色が必要と紹介し世間を驚かせた」と説明がある.



その号のMathematical Gamesコラムに はe^π√163は整数である(これについては高橋秀俊先生が1975年の高橋コンファレンスで話された. どこかにそれが書かれているかと探したが見当たらない.)とか怪しい話もあり, 結局は四月馬鹿の話題であったのだ.

私もその号のコラムを読み, なーんだと思ったひとりである. それから既に40年経った.

TAOCPには演習問題の解を見る前に自分で試みよとあったので, とりあえずバックトラックしながら解を探すプログラムをSchemeで書き, 解をひとつ見つけた. 結構時間が掛ったが, プログラムを走らせてから長めのミーティングに出ていて, 戻ってきたら解が出力されていた.

ちゃんと4色で塗れた. 探索プログラムより区画どうしの接続データを作るのが面倒であった. またこの図を描くPostScriptのプログラムも予想外に時間がかかった.

接続データはこういう形である.

(0 1 10 11 100 101 102 103 104 105 109)
(1 0 2 11 12 109)
(2 1 3 12 13 109)
(3 2 4 13 14 109)
(4 3 5 14 15 109)
(5 4 6 15 16 109)
... 途中100行省略
(106 10 95 96 105 107)
(107 10 96 97 106 108)
(108 10 97 98 107 109)
(109 0 1 2 3 4 5 6 7 8 9 10 9 19 98 108)))

例えば最上行は「0の区画と隣合うのは1, 10, 11, a0, a1, a2, a3, a4, a5, a9である」という意味. aは10 と書いてある. もちろんaの隣のリストにあるbについて, bの隣のリストにaがあることはチェックした.

得られた解で塗り分けたのが下の図である. かなり美しい.



110の区画でそれぞれの色が使われた数はであった. と書いた理由はTAOCPにひとつの色は7区画でしか使わない解があるという記述があったからだ. そういう解を探すのはまた大変そうだ.

TAOCPではこれをdancing linksで解くつもりらしい. dancing linksのプログラムは以前に書いたこともあるので, そのうちdancing linksでもプログラムを書いてみたい.

ところで各区画に付いている番号には意味があるのかな. 上の図は10次だが, 9次とか描くには番号が手引きになるのだろうか.