東京工科大学 メディア学部 ブログ

“美術館”という馴染み深い単語と“定理”という少々堅苦しい単語の組合せは，いささか奇異に感じられるかもしれません。しかし、これは数学の一分野である離散幾何学の立派な定理で、英語でも“Art Gallery Theorem”として知られています。以下に、その概要を記します。

1973年にクリ―（V. Klee）は、「n個の壁で仕切られ、内部に障害物がない美術館を、何人の警備員で監視できるか？」という問題を提起しました。これは美術館問題と呼ばれています（まだ問題の段階です）。なお、前提として、各警備員には定位置があり、そこから動くことがないものの360°見渡せるということにします。固定式の防犯カメラと思えばいいでしょう。さて、下の図を見てみましょう。上から美術館を眺めているものとして考えてください。(a)、(b)ともに9個の壁で囲まれています。図形として捉えれば、凹凸ありの単純9角形です。美術館が (a)のような形状であれば、★のあたりに警備員を一人配置することで美術館全体を監視でき、窃盗やいたずらを防ぐことができます。一方、(b)のような形状であれば、図の★のあたりに一人ずつ警備員を配置することで美術館全体が監視できます。警備員の配置は他にも考えられますが、それでも(b)の場合には最低3人の警備員が必要であることはわかると思います。

〔図〕 9個の壁で囲まれた美術館に必要な警備員の人数

この(b)の例は、山が3つあるような形状ですが、同様に山が4つになれば（つまり12角形のときには）警備員が4人、山が5つになれば（つまり15角形のときには）警備員が5人必要であることが想像つきますね。特殊な形状ではありますが、この素朴な観察が示唆することは、3k角形（k：自然数）の美術館にはk人の警備員が必要であることもありうるということです。1975年にクバタル（V.Chvatal）は、「任意のn角形（n：自然数）の美術館は、高々⎿n/3⏌人の警備員で監視が可能である」と主張し、その証明を与えました。これが“美術館定理”です。nを3の倍数に限定していないことに注意しましょう。⎿n/3⏌は、n/3を超えない最大の整数を意味します。　

さて、美術館の形状によっては⎿n/3⏌人の警備員が必要であるということが先の観察で明らかになりました。しかし、美術館定理はそれよりも踏み込んだ内容となっており、⎿n/3⏌人で十分であるということも主張しています。ここでは、1978年にフィスク（S.Fisk）が与えた証明の概観からそのことを理解してみましょう。キーワードは、三角形分割と頂点彩色です。下の図を見てください。左上の26角形が美術館の形状だとしましょう。これを右上にあるように、頂点を内部でも結んで全体を三角形に分割します。あとから加えた点線を含めると、この26角形が24個の三角形に分割されたことがわかります。一般に、n角形はn-2個の三角形に分割することができます（分割の仕方は一意ではありません）。そして、この三角形の各頂点を赤・緑・青の3色で彩色します。ただし、三角形を構成する頂点同士は別の色になるように塗ります。その一例が下側の図です。どの三角形においても3色が使われますので、各色の頂点の数は高々1個しか違いません。実際、この例の場合も、赤の頂点が8個，緑と青の頂点がそれぞれ9個となっています。

〔図〕 多角形の三角形分割と3色による頂点の彩色

ところで、三角形は凹形状にはならない唯一の多角形です。したがって、例えば赤の箇所に警備員を配置すれば、美術館全体の監視ができることになります。赤い頂点は8個でしたが、⎿26/3⏌= 8ですね。この美術館は実際にはその半数の警備員で全体を監視できますが、任意の26角形の美術館ということで考えれば、最悪の場合であっても8人の警備員で監視計画が立てられるということです。この美術館問題は、その後に様々なバリエーションのものが登場しました。また関連して、要塞問題や刑務所問題などもあります。関心のある方はいろいろと調べてみてください。

以上

（文責： メディア学部 松永）