COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

最短ネットワーク問題

 分岐点を新たに設けてもよいという条件の下で, 与えられたいくつかの点をもれなく結ぶ最短経路を求める問題は, 最短ネットワーク問題(the shortest path problem)と呼ばれ, インフラの建設計画を立てたり, 電気回路の設計をしたりする際に現れる素朴で重要な問題である.

$3$ 点の場合

定理≪$3$ 点の最短ネットワーク問題≫

 $3$ 点 $\mathrm A,$ $\mathrm B,$ $\mathrm C$ を結ぶ最短経路は,
(i)
$3$ 点が一直線上にあるとき, 最も離れた $2$ 点を結ぶ線分である.
(ii)
$3$ 点がどの内角も $120^\circ$ 未満であるような三角形をなすとき, $\angle\mathrm{AFB} = \angle\mathrm{BFC} = \angle\mathrm{CFA}$ なる点 $\mathrm F$ を交差点として $3$ 点を結ぶ三叉路である. 点 $\mathrm F$ は, $\triangle\mathrm{ABC}$ と $1$ 辺を共有する正三角形 $\mathrm{ABC}',$ $\mathrm{BCA}',$ $\mathrm{CAB}'$ を $\triangle\mathrm{ABC}$ の外側に描くとき, $3$ 直線 $\mathrm{AA}',$ $\mathrm{BB}',$ $\mathrm{CC}'$ の交点として定まる.
(iii)
$3$ 点がある内角が $120^\circ$ 以上であるような三角形をなすとき, その頂点と他の $2$ 頂点を結ぶ折れ線である.

証明

(i)
明らか.
(ii)
前半: 三角不等式 $\mathrm P_1\mathrm P_2+\mathrm P_2\mathrm P_3 \geqq \mathrm P_1\mathrm P_3$ を使うと, これは三角形の各頂点までの距離の和が最小になる点を求める問題に帰着できる(詳細は割愛する). その最小値を求める問題については, こちらを参照.
後半: $2$ 直線 $\mathrm{AA}',$ $\mathrm{BB}'$ の交点を $\mathrm F$ とおき, $\angle\mathrm{AFB} = \angle\mathrm{BFC} = \angle\mathrm{CFA}$ を示す. $\mathrm{CA} = \mathrm{CB}',$ $\mathrm{CB} = \mathrm{CA}',$ $\angle\mathrm{ACA'} = \angle\mathrm{BCB'} = \angle\mathrm{ACB}+60^\circ$ から $\triangle\mathrm{ACA}' \equiv \triangle\mathrm B'\mathrm{CB}$ であるので, $\angle\mathrm{CAF} = \angle\mathrm{CB}'\mathrm F,$ $\angle\mathrm{CBF} = \angle\mathrm{CA}'\mathrm F$ となる. よって, 円周角の定理の逆により, $4$ 点 $\mathrm C,$ $\mathrm F,$ $\mathrm A,$ $\mathrm B'$ と $4$ 点 $\mathrm C,$ $\mathrm F,$ $\mathrm B,$ $\mathrm A'$ はそれぞれ同一円周上にあるので, $\angle\mathrm{BFC} = \angle\mathrm{CFA} = 180^\circ -60^\circ = 120^\circ$ となり, $\angle\mathrm{AFB} = 360^\circ -\angle\mathrm{BFC}-\angle\mathrm{CFA} = 120^\circ$ となる.
(iii)
平面上に点 $\mathrm P$ をとる. $\mathrm P \neq \mathrm A$ のとき, 半直線 $\mathrm{CA}$ 上に $\mathrm{AB} = \mathrm{AB}'$ となるように点 $\mathrm B'$ をとり, $\triangle\mathrm{APB} \equiv \triangle\mathrm{AP}'\mathrm B'$ となるように点 $\mathrm P'$ をとると, 仮定から $\triangle\mathrm{APP}'$ は頂角が $60^\circ$ 以下の二等辺三角形となるので, $\mathrm{PA} \geqq \mathrm{PP}'$ となり, \begin{align*} \mathrm{PA}+\mathrm{PB}+\mathrm{PC} &\geqq \mathrm B'\mathrm P'+\mathrm P'\mathrm P+\mathrm{PC} \\ &> \mathrm B'\mathrm C = \mathrm B'\mathrm A+\mathrm{AC} = \mathrm{BA}+\mathrm{AC} \end{align*} となる. よって, $\mathrm{AP}+\mathrm{BP}+\mathrm{CP}$ は $\mathrm P = \mathrm A$ のとき最小になる.

