正方形の頂点と最短距離

シュタイナー木問題

いくつかの点が与えられた時に，その点たちをうまく連結させることを考えます。

連結させるときに使う線分の長さの和が最小になるような方法を求める問題を，シュタイナー木問題と言います。

• 例えば，点たちを「都市」，連結させるときに使う線分を「道路」と考えると，いくつかの都市を結ぶ最短の道路網を構成する問題になります。
• 例えば，1つの点を発電所，残りの点たちを「家」，連結させるときに使う線分を「電線」に見立てると，使う電線の長さ最小で家々に電気を配給する問題になります（電柱は何本使っても構いません）。

三点の場合のシュタイナー木問題

本題に入る前に，3点 $A,B,C$ を結ぶシュタイナー木問題考えます。

$\angle A$ が最大だとしても一般性を失いません（このとき $BC$ が三角形 $ABC$ の最大辺となる）。

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

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

以下ではフェルマー点の結果をもとに正方形の問題を考えます。

正方形の頂点を最短距離で結ぶ

次は，正方形の4頂点を結ぶ場合を考えます。 愚直な方法：一辺が1の正方形の三辺を選んで結ぶと長さの和は3になります。

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

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

緑の図が最短であることの証明

実際に $1+\sqrt{3}$ の解が最短であることを，以下の手順で証明します。

1. 分岐点は2つ以下のものだけを考えれば十分
2. 分岐点を2つに限れば $1+\sqrt{3}$ のものが最短

1はグラフ理論の言葉を使います。→グラフ理論の基礎

2はフェルマー点の導出方法を知っていれば比較的簡単に思いつく方法です。