|
$\S8. \ $ポアンカレモデル上のSteiner最小木問題(1) 最小木問題とは$n$点が与えれたとき，それらの点を線分で結ぶネットワークのうちの最短のものを求める問題であり， その最短の長さのネットワークを最小木という． さらに，考えるネットワークは，はじめに与えられた点だけを連結するのではなく，新しくいくつかの点を加えた 連結を考えたほうが短くなる場合がある．このネットワークをSteiner木という．Steiner木のうちで最小の長さのものを Steiner最小木という．Steiner最小木を求める問題をSteiner最小木問題という． 与えられた点を結ぶ線分だけで得られる最小木を求める問題に大きな困難はない．実際，$n$個の点が与えられたとき， 2点を結ぶ$_nC_2$本の線分のうち，連結（すべての点を結ぶことができる）の条件のもと長い線分から順に消去してい き，最後に残った $n-1$本が最小木である．これはもちろんポアンカレモデルでもそのまま用いることができる． 
しかしSteiner最小木はユークリッド平面でも簡単ではない．その難しさを説明する．3点のSteiner最小木は次のようになる． $\bullet \ \triangle ABC$のどの内角も$120^{\circ}$より小さいなら， $\triangle ABC$の内部に点$P$を $\angle APB=\angle BPC=\angle CPA(=120^{\circ})$ を満たすようにとれば，3点$A,B,C$のSteiner最小木は $AP+BP+CP$ である($P$の見つけ方は図を参照)． 
$\bullet \ \triangle ABC$で$\angle A \geqq 120^{\circ}$のとき3点$A,B,C$のSteiner最小木は $AB+BC$ である． 
この2つの定理がSteiner最小木問題の土台である．次に4点のSteiner最小木問題を考えてみよう．4点$A,B,C,D$が与えられたとき，Steiner最小木が1点$P$をとった $AP+BP+CP+DP$ となることはない．3点$A,B,P$に注目する（もし$\angle APB\geqq 120^{\circ}$なら他の3点を選ぶ）と $AP+BP$＞$AQ+BQ+PQ$ だからである． 
したがって，基本的には2点$P,Q$を付け加えた右のどちらかの図形がSteiner最小木の候補である．4点のSteiner最小木の候補はこれだけではない．3点で示した両方の場合が起こる，付け加える点が1つの場合もあり，さらに付け加える点が ない場合である最小木も候補である. すなわち右下の場合も考える必要もある． 
Steiner最小木問題は，解の候補となるのは4点の場合でもこれだけたくさんある．なお，Steiner最小木問題を考えるために，新しく付け加えて点， すなわち，その点から，与えられたいずれかの3点に 放射状に$120^{\circ}$のなす角で出ている点をSteiner点と呼ぶ． 5点の場合にSteiner最小木となる候補がどれだけあるか調べてみよう． Steiner点が3個ある場合は5通り Steiner点が２個の場合は$_5C_4\times 2=10$通り Steiner点が1個の場合は$_5C_3=10$通り Steiner点が0個の場合は$1$通り で26通りある．もちろんこの中には明らかに最小にならない場合もあり，もう少し増える場合もある． 実際，Steiner最小木の候補の個数は与える点が増えれば指数関数的に増加して，NP(Non deterministic polynomial time)困難問題 として計算機数学の対象の問題になっている． Steiner最小木問題の純数学的な扱いについては， Gilbert,E.N.and H.O.Pollak,1968,"Steine Minimal Trees." Siam J.Appl.Math 16,1-29. が詳しい． $n$個の点が与えられとき，最小木のネットワークの長さを$L_m$,Steiner最小木のネットワークの長さを$S_m$をとするとき， $\dfrac{L_s}{L_m}$ の値は興味ある問題である．この値をSteiner 比という．上記論文によると， $\dfrac{L_s}{L_m}\geqq \dfrac{\sqrt{3}}{2}\cdots (\sharp)$ がconjectureとして載っている．50年前の論文のなので今でもconjectureなのかどうかは分からない． ただ，3点が正三角形の時$\frac{\sqrt{3}}{2}$で，3点の場合に$(\sharp)$がなりたつことは容易に証明できる． 本稿の目的は，ポアンカレモデル上で，Steiner最小木を考えることである． ポアンカレモデル上ではSteiner比が$\frac{\sqrt{3}}{2}$ より小さくなる例が幾らでもありそれらを示しさらに下限が$\frac{1}{2}$であることを示す． 以下考えている空間は，特別に断らない限り， 上半平面 $\mathbb{H}^+=\{(x,y)\in \mathbb{R}^2|y$＞$０\}$ において第１基本形式 T$=\dfrac{(dx^2+dy^2)}{y^2}$ で定義された空間,すなわちポアンカレ非ユークリッドモデルである． 今までと同じように，２点$A,B$間の距離は$AB$で表し，線分$AB,AC$のなす角 （$A$における接線のなす角）は$\angle BAC$と表す． ポアンカレモデル上でSteiner最小木問題を扱うとき，基本になることは3点のSteiner最小木を求めることである． 基本的なことであるが次の性質を証明する． 
定理13点$A,B,C$が与えれいる．このとき $PA+PB+PC$ を最小にする点$P$は$\triangle ABC$の内部または周上にある． 証明 $P$が$\triangle ABC$の外部にあるとき，$PA+PB+PC$が最小でないことを示す． $\bullet PB,PC$が辺と交わらないとき． $AB+AC$＜$QB+QC$＜$PB+PC$ $\bullet PA,PB,PC$のいずれかが辺と交わるとき． $PA+PB+PC$＞$AC+RB$ したがって，いずれの場合も$P$は最小値を与えない． 
3点$A,B,C$が与えれいるとき$PA+PB+PC$ を最小にする点$P$を調べよう． 点$P$は頂点$A,B,C$のいずれかまたはそれ以外かである． 点$P$が頂点$A,B,C$のいずれかになるときはその点は最大内角の点である． 点$P$が頂点でないときは，点$P$は $\angle BPC=\angle CPA=\angle APB=120^{\circ}$ を満たす． それは，すでにポアンカレモデルの幾何学(2)の定理２で述べたように，$A$を中心とする 半径$AP$の円を描き，$P$のその円周上を動いたときの$BP+CP$を最小にする点であるから $\angle APB=\angle APC$ をみたす．さらに他の頂点でも同じ事を行えば $\angle BPC=\angle CPA=\angle APB=120^{\circ}\cdots (\sharp)$ が得られる． また，定理１より，点$P$は$\triangle ABC$の内部の点である（周上に条件を満たす点は存在しない）． $\triangle ABC$の内部の点を$P$とすると $\angle APC$＞$\angle BAC$ であるので，$\triangle ABC$の内角の１つが$120^{\circ}$以上のとき$(\sharp)$を満たす点$P$は存在しないので， $PA+PB+PC$を最小にする点$P$は最大内角の頂点である． ここで，ユークリッド原論の中のポアンカレモデルでも成り立つ命題を述べておこう．ユークリッド原論の命題のうち第１命題から 第２８命題までは第５公準を用いていないので，当然ポアンカレモデルでも成り立つ命題である． その中で，今まで用いたものや， よく使う命題を述べる． 第４命題 ２辺とその間の角の合同条件 第８命題 3辺相等の合同条件 第16命題 三角形の外角は内対角の１つより大きい 第18命題 三角形の大きい辺に対応する角は大きい 第19命題 18命題の逆 第20命題 三角形の２辺の和は第３辺より大きい 第21命題 三角形の内部に同一底辺上に立つ三角形のつくれば， 後者の残りの２辺の和は前者の残りの２辺の和より小さく，より大きい角を はさむ． 第24命題 ２辺をそれぞれ等しくする２つの三角形のうち，等しい辺にはさまれる角が大きいほうが大きい対辺を持つ 第25命題 第24命題の逆 第26命題 １辺とその両端の角の合同条件 まず，三点が正三角形の頂点になるときのSteiner比を計算する． １点$O$を定め，点$O$から放射状になす角が$120^{\circ}$で伸びている半直線で考える． 点$O$が3点$A,B,C$のSteiner点である． $OA=OB=OC=x$ と置けば， 
双曲幾何の三角法より$AB=a$ は $\cosh a=\cosh^2 x+\dfrac{\sinh ^2 x}{2}$ を満たす．このとき関数 $f(x)=\dfrac{3x}{2a}$ の値が，１辺の長さ$a$の正三角形のSteiner ratioである． 定義域$(0,\infty)$で単調減少で， $\displaystyle \lim_{x\to \infty}f(x)=\dfrac{3}{4}$ $\displaystyle \lim_{x\to +0}f(x)=\dfrac{\sqrt{3}}{2}$ したがって，正三角形のSteiner 比$\rho$は $\dfrac{3}{4}$＜$\rho$＜$\dfrac{\sqrt{3}}{2}$ 右上図は$y=f(x)$の$0\leqq x \leqq 20$におけるグラフ． 
次に一般の３点で考える．Steiner点が存在すれるときだけ扱えばよいので，Steiner点を$O$とし，正三角形の場合と同様に， $OA=x,OB=sx,OC=tx, \ \ 1\leqq s,t ,0$＜$x$ とし，$AB=c,AC=b$のとき， $\cosh c=\cosh x\cosh sx +\dfrac{\sinh x \sinh sx}{2}$ $\cosh b=\cosh x\cosh tx +\dfrac{\sinh x \sinh tx}{2}$ である． 3点$A,B,C$のSteiner ratioは $\dfrac{x+sx+tx}{b+c}$ である．この値は$s,t$に関して単調増加である（微分してもよいが，パソコンでグラフを描くのが手っ取り早い）． したがって，$x=y=1$のときだけ考えればよいので，正三角形の場合に帰着される． 三角形のSteiner比$\rho$は $\dfrac{3}{4}$＜$\rho$ が証明された． ポアンカレモデル上のSteiner 最小木問題(2) 目次に戻る 微分幾何 |