Steiner木

同義語：シュタイナー木Steiner tree

概要

前提知識: Fermat点, 一筆書きとグラフ, 対称点と折れ線の最短

高校での出発点：4 つの町を結ぶ道路網

1 辺 $1$ km の正方形の 4 つの角に町 $A$、$B$、$C$、$D$ がある。4 つの町のどの 2 つの間も道路を通って行き来できるように、まっすぐな道路をつないだ道路網を作る。道路の長さの合計をいちばん短くするには、どう作ればよいだろうか。道路は途中で分かれてもよく、町以外の場所に分かれ道（分岐点）を置いてもよい。

正方形の 4 頂点を結ぶ 3 つの道路網

$A(0,0)$、$B(1,0)$、$C(1,1)$、$D(0,1)$ とする。
(1) 3 辺を使う：$AB$、$BC$、$CD$ の 3 本で、長さは $1+1+1=3$ である。
(2) 2 本の対角線を使う：$AC$ と $BD$ は中心 $\left(\dfrac12,\dfrac12\right)$ で交わり、長さは $\sqrt2+\sqrt2=2\sqrt2\approx2.828$ である。
(3) 分岐点を 2 つ置く：$S_1\left(\dfrac12,\dfrac{\sqrt3}6\right)$、$S_2\left(\dfrac12,1-\dfrac{\sqrt3}6\right)$ をとり、$S_1$ を $A$、$B$、$S_2$ に、$S_2$ を $C$、$D$ に結ぶ。
$$ AS_1=\sqrt{\left(\frac12\right)^2+\left(\frac{\sqrt3}6\right)^2}=\sqrt{\frac14+\frac1{12}}=\sqrt{\frac13}=\frac{\sqrt3}3 $$
で、$BS_1$、$CS_2$、$DS_2$ も同じく $\dfrac{\sqrt3}3$ である。$S_1S_2=1-\dfrac{\sqrt3}3$ なので、長さは
$$ 4\cdot\frac{\sqrt3}3+1-\frac{\sqrt3}3=1+\sqrt3\approx2.732 $$
である。
(3) がいちばん短い。(3) では、分岐点 $S_1$ から出る 3 本の道路が互いに $120^\circ$ の角をなしている。たとえば $\overrightarrow{S_1A}=\left(-\dfrac12,-\dfrac{\sqrt3}6\right)$、$\overrightarrow{S_1B}=\left(\dfrac12,-\dfrac{\sqrt3}6\right)$ の内積は $-\dfrac14+\dfrac1{12}=-\dfrac16$ で、長さの積 $\dfrac13$ で割ると $-\dfrac12=\cos120^\circ$ である。

1 辺 1 の正方形の 4 頂点を結ぶ道路網。左から、3 辺（長さ 3）、2 本の対角線（長さ 2√2≈2.828）、分岐点を 2 つ置いた網（長さ 1+√3≈2.732）
3 つの点を結ぶ場合は、3 点までの距離の和が最小になる 1 点（Fermat 点）で道路を分ければよく、そこでは 3 本の道路が $120^\circ$ で出会う（Fermat点）。点が 4 つ以上になると、分岐点がいくつ要るのか、どこに置くのかが問題になる。この記事で答える問いは次の 3 つである。

最も短い道路網は、どんな形をしているか。→ thm-stn-shape
正方形の 4 頂点では、(3) の $1+\sqrt3$ が本当に最短か。→ thm-stn-square

分岐点を置かずに町どうしを直接結ぶと、どれだけ長くなるか。→ ex-stn-mst

高校の計算	この記事の言葉	大学の言葉
3 点までの距離の和の最小（Fermat 点）	分岐点で $120^\circ$ に分かれる	局所的な最小の条件
頂点・辺・次数（一筆書き）	道路網をグラフとみる	平面に描いた木
$60^\circ$ の回転で折れ線をのばす	最短の長さの下からの評価	組合せ最適化の下界
町どうしを直接結ぶ	最小全域木	Steiner 比

言葉の準備：ネットワークと木

ネットワークと Steiner 木

平面の $n$ 個（$n\ge2$）の異なる点 $P_1,\dots,P_n$ が与えられているとする。有限個の線分を合わせた図形 $N$ で、次の 2 つを満たすものを、$P_1,\dots,P_n$ を結ぶ ネットワーク という。
(1) $P_1,\dots,P_n$ はどれも $N$ の上にある。
(2) $N$ はつながっている。つまり、$N$ の上のどの 2 点も、$N$ の上を通る道で結べる。
線分どうしは重ならない（共有点があっても有限個）ようにとり、$N$ の長さを線分の長さの和とする。$P_1,\dots,P_n$ を結ぶネットワークのうちで長さが最小のものを、$P_1,\dots,P_n$ の Steiner 木（最短のネットワーク）という。

