gm learning

完全グラフの穴

　まず，実験！頂点数を 100 にして決定ボタンをクリックしましょう．すると，少々時間が掛かりますが，真っ黒な円になってしまいますね．

　続いて，頂点数を 99 にして決定ボタンをクリックしましょう．今度も真っ黒ですが，さっきと何かが違います．さて，何が違うのでしょうか？

　もちろん，初めのは K₁₀₀ で，次のは K₉₉ ですね．違いがわからなければ，もう一度， K₁₀₀ と K₉₉ を描き直して比較してください．

　ヒントはこのページの題名にあります．

　答えは，K₁₀₀ が真っ黒になるのに対して， K₉₉ は真中に白い穴が開くということです．嘘だと思うのなら，もう１度実験して確かめてください． 98 と 97 で試してもいいですよ．

　では，どうしてそんな穴があくのでしょうか？

　答えは簡単です． 100 は偶数だけど，99 は奇数だから穴が開くのです．

　といわれても，ピンと来ない人は， K₁₀ と K₉ を描いてみてくっださい．基本的には 100 と 99 の場合と同じ現象が起こります．

　要するに，100 も 10 も偶数なので，正多角形状に頂点を配置すると，どの頂点に対しても，それとちょうど真反対に位置する頂点があるのです．そういう頂点を結ぶ辺は正多角形の中心を通るので，真中の点が絶対に黒くなるのです．

　一方，99 も 9 も奇数なので，真反対の頂点というのがありません．だから，中心を貫くような辺もないことになります．それで，中心の点は白いままで，穴のようになるわけです．

　言われてみれば当たり前のことですが，頂点数が少ない完全グラフを漫然と眺めていても，こういう現象に気づかないかもしれませんね．コンピュータの力を借りて， 99 個も頂点がある完全グラフを描いてみたからこそ， “完全グラフの穴”の存在に気づいたのだとは思いませんか？

　ところで，その穴の大きさはどのくらいになるのでしょうか？中心点から辺までの距離の最小値がその穴の半径になりますね．その答えはみなさんにお任せします．