定義≪フェルマー点≫

 $\triangle\mathrm{ABC}$ の各頂点までの距離の和が最小となるような点を $\triangle\mathrm{ABC}$ のフェルマー点またはトリチェリ点(Fermat point, Torricelli point)と呼ぶ.

正方形の $4$ 頂点の場合

定理≪正方形の $4$ 頂点の最短ネットワーク問題≫

 正方形 $\mathrm{ABCD}$ の $4$ 頂点を結ぶ最短経路は, \[\mathrm{PA} = \mathrm{QB} = \mathrm{QC} = \mathrm{PD},\ \angle\mathrm{APD} = \angle\mathrm{BQC} = 120^\circ\] を満たす正方形の内部の点 $\mathrm P,$ $\mathrm Q$ について, $2$ 本折れ線 $\mathrm{APD},$ $\mathrm{BQC}$ を線分 $\mathrm{PQ}$ でつないだ経路である.

証明

 三角不等式を使った議論により, 分岐点が $2$ 個の場合に帰着できる(詳細は省略). 対称性に着目すると, その $2$ 点が線分 $\mathrm{AD}$ の垂直二等分線上にある場合に帰着できる. その先の証明については, こちらを参照. 

問題

数学 B: ベクトル

問題≪$3$ 点の最短ネットワーク問題≫

(1)
平面上の単位ベクトル $\overrightarrow{e_1},$ $\overrightarrow{e_2},$ $\overrightarrow{e_3}$ が $\overrightarrow{e_1}+\overrightarrow{e_2}+\overrightarrow{e_3} = \vec 0$ を満たすとき, $\overrightarrow{e_1},$ $\overrightarrow{e_2},$ $\overrightarrow{e_3}$ の互いに成す角をそれぞれ求めよ.
(2)
すべての平面ベクトル $\vec a (\neq \vec 0),$ $\vec p$ に対して \[ |\vec a-\vec p| \geqq |\vec a|-\frac{\vec a}{|\vec a|}\cdot\vec p\] が成り立つことを示せ.
(3)
すべての内角が $120^\circ$ 未満の $\triangle\mathrm{ABC}$ において, 内部の点 $\mathrm P$ から各頂点までの距離の和 $L = |\overrightarrow{\mathrm{PA}}|+|\overrightarrow{\mathrm{PB}}|+|\overrightarrow{\mathrm{PC}}|$ が最小になるとき, 点 $\mathrm P$ はどのような位置にあるか.
[2001 東北大*]

解答例