ネットワークは、一筆書きとグラフで学んだグラフとして見ることができる。与えられた点、線分の端点、2 本の線分の交点を頂点とし、頂点で区切られた線分の各部分を辺とする。1 つの頂点から出る辺の本数をその頂点の次数という。次数の和は辺の数の 2 倍に等しい（一筆書きとグラフの定理）。1 本の線分の途中の点で、ほかの線分と交わらないものは頂点にしない。2 本の線分が一直線につながっていて、ほかの線分が出ていない点も、1 本の線分とみなして頂点にしない（その点が与えられた点なら頂点にする）。

木と分岐点

つながっていて、同じ辺を 2 度通らずに出発点にもどる道（閉路）をもたないグラフを木という。ネットワークの頂点のうち、与えられた点 $P_1,\dots,P_n$ 以外のものを 分岐点（Steiner 点）という。

グラフとして数える

ex-stn-start の 3 つの道路網をグラフとして見る。
(1) 3 辺の網：頂点は $A$、$B$、$C$、$D$ の 4 つ、辺は 3 本。次数は $A$ と $D$ が $1$、$B$ と $C$ が $2$ で、和は $6=2\cdot3$ である。閉路はなく、木である。分岐点はない。
(2) 対角線の網：2 本の線分の交点 $O\left(\dfrac12,\dfrac12\right)$ も頂点で、頂点は 5 つ、辺は $OA$、$OB$、$OC$、$OD$ の 4 本である。$O$ は分岐点で、次数は $4$ である。
(3) 分岐点 2 つの網：頂点は 6 つ、辺は 5 本。次数は $S_1$、$S_2$ が $3$、4 つの町が $1$ で、和は $3+3+1+1+1+1=10=2\cdot5$ である。
どの木でも、辺の数は頂点の数より $1$ 少ない（$4-1=3$、$5-1=4$、$6-1=5$）。これが次の補題である。

木の辺の数

頂点が $m$ 個の木の辺の数は $m-1$ である。

要点：頂点が $2$ 個以上の木には次数 $1$ の頂点がある。その頂点と辺を 1 つずつ取り除いても木のままなので、$m$ についての数学的帰納法で示せる。

詳しい証明を開く

段 1（次数 1 の頂点がある）。頂点が $2$ 個以上の木で、同じ頂点を 2 度通らない道のうち辺の数が最も多いものを 1 つとり、その端の頂点を $v$ とする。木はつながっていて頂点が 2 個以上なので、この道は辺を 1 本以上もち、$v$ の次数は $1$ 以上である。$v$ に道の辺以外の辺 $vw$ があるとすると、$w$ が道の上にあれば閉路ができ、道の上になければ道を $w$ まで延ばせて、どちらも矛盾である。よって $v$ の次数は $1$ である。

段 2（帰納法）。$m=1$ なら辺は $0$ 本で、$m-1=0$ である。$m\ge2$ のとき、段 1 の $v$ と、$v$ から出る 1 本の辺を取り除く。残りはつながっていて（$v$ を通る道は $v$ で終わるので、残りの 2 頂点を結ぶ道は $v$ を通らない）、閉路もないので、頂点 $m-1$ 個の木である。帰納法の仮定からその辺の数は $m-2$ で、もとの木の辺の数は $m-1$ である。$\square$

主定理 1：最短のネットワークの形

最短のネットワークの形は、「少しでも短くできる所があれば最短ではない」という考え方で決まる。短くする道具は 3 つある。閉路の辺を 1 本外す、折れ曲がった 2 本を 1 本の線分にする、$120^\circ$ 未満の角を Fermat 点で置きかえる、である。

最短のネットワークの形

$N$ を $P_1,\dots,P_n$ の Steiner 木（最短のネットワーク）とする。$N$ をグラフとみると、次が成り立つ。
(1) $N$ は木である。
(2) どの頂点でも、そこから出る 2 本の辺のなす角は $120^\circ$ 以上である。
(3) どの頂点も次数は $3$ 以下である。分岐点の次数はちょうど $3$ で、3 本の辺は互いに $120^\circ$ の角をなす。
(4) 分岐点の個数は $n-2$ 以下である。

