正方形の頂点と最短距離
正方形の頂点と最短距離

正方形の頂点と最短距離

正方形の４つの頂点を結ぶ最短の方法を解説します。有名なシュタイナー木問題。フェルマー点の考え方を応用します。

素朴に思いつくのは線分 A B , A C AB, AC A B , A C を引く方法ですが，実は三角形の内部にうまく点 P P P を選んで P A , P B , P C PA,PB,PC P A , PB , PC を結ぶとより短くできる場合があります。つまり， A B + A C > P A + P B + P C AB+AC > PA+PB+PC A B + A C > P A + PB + PC となる場合があります。（図において青線で結ぶより赤線で結ぶ方がお得！）

∠ A \angle A ∠ A が 12 0 ∘ 120^ 12 0 ∘ 未満の場合， P P P をフェルマー点（ ∠ A P B = ∠ B P C = ∠ C P A = 12 0 ∘ \angle APB=\angle BPC=\angle CPA=120^ ∠ A PB = ∠ BPC = ∠ CP A = 12 0 ∘ を満たす点）に取れば線分和が最小になることが知られています。→三角形のフェルマー点の3通りの証明

3点のシュタイナー木問題の答え
  • 最大角が 12 0 ∘ 120^ 12 0 ∘ 以下なら，フェルマー点と3頂点を結んだもの
  • 最大角が 12 0 ∘ 120^ 12 0 ∘ 以上なら，短い2辺を使うもの

少し工夫した方法：真ん中に分岐点を1つ作って X X X 型に結ぶと長さの和は 2 2 ≒ 2.8 2\sqrt\fallingdotseq 2.8 2 2

さらに工夫した方法： X X X 型の図の下側の三角形と上側の三角形に注目してそれぞれフェルマー点に分岐点を作ります。 結果的に分岐点は2つになります。分岐点の周りの角度が全て 12 0 ∘ 120^ 12 0 ∘ であることに注意して長さの総和を計算すると 1 + 3 ≒ 2.7 1+\sqrt\fallingdotseq 2.7 1 + 3

実際に 1 + 3 1+\sqrt 1 + 3

  1. 分岐点は2つ以下のものだけを考えれば十分
  2. 分岐点を2つに限れば 1 + 3 1+\sqrt 1 + 3 ​ のものが最短
分岐点が2つ以下であることの証明

最適解における，4つの頂点と n n n 個の分岐点をつないだグラフを考える。

木において辺の数は頂点の数 − 1 -1 − 1 なので辺の数は ( n + 4 ) − 1 (n+4)-1 ( n + 4 ) − 1 である。

また，各分岐点には 3 3 3 本以上の辺が接続されている（もし2本以下なら余分な頂点なので除去できる）。

よって辺の数は ( 3 × n + 4 ) ÷ 2 (3\times n+4)\div 2 ( 3 × n + 4 ) ÷ 2 以上である。

以上より n + 3 ≧ ( 3 n + 4 ) ÷ 2 n+3\geqq (3n+4)\div 2 n + 3 ≧ ( 3 n + 4 ) ÷ 2

n 2 ≦ 1 \dfrac\leqq 1 2 n ​ ≦ 1

つまり n ≦ 2 n\leqq 2 n ≦ 2

分岐点が2つのとき緑の線が最短であることの証明

2 2 2 つの分岐点 S , T S,T S , T がそれぞれ A , B A,B A , B と C , D C,D C , D につながっているとしても一般性を失わない。

正方形 A B C D ABCD A BC D の上側に P P P ，下側に Q Q Q を A B P ABP A BP と C D Q CDQ C D Q が正三角形になるようにとる。

また， A S U ASU A S U と D T V DTV D T V が正三角形になるように U , V U,V U , V を取る。

線分和 = A S + B S + S T + C T + D T = S U + P U + S T + Q V + T V =AS+BS+ST+CT+DT\\ =SU+PU+ST+QV+TV = A S + BS + ST + CT + D T = S U + P U + ST + Q V + T V

これは P P P と Q Q Q を結ぶ折れ線の長さなので， S , T S,T S , T を調節して直線になるときが最短となる。実際 S , T S,T S , T の周りの角度が全て 12 0 ∘ 120^ 12 0 ∘ のとき直線になる。

東京大学大学院情報理工学系研究科修了／2014年にWebサイト『高校数学の美しい物語』を立ち上げ／著書累計 50,000部突破／「わかりやすいこと」と「ごまかさないこと」の両立を意識している。 →著者情報・書籍一覧を見る

  • シュタイナー木問題
  • 三点の場合のシュタイナー木問題
  • 正方形の頂点を最短距離で結ぶ
  • 緑の図が最短であることの証明