(1)
$|\overrightarrow{e_1}+\overrightarrow{e_2}| = |-\overrightarrow{e_3}| = |\overrightarrow{e_3}| = 1$ の両辺を $2$ 乗すると, $|\overrightarrow{e_1}| = |\overrightarrow{e_2}| = 1$ から \[ 1 = |\overrightarrow{e_1}|^2+2\overrightarrow{e_1}\cdot\overrightarrow{e_2}+|\overrightarrow{e_2}|^2 = 2\overrightarrow{e_1}\cdot\overrightarrow{e_2}+2\] つまり $\overrightarrow{e_1}\cdot\overrightarrow{e_2} = -\dfrac{1}{2}$ となるので, $\overrightarrow{e_1}$ と $\overrightarrow{e_2}$ の成す角は $120^\circ$ である.
同様に, $\overrightarrow{e_2}$ と $\overrightarrow{e_3},$ $\overrightarrow{e_3}$ と $\overrightarrow{e_1}$ の成す角は $120^\circ$ である.
(2)
コーシー=シュワルツの不等式により, \begin{align*} |\vec a-\vec p| &= \left|\frac{\vec a}{|\vec a|}\right||\vec a-\vec p| \\ &\geqq \left|\frac{\vec a}{|\vec a|}\cdot (\vec a-\vec p)\right| = \left||\vec a|-\dfrac{\vec a}{|\vec a|}\cdot\vec p\right| \\ &\geqq |\vec a|-\dfrac{\vec a}{|\vec a|}\cdot\vec p \end{align*} が成り立つ.
(3)
$\mathrm A,$ $\mathrm B,$ $\mathrm C$ と異なる点 $\mathrm O$ を起点とした位置ベクトルによって $\mathrm A(\vec a),$ $\mathrm B(\vec b),$ $\mathrm C(\vec c),$ $\mathrm P(\vec p)$ とおく. (2) で示した不等式から, \begin{align*} |\overrightarrow{\mathrm{PA}}| &= |\vec a-\vec p| \geqq |\vec a|-\frac{\vec a}{|\vec a|}\cdot\vec p \quad \cdots [1], \\ |\overrightarrow{\mathrm{PB}}| &= |\vec b-\vec p| \geqq |\vec b|-\frac{\vec b}{|\vec b|}\cdot\vec p \quad \cdots [2], \\ |\overrightarrow{\mathrm{PC}}| &= |\vec c-\vec p| \geqq |\vec c|-\frac{\vec c}{|\vec c|}\cdot\vec p \quad \cdots [3] \end{align*} が成り立つ. 辺々を加えると, \[ L \geqq |\vec a|+|\vec b|+|\vec c|-\left(\frac{\vec a}{|\vec a|}+\frac{\vec b}{|\vec b|}+\frac{\vec c}{|\vec c|}\right)\cdot\vec p\] が得られる. $\dfrac{\vec a}{|\vec a|}+\dfrac{\vec b}{|\vec b|}+\dfrac{\vec c}{|\vec c|} = \vec 0$ が成り立つように点 $\mathrm O$ をとり直す. (1) で示したことから, このような点は $\angle\mathrm{AOB} = \angle\mathrm{BOC} = \angle\mathrm{COA}$ を満たす点として定まる. しかも, $\triangle\mathrm{ABC}$ の内角に関する条件から, この $\mathrm O$ は $\triangle\mathrm{ABC}$ の内部にとれることに注意する. このとき, \[ L \geqq |\vec a|+|\vec b|+|\vec c|\] が成り立つ. 等号成立は, $[1]$~$[3]$ で等号が成り立つ場合に限る. これは, $\vec p$ が $\vec a,$ $\vec b,$ $\vec c$ の定数倍であるときに限る. $\vec a,$ $\vec b,$ $\vec c$ は $\vec 0$ でなく互いに平行でないから, これは $\vec p = \vec 0$ となる場合である. ゆえに, 点 $\mathrm P$ が上記の点 $\mathrm O$ に一致するとき, つまり $\angle\mathrm{APB} = \angle\mathrm{BPC} = \angle\mathrm{CPA}$ を満たすときに限り, $L$ は最小となる.

背景

 分岐点を新たに設けてもよいという条件の下で, 与えられたいくつかの点をもれなく結ぶ最短経路を求める問題は, 「最短ネットワーク問題」(the shortest path problem)と呼ばれ, インフラの建設計画を立てたり, 電気回路の設計をしたりする際に現れる素朴で重要な問題である.
 $1$ 直線上にある $3$ 点を結ぶ最短経路は, 明らかに最も離れた $2$ 点を結ぶ線分である. よって, $3$ 点の「最短ネットワーク問題」については, $3$ 点が三角形をなす場合が問題になる. 「三角不等式」$\mathrm P_1\mathrm P_2+\mathrm P_2\mathrm P_3 \geqq \mathrm P_1\mathrm P_3$ を使うと, これは三角形の各頂点までの距離の和が最小になる点を求める問題に帰着できる(詳細は割愛する).
 $L$ の最小値を与える点 $\mathrm P$ は $\triangle\mathrm{ABC}$ の「フェルマー点」または「トリチェリ点」(Fermat point, Torricelli point)などと呼ばれる.