方針：(1)〜(3) は、条件が崩れていると仮定して、もっと短いネットワークを作り、最短であることに矛盾させる。(4) は次数を数える。
段 1（(1) 木である）。$N$ に閉路があるとし、閉路の上の辺 $e$ を 1 本とる。$e$ の両端の頂点は残したまま、$e$ の端点以外の部分を取り除く。$e$ を通っていた道は、閉路の残りの部分を回り道すれば通れるので、図形はつながったままで、与えられた点もすべて残る。長さは $e$ の長さだけ短くなり、$N$ が最短であることに矛盾する。
段 2（(2) $120^\circ$ 以上）。頂点 $V$ から出る 2 本の辺 $VX$、$VY$ のなす角 $\theta=\angle XVY$ が $120^\circ$ 未満だとする。線分は重ならないので $\theta>0^\circ$ である。$VX$、$VY$ の長さより小さい正の数 $\varepsilon$ をとり、$VX$ の上に $VX'=\varepsilon$、$VY$ の上に $VY'=\varepsilon$ となる点 $X'$、$Y'$ をとる。三角形 $VX'Y'$ は頂角 $\theta<120^\circ$ の二等辺三角形で、底角は $\dfrac{180^\circ-\theta}2<90^\circ$ なので、3 つの角はすべて $120^\circ$ 未満である。Fermat点の主定理により、3 点 $V$、$X'$、$Y'$ までの距離の和を最小にする点 $F$ がただ 1 つあり、$F$ は三角形の内部にある。$V$ での距離の和は $0+\varepsilon+\varepsilon=2\varepsilon$ で、$F\ne V$ なので
$$ FV+FX'+FY'<2\varepsilon $$
である。$N$ から線分 $VX'$、$VY'$ を取り除き、3 本の線分 $FV$、$FX'$、$FY'$ を加える。$V$、$X'$、$Y'$ は $F$ を通ってつながっているので、図形はつながったままで、与えられた点もすべて残る（新しい線分がほかの線分と重なる部分があれば、1 本にまとめて長さはさらに短くなる）。長さは $2\varepsilon-(FV+FX'+FY')>0$ だけ短くなり、矛盾する。
段 3（(3) 次数）。頂点 $V$ から $k$ 本（$k\ge2$）の辺が出ているとする。$V$ のまわりに辺を順に並べると、となり合う辺のなす $k$ 個の角の和は $360^\circ$ で、段 2 からどの角も $120^\circ$ 以上なので、$120^\circ\times k\le360^\circ$、つまり $k\le3$ である。
次に分岐点 $V$ の次数を調べる。次数が $1$ なら、$V$ から出る辺を $V$ ごと取り除いても、図形はつながったままで与えられた点も残り（$V$ は与えられた点ではない）、短くなるので矛盾する。次数が $2$ なら、2 本の辺 $VX$、$VY$ のなす角 $\angle XVY$ は段 2 から $120^\circ$ 以上で、頂点の決め方から $180^\circ$ ではない。三角形 $XVY$ ができるので、2 本を線分 $XY$ に取りかえると（$XY$ がほかの線分と重なる部分があれば 1 本にまとめる）、$XY< XV+VY$（対称点と折れ線の最短の 3 点の三角不等式）から短くなり、矛盾する。よって分岐点の次数は $3$ である。3 つの角はどれも $120^\circ$ 以上で和が $360^\circ$ なので、どれもちょうど $120^\circ$ である。
段 4（(4) 分岐点の個数）。分岐点の個数を $s$ とすると、頂点は $n+s$ 個で、(1) と lem-stn-tree-edges から辺は $n+s-1$ 本である。次数の和は辺の数の 2 倍なので $2(n+s-1)$ である。一方、与えられた点の次数はどれも $1$ 以上（$n\ge2$ でつながっているから）、分岐点の次数は段 3 からちょうど $3$ なので、次数の和は $n+3s$ 以上である。よって
$$ 2(n+s-1)\ge n+3s,\qquad\text{つまり}\qquad s\le n-2 $$
である。$\square$

頂点 V で 2 本の辺のなす角が 120° 未満なら、V の近くの X'、Y' と V の 3 点の Fermat 点 F を分岐点にすると、赤の 2 本を青の 3 本に取りかえて短くできる
thm-stn-shape は「最短のネットワークがあれば、その形はこうなる」という主張である。与えられた点がいくつでも最短のネットワークがあることは正しいが、この記事では証明しない。正方形の 4 頂点については、thm-stn-square で最短のネットワークを実際に求める。

主定理 1 の条件を確かめる

1 辺 $1$ の正三角形の 3 頂点（$n=3$）。分岐点は $n-2=1$ 個以下である。分岐点がないと、ネットワークは与えられた 3 点だけを頂点とする木で、辺は 2 本、たとえば 2 辺 $AB$、$AC$ である。頂点 $A$ で 2 本のなす角は $60^\circ$ で、(2) に反するので最短ではない。分岐点を中心 $G$ に 1 つ置くと、3 本の辺は $120^\circ$ で出会い、長さは $3\cdot\dfrac{\sqrt3}3=\sqrt3\approx1.732$ で、2 辺の長さ $2$ より短い。
$A(0,0)$、$B(1,0)$、$C(-1,1)$ の 3 点（$\angle A=135^\circ$）。2 辺 $AB$、$AC$ だけのネットワークは、$A$ での角が $135^\circ\ge120^\circ$ で (2) を満たす。3 点までの距離の和は $A$ で最小（Fermat点の $120^\circ$ 以上の角の命題）なので、分岐点 $S$ を 1 つ置いて $A$、$B$、$C$ に結ぶ網は、どこに $S$ を置いても長さ $SA+SB+SC\ge1+\sqrt2\approx2.414$ で、2 辺の網より短くならない。
ex-stn-start の (3)（$n=4$）。分岐点は $2=n-2$ 個で (4) の上限に等しく、どちらも次数 $3$、角は $120^\circ$ である。(2) の対角線の網は、分岐点 $O$ の次数が $4$ で角が $90^\circ$ なので (2)・(3) に反し、最短ではない。

