趣味の数学とプログラム。楽しい数学の世界へようこそ!

美術館定理

美術館に監視カメラをつけます。美術館は\(n\)角形で穴がなく(中庭などはない)、監視カメラは360度監視できるとします。

監視カメラの台数をなるべく少なくしたい場合、何台必要でどこに設置するといいでしょうか。

凸角形の場合は、1台設置すればいいですね。

こんなギザギザの形の場合、

廊下の部分に1台だけ設置すると、トゲの先の方は死角になります。最低何台の監視カメラが必要でしょうか。

美術館定理
穴がない\(n\)角形の美術館は、高々\(\lfloor \large{\frac{3}{n}} \rfloor\)台の監視カメラで監視が可能である
※ガウス記号\(\lfloor x \rfloor\)は、\(x\)を超えない整数を表します。

\(n\)角形は、\(n-2\)個の三角形に分割することができます。
各三角形の頂点を3色に塗り分けますが、同じ三角形の頂点同士は別の色に塗るようにします。(3色に塗り分け可能については、最後に証明します)

どの三角形でも3色使われるので、各色の頂点の数は同じか1個違いで、一番少ない頂点の数は、\(\lfloor \large{\frac{3}{n}} \rfloor\)個です。上の例では、赤:3個、緑:3個、青:2個。

一番少ない色の箇所に、監視カメラを設置すると

その頂点が属する三角形の範囲は必ず監視できるので、\(\lfloor \large{\frac{3}{n}} \rfloor\)個(上の例では2個)の監視カメラで美術館全体を監視できます。

3色に塗り分け可能について

 

「穴のない \(n\)角形を三角形分割したグラフの頂点を、3色に塗り分けられる」ことを、帰納法で証明します。(グラフ理論でいうグラフは、点の集合と辺の集合で表されます。例:路線図、電気図など)

 

三角形が1個の場合は、明らかに塗り分け可能。

 

\(n\)個の三角形からなるグラフの頂点が、3色に塗り分け可能だと仮定する。

 

\(n+1\)個の三角形からなるグラフについて、1つの三角形としか隣接しない三角形が存在する(存在しない場合には、内側に頂点か穴ができるので、仮定と矛盾)

 

この三角形を除いた\(n\)個の三角形からなるグラフは、仮定から頂点を3色に塗り分け可能。\(n+1\)個目の三角形を加えたときに、追加する頂点を共有する2つの頂点以外の色で塗ると、\(n+1\)個の三角形からなるグラフの頂点を3色に塗り分けたことになる。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です