正方形の頂点と最短距離
正方形の4頂点を結ぶ方法で,使う線分の長さの総和が最も短いものを求めよ
正方形以外の場合にも拡張できますが,正方形の場合の結果が特に有名な問題です。
シュタイナー木問題
三点の場合のシュタイナー木問題
正方形の頂点を最短距離で結ぶ
緑の図が最短であることの証明
シュタイナー木問題
いくつかの点が与えられた時にその点たちをうまく連結させることを考えます。
連結させるときに使う線分の長さが最小になるような方法を求める問題をシュタイナー木問題と言います。
例えば,点たちを「都市」,連結させるときに使う線分を「道路」に見立ててみると,いくつかの都市を結ぶ最短の道路網を構成する問題になります。
例えば,1つの点を発電所,残りの点たちを「家」,連結させるときに使う線分を「電線」に見立てると,使う電線の長さ最小で家々に電気を配給する問題になります。(電柱は何本使っても構いません)
三点の場合のシュタイナー木問題
本題に入る前に,三点 を結ぶシュタイナー木問題考えてみます。
が最大だとしても一般性を失いません。(このとき が三角形 の最大辺となる)
素朴に思いつくのは線分 を引く方法ですが,実は三角形の内部にうまく点 を選んで を結ぶとより小さくできる場合があります。つまり, となる場合があります。(図において青線で結ぶより赤線で結ぶ方がお得!)
をフェルマー点と呼ばれる点( を満たす点)に取れば線分和が最小になることが分かります。→三角形のフェルマー点の3通りの証明
三点のシュタイナー木問題の答え:
最大角が 以下→フェルマー点と三頂点を結んだもの
最大角が 以上→短い2辺を使うもの
以降はフェルマー点の考え方をもとに正方形の問題を扱います。
正方形の頂点を最短距離で結ぶ
愚直な方法:一辺が1の正方形の三辺を選んで結ぶと長さの和は3になります。(上の図)
少し工夫した方法:真ん中に分岐点を1つ作って 型に結ぶと長さの和は になります。(まん中の図)
更に工夫した方法: 型の図の下側の三角形と上側の三角形に注目してそれぞれフェルマー点に分岐点を作ります。結果的に分岐点は2つになります。(下の図)分岐点の周りの角度が全て であることに注意して長さの総和を計算すると となります。
緑の図が最短であることの証明
実際に の解が最短であることは以下の手順で証明できます。
- 分岐点を2つに限れば のものが最短
- 分岐点は2つ以下のものだけを考えれば十分
後者は直感的にはほとんど当たり前ですが厳密に書くとわりと難しいのでここでは前者を解説します。フェルマー点の導出方法を知っていたら比較的簡単に思いつく方法です。
つの分岐点 がそれぞれ と につながっているとしても一般性を失わない。
正方形 の上側に ,下側に を と が正三角形になるようにとる。
また, と が正三角形になるように を取る。
三角形のフェルマー点のときと同様な議論により
線分和
これは と を結ぶ折れ線の長さなので, を調節して直線になるときが最短となる。実際 の周りの角度が全て のとき直線になる。
線分の長さの和は折れ線の長さに変換するしかありません,正方形のシュタイナー木はあまりにも有名なのでぜひ覚えておきましょう