主定理 2：正方形の 4 頂点を結ぶ最短のネットワーク

ex-stn-start の (3) の長さ $1+\sqrt3$ が最短であることを示す。どんなネットワークも $1+\sqrt3$ 以上であることを、分岐点の数と結び方で場合を分けて確かめる。道具を 2 つ用意する。

$60^\circ$ の回転による下限

点 $X$、$Y$ と、線分 $XY$ を 1 辺とする正三角形 $XYE$ の 3 つ目の頂点 $E$（直線 $XY$ のどちら側でもよい）をとる。どの点 $P$、$Z$ についても
$$ PX+PY+PZ\ge ZE $$
である。

Fermat点の $60^\circ$ の回転の補題と同じ議論である。$X$ を中心とし $Y$ を $E$ に移す $60^\circ$ の回転を $\rho$ とし、$P'=\rho(P)$ とする。回転は長さを変えないので $XP'=XP$ で、$\angle PXP'=60^\circ$ だから、$P\ne X$ なら三角形 $XPP'$ は正三角形で $PP'=PX$ である（$P=X$ なら $P'=X$ で $PP'=0=PX$）。また $\rho(P)=P'$、$\rho(Y)=E$ から $P'E=PY$ である。よって、3 点の三角不等式を 2 回使って
$$ PX+PY+PZ=ZP+PP'+P'E\ge ZP'+P'E\ge ZE $$
である。$\square$

ネットワークを木に直す

$P_1,\dots,P_n$ を結ぶどのネットワーク $N$ からも、次の (i)〜(iii) を満たす「グラフ」$T$ が作れる。
(i) $T$ の頂点は、$P_1,\dots,P_n$ と、何個かの分岐点である。分岐点の次数は $3$ 以上である。
(ii) $T$ の各辺は、2 つの頂点を結ぶ折れ線（$N$ の一部）で、辺どうしは端点以外で共有点をもたない。$T$ は木である。
(iii) $T$ の辺の長さの和は $N$ の長さ以下である。
とくに、$N$ の長さは、$T$ の各辺の両端の頂点の距離の和以上である。また、$T$ の分岐点の個数は $n-2$ 以下である。

要点：$N$ の閉路の辺を外して木にし、与えられた点でない次数 $1$ の頂点を辺ごと取り除き、与えられた点でない次数 $2$ の頂点では 2 本の辺を 1 本の折れ線とみなす。どの操作も長さを増やさない。最後の 2 つの主張は、折れ線の長さが両端の距離以上であることと、thm-stn-shape の段 4 と同じ数え方から出る。

詳しい証明を開く

段 1（閉路をなくす）。$N$ をグラフとみて、閉路がある間は、閉路の上の辺を 1 本ずつ（端点を残して）取り除く。thm-stn-shape の段 1 と同じく、つながったままで与えられた点も残り、長さは増えない。辺の数は有限なので、いつか閉路がなくなり、木になる。

段 2（余分な枝を落とす）。与えられた点でない次数 $1$ の頂点があれば、その頂点と辺を取り除く。木のままで、与えられた点は残る。これを、そのような頂点がなくなるまで続ける（頂点の数は減り続けるので、いつか終わる）。

段 3（次数 2 の点をまとめる）。与えられた点でない次数 $2$ の頂点 $V$ では、$V$ から出る 2 本の辺を、$V$ を通る 1 本の折れ線とみなし、$V$ を頂点から外す。これを繰り返すと、与えられた点でない頂点はどれも次数 $3$ 以上になる。できたグラフ $T$ は木のままで、辺の長さの和は段 2 の後と同じである。これで (i)〜(iii) が示せた。

段 4（距離の和）。$T$ の各辺は両端の頂点を結ぶ折れ線なので、その長さは両端の距離以上である（3 点の三角不等式をくり返し使う）。よって $N$ の長さ $\ge$（$T$ の辺の長さの和）$\ge$（各辺の両端の距離の和）である。

段 5（分岐点の個数）。$T$ の分岐点の個数を $s$ とすると、lem-stn-tree-edges から辺は $n+s-1$ 本で、次数の和 $2(n+s-1)$ は、与えられた点の次数 $1$ 以上と分岐点の次数 $3$ 以上から $n+3s$ 以上である。よって $s\le n-2$ である。$\square$

正方形の 4 頂点の Steiner 木

1 辺 $1$ の正方形 $ABCD$（$A(0,0)$、$B(1,0)$、$C(1,1)$、$D(0,1)$）の 4 頂点を結ぶネットワークの長さは、どれも $1+\sqrt3$ 以上である。ex-stn-start の (3) の網の長さは $1+\sqrt3$ なので、4 頂点の Steiner 木の長さは $1+\sqrt3$ である。