数学 III: 微分法

問題≪正方形の頂点の最短ネットワーク問題≫

 $xy$ 平面上に $4$ 点 $\mathrm A(1,1),$ $\mathrm B(−1,1),$ $\mathrm C(−1,−1),$ $\mathrm D(1,−1)$ をとる. また, $y$ 軸に関して対称になるように, $x$ 軸上に点 $\mathrm P,$ $\mathrm Q$ をとる. このとき, $L = \mathrm{PQ}+\mathrm{PA}+\mathrm{QB}+\mathrm{QC}+\mathrm{PD}$ の最小値と, 最小値を与える点 $\mathrm P$ の座標を求めよ.

解答例

 点 $\mathrm P$ の座標を $(x,0)$ とおく. $x < 0$ のとき線分 $\mathrm{PA}$ と $\mathrm{QB},$ $\mathrm{QC}$ と $\mathrm{PD}$ は交差してしまうので, $L$ の最小値を求めるには $x \geqq 0$ の場合を考えれば十分である. 対称性により, $f(x) = \mathrm{PO}+\mathrm{PA}+\mathrm{PD} = \mathrm{PO}+2\mathrm{PA}$ の最小値を求めればよい. $x \geqq 0$ のとき, \begin{align*} f(x) &= x+2\sqrt{(1-x)^2+1} = x+2\sqrt{x^2-2x+2}, \\ f'(x) &= 1+\frac{2x-2}{\sqrt{x^2-2x+2}} = \frac{2(x-1)+\sqrt{x^2-2x+2}}{\sqrt{x^2-2x+2}} \end{align*} から, \begin{align*} f'(x) = 0 &\iff 2(1-x) = \sqrt{x^2-2x+2} \\ &\iff 4(1-x)^2 = x^2-2x+2 \\ &\iff 3x^2-6x+2 = 0 \\ &\iff x = 1-\frac{1}{\sqrt 3} \end{align*} が成り立つ. よって, $f(x)$ の増減表は次のようになるから, $f(x)$ は $x = 1-\dfrac{1}{\sqrt 3}$ のとき極小かつ最小の値 $1+\sqrt 3$ をとる.
$x$$0$$\cdots$$1-\dfrac{1}{\sqrt 3}$$\cdots$
$f'(x)$$-$$0$$+$
$f(x)$$\searrow$$1+\sqrt 3$$\nearrow$
最小値は, 点 $\mathrm P$ から辺 $\mathrm{AD}$ に下した垂線の足 $\mathrm H$ について, $\mathrm{AH}:\mathrm{HP} = 1:\dfrac{1}{\sqrt 3} = \sqrt 3:1$ から $\mathrm{PA} = \dfrac{2}{\sqrt 3}$ であることを使って \[\left( 1-\frac{1}{\sqrt 3}\right) +2\cdot\frac{2}{\sqrt 3} = 1+\frac{3}{\sqrt 3} = 1+\sqrt 3\] と求めた.
ゆえに, $L$ は $\mathrm P\left( 1-\dfrac{1}{\sqrt3 },0\right)$ のとき最小値 $2(1+\sqrt 3)$ をとる.

背景

 正方形の頂点を結ぶ最短経路を求める問題は三角不等式 $\mathrm P_1\mathrm P_2+\mathrm P_2\mathrm P_3 \geqq \mathrm P_1\mathrm P_3$ を使った議論により, 本問のような場合に帰着されて(詳細は省略), その解は上の図のようになる.
 なお, $n \geqq 6$ のとき正 $n$ 角形 $\mathrm P_1\mathrm P_2\cdots\mathrm P_n\mathrm P_1$ の頂点を結ぶ最短経路は折れ線 $\mathrm P_1\mathrm P_2\cdots\mathrm P_n$ であることが知られている.
 複数の点を結ぶ最短経路は「最小シュタイナー木」と呼ばれ, その解法としていくつかの初等幾何学的なアルゴリズムが知られている.