方針：任意のネットワーク $N$ に lem-stn-reduce を使って木 $T$ にし、分岐点の個数 $s$（$0\le s\le4-2=2$）で場合を分ける。どの場合も、$T$ の辺の両端の距離の和が $1+\sqrt3$ 以上であることを示す。正方形の 2 頂点の距離は $1$ か $\sqrt2$ なので、どれも $1$ 以上であることを何度も使う。
段 1（$s=0$）。$T$ は 4 頂点 $A$、$B$、$C$、$D$ だけの木で、lem-stn-tree-edges から辺は $3$ 本である。各辺の両端は正方形の 2 頂点なので距離は $1$ 以上で、和は $3$ 以上である。
段 2（$s=1$、分岐点 $S$ の次数が $4$）。木では同じ 2 頂点を結ぶ辺は 1 本しかない（2 本あれば閉路になる）。$s=1$ のとき、$S$ と辺で結ばれる頂点は $A$、$B$、$C$、$D$ のうちの異なる点なので、$S$ の次数は $4$ 以下で、lem-stn-reduce の (i) から $3$ 以上である。次数が $4$ なら、$S$ は $A$、$B$、$C$、$D$ のすべてと辺で結ばれている。距離の和は $SA+SB+SC+SD\ge AC+BD=2\sqrt2$ である（3 点の三角不等式 $SA+SC\ge AC$、$SB+SD\ge BD$）。
段 3（$s=1$、分岐点 $S$ の次数が $3$）。$S$ は 4 頂点のうち 3 つと結ばれている。残りの 1 頂点 $W$ は $S$ と結ばれていないが次数は $1$ 以上なので、正方形のほかの頂点と結ぶ辺があり、その辺の距離は $1$ 以上である。$S$ と結ばれた 3 頂点は、正方形を $90^\circ$ ずつ回すと $A$、$B$、$D$ に重ねられるので、$A$、$B$、$D$ の場合を調べればよい。lem-stn-rotation を $X=A$、$Y=B$、$Z=D$、$P=S$、正方形の外側の正三角形の頂点 $E\left(\dfrac12,-\dfrac{\sqrt3}2\right)$ に使うと
$$ SA+SB+SD\ge DE=\sqrt{\left(\frac12\right)^2+\left(1+\frac{\sqrt3}2\right)^2}=\sqrt{2+\sqrt3}\approx1.932 $$
である。距離の和は $1.932+1=2.932$ 以上である。
段 4（$s=2$：形が決まる）。分岐点を $S_1$、$S_2$、次数を $d_1$、$d_2$（どちらも $3$ 以上）とする。頂点は $6$ 個、辺は $5$ 本で、次数の和は $10$ である。4 頂点の次数はどれも $1$ 以上なので $d_1+d_2\le10-4=6$ で、$d_1=d_2=3$、4 頂点の次数はどれもちょうど $1$ である。$S_1$ と $S_2$ が辺で結ばれていないと、$S_1$ の 3 本と $S_2$ の 3 本は異なる辺で、辺が $6$ 本以上になって矛盾する。よって $S_1S_2$ は辺で、$S_1$ は残り 2 本で、$S_2$ も残り 2 本で正方形の頂点と結ばれている。4 頂点の次数は $1$ なので、$S_1$ と結ばれた 2 頂点と $S_2$ と結ばれた 2 頂点は重ならない。結び方は、$\{A,B\}$ と $\{C,D\}$、$\{A,D\}$ と $\{B,C\}$、$\{A,C\}$ と $\{B,D\}$ の 3 通りである。
段 5（$s=2$、$\{A,B\}$ と $\{C,D\}$）。$S_1$ が $A$、$B$ と、$S_2$ が $C$、$D$ と結ばれているとする（逆でも名前を入れかえるだけである）。距離の和は $S_1A+S_1B+S_1S_2+S_2C+S_2D$ である。lem-stn-rotation を $X=A$、$Y=B$、$P=S_1$、$Z=S_2$、$E\left(\dfrac12,-\dfrac{\sqrt3}2\right)$ に使うと
$$ S_1A+S_1B+S_1S_2\ge S_2E $$
である。もう一度 lem-stn-rotation を $X=D$、$Y=C$、$P=S_2$、$Z=E$ と、正方形の上側の正三角形 $DCF$ の頂点 $F\left(\dfrac12,1+\dfrac{\sqrt3}2\right)$ に使うと
$$ S_2D+S_2C+S_2E\ge EF=\left(1+\frac{\sqrt3}2\right)+\frac{\sqrt3}2=1+\sqrt3 $$
である。2 つを合わせて、距離の和は $1+\sqrt3$ 以上である。$\{A,D\}$ と $\{B,C\}$ の場合は、正方形を $90^\circ$ 回すとこの場合に重なるので、同じく $1+\sqrt3$ 以上である。
段 6（$s=2$、$\{A,C\}$ と $\{B,D\}$）。距離の和は $S_1A+S_1C+S_1S_2+S_2B+S_2D\ge AC+BD=2\sqrt2\approx2.828$ である。
段 7（まとめ）。どの場合も、lem-stn-reduce により $N$ の長さは $T$ の辺の両端の距離の和以上で、それは $3$、$2\sqrt2$、$2.932$、$1+\sqrt3$ のどれか以上である。この中で最も小さいのは $1+\sqrt3\approx2.732$ なので、$N$ の長さは $1+\sqrt3$ 以上である。ex-stn-start の (3) で等号が成り立つ。$\square$

下限の等号を確かめる

ex-stn-start の (3) の $S_1\left(\dfrac12,\dfrac{\sqrt3}6\right)$、$S_2\left(\dfrac12,1-\dfrac{\sqrt3}6\right)$ では、段 5 の 2 つの不等式がどちらも等号になる。
$$ S_1A+S_1B+S_1S_2=\frac{2\sqrt3}3+1-\frac{\sqrt3}3=1+\frac{\sqrt3}3,\qquad S_2E=\left(1-\frac{\sqrt3}6\right)+\frac{\sqrt3}2=1+\frac{\sqrt3}3 $$
である。$S_1$、$S_2$ はどちらも線分 $EF$（直線 $x=\dfrac12$ の一部）の上にある。図 3 のように、正方形の外側に 2 つの正三角形を立てると、Steiner 木の真ん中の辺は線分 $EF$ の一部になる。

正方形の下に正三角形 ABE、上に正三角形 DCF を立てると、線分 EF の長さ 1+√3 が下限になる。Steiner 木（赤）の分岐点 S1、S2 は線分 EF の上にある
thm-stn-square と同じ長さ $1+\sqrt3$ の網は、ex-stn-start の (3) を $90^\circ$ 回したもの（分岐点を $x$ 軸に平行に並べたもの）もある。最短のネットワークはただ 1 つとは限らない。

分岐点を置かない場合と比べる

最小全域木

与えられた点 $P_1,\dots,P_n$ だけを頂点とし、そのうち 2 点を結ぶ線分を辺とする木を考える。その中で辺の長さの和が最小のものを、$P_1,\dots,P_n$ の 最小全域木 という。分岐点を置かない最短の道路網である。

最小全域木は、辺を短い順に並べ、閉路ができない限り順に加えていく方法（Kruskal の方法）で求められる（KT17 §12.1、Algorithm 12.8）。この記事では、点が少ない場合に長さを直接比べる。

最小全域木の長さ

1 辺 $1$ の正三角形：どの 2 頂点の距離も $1$ で、辺は $2$ 本要るので、最小全域木の長さは $2$ である。Steiner 木は中心を分岐点とする長さ $\sqrt3\approx1.732$ の網である（分岐点がなければ長さは $2$ 以上、分岐点が 1 つなら Fermat点の最小値 $\sqrt3$ 以上になることが、lem-stn-reduce で木に直し、thm-stn-square と同じく分岐点の数で場合を分けると分かる）。
1 辺 $1$ の正方形：2 頂点の距離は $1$ か $\sqrt2$ で、辺は $3$ 本要り、長さ $1$ の辺だけで木が作れるので、最小全域木の長さは $3$ である。Steiner 木は $1+\sqrt3\approx2.732$ である（thm-stn-square）。
1 辺 $1$ の正六角形：2 頂点の距離は $1$ 以上で、辺は $5$ 本要り、5 つの辺で木が作れるので、最小全域木の長さは $5$ である。
横 $\dfrac32$、縦 $1$ の長方形：2 頂点の距離は $1$、$\dfrac32$、$\dfrac{\sqrt{13}}2$ のどれかで、辺は $3$ 本要る。長さ $1$ の辺（縦の 2 辺）は 2 本しかないので、長さは $1+1+\dfrac32=\dfrac72$ 以上で、縦の 2 辺と横の 1 辺でちょうど $\dfrac72$ になる。

与えられた点	最小全域木	分岐点を置いた網	比
1 辺 $1$ の正三角形	$2$	$\sqrt3\approx1.732$（Steiner 木）	$\dfrac{\sqrt3}2\approx0.866$
1 辺 $1$ の正方形	$3$	$1+\sqrt3\approx2.732$（Steiner 木）	$\approx0.911$
$\dfrac32\times1$ の長方形	$\dfrac72=3.5$	$\dfrac32+\sqrt3\approx3.232$	$\approx0.923$
1 辺 $1$ の正六角形	$5$	対称な網 $3\sqrt3\approx5.196$（最短ではない）	$\approx1.039$

分岐点を置くと短くなることが多いが、いつもではない。正六角形の対称な網は、thm-stn-shape の角の条件をすべて満たすのに、最小全域木より長い（ex-stn-cx-hex）。長方形の網が最短であることは thm-stn-square と同じ場合分けで示せるが、この記事では細部を書かない。正六角形の Steiner 木がどれかは、この記事では求めない。

例と反例

外す条件	反例	成り立たなくなること
分岐点を置いてよい	正方形の最小全域木	長さが最短 $1+\sqrt3$ である
最短である（$120^\circ$ の条件だけを満たす）	$\dfrac32\times1$ の長方形の縦向きの網	最短である
最短である（$120^\circ$ の条件だけを満たす）	正六角形の対称な網	最小全域木より短い
与えられた点で 2 本の辺が $120^\circ$ 以上	直角二等辺三角形の 2 辺	最短である

反例：$120^\circ$ の条件を満たすが最短でない網（長方形）

横 $\dfrac32$、縦 $1$ の長方形 $A(0,0)$、$B\left(\dfrac32,0\right)$、$C\left(\dfrac32,1\right)$、$D(0,1)$ で、ex-stn-start の (3) と同じ形の網を 2 通り作る。
(1) 横向き：分岐点 $S_1\left(\dfrac{\sqrt3}6,\dfrac12\right)$ を $A$、$D$ に、$S_2\left(\dfrac32-\dfrac{\sqrt3}6,\dfrac12\right)$ を $B$、$C$ に結び、$S_1S_2$ を結ぶ。長さは $\dfrac32+\sqrt3\approx3.232$ である。

(1) の長さの計算を開く

4 本の短い辺はどれも $\sqrt{\dfrac1{12}+\dfrac14}=\dfrac{\sqrt3}3$、真ん中の辺は $\dfrac32-\dfrac{\sqrt3}3$ で、長さは $\dfrac{4\sqrt3}3+\dfrac32-\dfrac{\sqrt3}3=\dfrac32+\sqrt3$ である（ex-stn-start の (3) と同じ計算）。

(2) 縦向き：分岐点 $T_1\left(\dfrac34,\dfrac{\sqrt3}4\right)$ を $A$、$B$ に、$T_2\left(\dfrac34,1-\dfrac{\sqrt3}4\right)$ を $C$、$D$ に結び、$T_1T_2$ を結ぶ。4 本の短い辺はどれも $\sqrt{\dfrac9{16}+\dfrac3{16}}=\dfrac{\sqrt3}2$、真ん中の辺は $1-\dfrac{\sqrt3}2\approx0.134$ で、長さは $2\sqrt3+1-\dfrac{\sqrt3}2=1+\dfrac{3\sqrt3}2\approx3.598$ である。
どちらの網でも、分岐点の次数は $3$ で、3 本は $120^\circ$ で出会い、与えられた点の次数は $1$ である。thm-stn-shape の (1)〜(4) の条件をすべて満たす。しかし (2) は (1) より長いので最短ではない。外した条件：最短であること（角の条件だけにする）。成り立たなくなること：条件を満たす網が最短であること。thm-stn-shape は最短であるための必要条件で、十分条件ではない。

横 3/2、縦 1 の長方形で、真ん中の辺を横向きにした網。長さは 3/2+√3≈3.232

同じ長方形で、真ん中の辺を縦向きにした網。120° の条件を満たすが、長さは 1+3√3/2≈3.598 で長い

反例：正六角形の対称な網

1 辺 $1$ の正六角形の頂点を $V_k=\left(\cos60^\circ k,\ \sin60^\circ k\right)$（$k=0,1,\dots,5$）とする。となり合う 2 頂点 $V_0$、$V_1$ の組、$V_2$、$V_3$ の組、$V_4$、$V_5$ の組ごとに分岐点を 1 つ置き、3 つの分岐点を中心 $O$ で結ぶ。分岐点は、中心から距離 $\dfrac{\sqrt3}3$、向き $30^\circ$、$150^\circ$、$270^\circ$ の点である。
分岐点から 2 頂点への辺はどれも $\dfrac{\sqrt3}3$、分岐点から $O$ への辺も $\dfrac{\sqrt3}3$ で、辺は $6+3=9$ 本、長さは $9\cdot\dfrac{\sqrt3}3=3\sqrt3\approx5.196$ である。どの分岐点でも（$O$ も分岐点）3 本の辺は $120^\circ$ で出会う。それでも、最小全域木（5 辺をたどる網）の長さ $5$ より長い。外した条件：最短であること。成り立たなくなること：分岐点を置いた網が最小全域木より短いこと。

分岐点の位置と $120^\circ$ の確かめを開く

$V_0(1,0)$、$V_1\left(\dfrac12,\dfrac{\sqrt3}2\right)$ の中点は、中心から距離 $\dfrac{\sqrt3}2$、向き $30^\circ$ にある。分岐点 $S$ を、この向きで中心から距離 $r$ の点とすると、$V_0$、$V_1$ は $S$ から見て、中点までの距離 $\dfrac{\sqrt3}2-r$ と半分の辺 $\dfrac12$ の直角三角形の向きにある。$\angle V_0SV_1=120^\circ$ となるのは $\tan60^\circ=\dfrac{1/2}{\sqrt3/2-r}$、つまり $\dfrac{\sqrt3}2-r=\dfrac1{2\sqrt3}=\dfrac{\sqrt3}6$ のときで、$r=\dfrac{\sqrt3}3$ である。$SV_0=\sqrt{\left(\dfrac{\sqrt3}6\right)^2+\left(\dfrac12\right)^2}=\sqrt{\dfrac1{12}+\dfrac14}=\dfrac{\sqrt3}3$ である。$S$ から $O$ への向きは $V_0$、$V_1$ への向きのちょうど反対側の真ん中なので、残りの 2 つの角も $\dfrac{360^\circ-120^\circ}2=120^\circ$ である。$O$ では 3 本が $30^\circ$、$150^\circ$、$270^\circ$ の向きで、$120^\circ$ ずつである。

正六角形の最小全域木（左、長さ 5）と、120° の条件を満たす対称な網（右、長さ 3√3≈5.196）

反例：与えられた点での角が $120^\circ$ 未満

$A(0,0)$、$B(1,0)$、$D(0,1)$（$A$ の角が直角の直角二等辺三角形）で、2 辺 $AB$、$AD$ の網（最小全域木、長さ $2$）は、与えられた点 $A$ で 2 本が $90^\circ$ をなし、thm-stn-shape の (2) に反する。実際、3 点の Fermat 点 $F\left(\dfrac{3-\sqrt3}6,\dfrac{3-\sqrt3}6\right)\approx(0.211,0.211)$ を分岐点にすると、長さは
$$ FA+FB+FD=\sqrt{2+\sqrt3}=\frac{\sqrt6+\sqrt2}2\approx1.932<2 $$
になる（thm-stn-square の段 3 の $DE$ と同じ値）。外した条件：与えられた点で 2 本の辺のなす角が $120^\circ$ 以上であること。成り立たなくなること：網が最短であること。

大学数学で見る：組合せ最適化と石鹸膜

最短のネットワークを求める難しさ

thm-stn-shape により、Steiner 木は「どの与えられた点どうしを、どの分岐点を通してつなぐか」という結び方（木の形）を決めれば、あとは $120^\circ$ の条件で分岐点の位置が決まる。しかし、点の個数 $n$ が増えると結び方の数は急に増え、すべてを調べるのは現実的でない。平面の点の Steiner 木を求める問題は、計算量の理論で NP 困難 と呼ばれる種類の問題であることが知られている（GGJ77。紹介にとどめ、この記事では証明しない）。一方、最小全域木は Kruskal の方法で効率よく求められる（KT17 §12.1）。

Steiner 比を開く

最小全域木の長さに対する Steiner 木の長さの比を考える。正三角形の 3 頂点では $\dfrac{\sqrt3}2\approx0.866$ で、正方形では $\dfrac{1+\sqrt3}3\approx0.911$ である。平面のどんな点の集まりでも、この比がどこまで小さくなりうるかは、Gilbert と Pollak が論文 GP68 で問うた問題である。Steiner 木の長さは最小全域木の長さ以下なので、最小全域木は Steiner 木の長さの見積もり（上からの評価）に使える。

石鹸膜と $120^\circ$

2 枚の平行な透明な板の間に、与えられた点の位置に棒を立て、石鹸水にひたして引き上げると、棒どうしを結ぶ石鹸膜ができる。石鹸膜は表面張力によって面積をなるべく小さくしようとするので、上から見ると、長さが短い網の形になる。膜が 3 枚ずつ $120^\circ$ で出会う様子が見られる（Plateau の法則として知られる。紹介にとどめる）。ただし、石鹸膜が作るのは thm-stn-shape の条件を満たす網で、ex-stn-cx-rect のように最短でないものになることもある。

さらに先へ

3 点の場合の Steiner 木は、3 点までの距離の和を最小にする Fermat 点を分岐点にするか（角がすべて $120^\circ$ 未満のとき）、$120^\circ$ 以上の角の頂点で 2 辺を結ぶかである（Fermat点）。
最短の道を「折り返して一直線にのばす」考え方は対称点と折れ線の最短と Fagnanoの問題で使った。この記事の lem-stn-rotation は、折り返しの代わりに $60^\circ$ の回転でのばしている。
頂点・辺・次数の言葉と「次数の和は辺の数の 2 倍」は一筆書きとグラフにある。木の辺の数の数え方は、平面グラフの Euler の公式にもつながる（Eulerの多面体定理（高校数学））。
与えられた点どうしを結ぶ辺に重み（長さ）があるグラフの上で、同じ問題を考えたものは「グラフの Steiner 木問題」と呼ばれ、通信網や回路の設計で使われる。