Tree Metric and Ultra Metric

$\Leftarrow$を示す。
$d(x, y) + d(z, w) = d_T(x, u) + d_T(u, y) + d_T(z, u') + d_T(u', w)$
$d(x, z) + d(y, w) = d(x, w) + d(y, z) = d_T(x, u) + d_T(u, y) + d_T(z, u') + d_T(u', w) + 2 \cdot d_T(u, u')$
より、$d(x, z) + d(y, w) = d(x, w) + d(y, z) \geq d(x, y) + d(z, w)$だから4PCを満たす。また$u=u'$のとき、$d_T(u, u') = 0$より等号が成り立つ。
$\Rightarrow$を示す。
図1のような木$T$を考え、
$d_T(x, u) = \frac{d(x, y) + d(x, z) - d(y, z)}{2}$
$d_T(y, u) = \frac{d(y, x) + d(y, z) - d(x, z)}{2}$
$d_T(z, u') = \frac{d(z, w) + d(z, x) - d(x, w)}{2}$
$d_T(w, u') = \frac{d(w, z) + d(w, x) - d(x, z)}{2}$
$d_T(u, u') = \frac{d(x, z) + d(y, w) - d(x, y) - d(z, w)}{2}$
とすれば、$T$上の距離と$d$は等しくなっている。($d_T(x,u), d_T(y,u), d_T(z,u'), d_T(w,u') \geq 0$は三角不等式より、$d_T(u,u') \geq 0$は4PCの条件より成り立つ。)
例えば、
\begin{eqnarray} d_T(x, z) &=& d_T(x, u) + d_T(u, u') + d_T(u', z) \\ &=& d(x, z) + d(x, z) + d(y, w) - d(y, z) - d(x, w) \\ &=& d(x, z) \end{eqnarray}
他も同様。
また等号が成り立つ時$d_T(u,u')=0$より$u=u'$

$\Rightarrow$を示す。
木距離で表されるのだから、木$T = (V, E)$が存在して、$T$上の距離は$d$と一致している。
任意の4点$x, y, z, w \in X \subseteq V$を取る。距離は木$T$で表されているから、4点の全点対間パスからなる部分グラフを取ると一般性を失わず、補題1図1のようになっている。(必ずしも$u \neq u', u \neq x$など、とは限らない。)つまり、4PCを満たす。

$\Leftarrow$を示す。
距離空間の集合の元の数に関する帰納法で示す。
$|X| \leq 3$のときは自明である。
$|X| \geq 4$のとき、
帰納法の仮定より$|X| - 1$個の元を含む木$T = (V, E)$が存在している。
新たに頂点$v \in X$を距離$d$にあうように$T$に付け足す。
2つの場合に分ける。
(1) すべての$x, y, z \in V \cap X$について、$d_{xy,zv} = d_{xz,yv} = d_{xv,yz}$のとき。
ある$x, y, z \in V \cap X$をとり、$T$上の$xy, yz, zx$パスが誘導するグラフを考える。
$T$は木であるから、一般性を失うことなく、図2のように書ける(必ずしも $x \neq u$など、とは限らない)。

頂点$v$を$u$から$w = \frac{d(x, v) + d(y, v) - d(x, y)}{2}$の重みの辺でつなぎ新たに木$T'$を作る。$T'$が求めていた木になっていることを示す。
補題1と$w$の選び方より、$x,y,z$と$v$の間では$d$と$d_{T'}$が等しいことがわかる。
よって$x,y,z$以外の$z' \in V \cap X$について$d_{T'}(z', v) = d(z', v)$を示す。
$T$上の$xy,yz',z'x$パスが誘導するグラフを考える。一般性を失わず、図3のようになっている。

$w_z$同様に$w_{z'}$を定める。この時次の3式が成り立つ。

• $d_T(x, u) + w_z = d_T(x, u') + w_z (= d(x, v))$
• $d_T(y, u) + w_z = d_T(y, u') + w_z (= d(y, v))$
  この式を満たすには$d_T(x, u) = d_T(x, u'), d_T(y, u) = d_T(y, u')$となるしかない。よって$u = u'$つまり$z'$も$z$と同様の議論で$d(z,v) = d_{T'}(z, v)$である。

(2) (1)でないとき
ある$x, y, z \in X \cap V$が存在して、$d_{xy, zv} < d_{xz, yv} = d_{xv, yz}$となっている。$T$上の$xy, yz, zx$パスが誘導するグラフを考えると図2のようなグラフになっているとしてよい。
$u$を取り除くと$T$はいくつかの連結成分に分かれる。$z$を含む連結成分を$C_0$として、
その他の連結成分を$C_1, ... ,C_k$とする。
このとき、$\forall 1 \leq i \leq k, \forall w \in C_i$について、$d(w, v) = d_T(w, u) + \frac{d(x, v) + d(y, v) - d(x, y)}{2} $ ・・・(i)であることを示す。
これを示せば、距離の条件に$d(u, v) = \frac{d(x, v) + d(y, v) - d(x, y)}{2}$を加え$u + C_0$について同様の手続き(3点選んで$v$を挿入する適切な位置を探す)をすれば良い。$u + C_0$は$T$よりも真に頂点数が少なくなっているので、(1)のケースが起きるか、頂点数が2となる時に操作が終了する。頂点数が2となった時は2点の間の辺を距離に応じて適当に分割して新たな頂点を作り、そこから辺を伸ばして$v$を付け足せば良い。

(i)を示す。

$w$が$y$と同じ連結成分に属する時以外は図4のような位置関係にあるとして良い。($u \neq u''$とは限らないことに注意)
また真に不等号が成り立っているから$u \neq u'$である。
$x,y,z,v$と$x,y,z,w$の4PCより、
$d(x,y) + d(z,v) < d(x,z) + d(y,v) = d(x,v) + d(y,z)\ \mathrm{(ii)} $
$d(x,w) + d(y,z) \leq d(x,y) + d(w,z) = d(x,z) + d(w,y)\ \mathrm{(iii)} $
が成り立つ。
よって
\begin{eqnarray} d(x,w) + d(z,v) &<& (d(x,y) + d(w,z) - d(y,z)) + (d(x,v) + d(y,z) - d(x,y))\ \mathrm{(ii), (iii)より}\\ &=& d(x, v) + d(w, z) \end{eqnarray}
よって$x,w,z,v$の4PCを考えると、
$d(x,w) + d(z, v) < d(x, v) + d(w, z) = d(x, z) + d(w, v)$ (iv)
が成り立つ。
\begin{eqnarray} d_T(w, u) + \frac{d(x, v) + d(y, v) - d(x, y)}{2} &=& \frac{d_T(w, y) + d_T(w, z) - d_T(y, z)}{2} + \frac{d(x, v) + d(y, v) - d(x, y)}{2} \\ &=& \frac{d(w, y) + d(w, z) - d(y, z)}{2} + \frac{d(x, v) + d(y, v) - d(x, y)}{2} \\ &=& \frac{(d(x,y) + d(w,z) - d(x,z)) + d(w, z) - d(y, z)}{2} \\ && + \frac{d(x, v) + (d(x,v) + d(y,z) - d(x,z)) - d(x, y)}{2}\ \mathrm{(ii), (iii)より}\\ &=& d(x, v) + d(w, z) - d(x,z) \\ &=& d(w, v)\ \mathrm{(iv)より} \end{eqnarray}
$w$が$y$と同じ連結成分に属する時は$x,y$を入れ替えて、同様の議論をすれば良い。

異なる4点$x,y,z,w \in X$を任意に取る。
3PCを満たすから、一般性を失うことなく、$d(x,y) \leq d(x,z) = d(y,z)$・・$\mathrm{(i)}$としてよい。
$x,y,w$の3PCの条件について、2通りの場合を考える。
(1) $d(x,y) \leq d(x,w) = d(y,w)$・・$\mathrm{(1)}$のとき、
$\mathrm{(i)}, \mathrm{(1)}$より、$d(y,z) + d(x,w) = d(y,w) + d(x,z)$である。
$x,w,z$の3PCの条件より、$d(w,z) \leq \max(d(x,w), d(x,z))$である。
$d(w,z) \leq d(x,w)$のときは、$d(x,y) + d(w,z) \leq d(y,z) + d(x,w)$$\mathrm{(i)}$より
$d(w,z) \leq d(x,z)$のときは、$d(x,y) + d(w,z) \leq d(y,w) + d(x,z)$$\mathrm{(1)}$より
が成り立つ。
いずれの場合も$d(x,y) + d(w,z) \leq d(y,z) + d(x,w) = d(y,w) + d(x,z)$となり、4PCが成り立つ。
(2) $d(x,w) \leq d(x,y) = d(y,w)$・・$\mathrm{(2)}$のとき、
$\mathrm{(i)}, \mathrm{(2)}$より、$d(x,w) \leq d(x,y) \leq d(x,z)$・・$\mathrm{(ii)}$が成り立つ。
$\mathrm{(ii)}$の不等号が全て等号であるとき、$d(x,w) = d(x,z)$となる。$x,w,z$の3PCの条件より、$d(w,z) \leq d(x,w) = d(x,z)$である。このとき、$\mathrm{(i)}, \mathrm{(2)}$の等号もすべて成立し、$d(x,y) + d(w,z) \leq d(y,z) + d(x,w) = d(y,w) + d(x,z)$となり、4PCが成り立つ。
$\mathrm{(ii)}$の不等号が等号でないことがあるとき、$d(x,w) < d(x,z)$となる。$x,w,z$の3PCの条件より、$d(x,w) < d(x,z) = d(w,z)$・・$\mathrm{(iii)}$である。このとき、$\mathrm{(2)}$と合わせると、
$d(x,y) + d(w,z) = d(y,w) + d(x,z)$である。$\mathrm{(i),(2)}$より、$d(x,w)+d(y,z) \leq d(y,w) + d(x,z)$だから4PCが成立する。

$\Rightarrow$を示す。
$X$の各頂点対$x,y$を$d(x,y)$の辺重みで繋いだグラフ$G$、$M$を$G$の最小全域木とする。
Ultra Metricの性質1より、$M$上の$x,y$パスを$x=t_0,t_1,...,t_k=y$とすると、
$d(x,y) \leq \max_{0 \leq i < k} d(t_i, t_{i+1}) = \max_{0 \leq i < k} \delta_M(t_i, t_{i+1}) = \delta_M(x, y)$
また、$M$は$G$の最小全域木であることから、$\delta_M(x, y) \leq d(x, y)$である。
つまり$d(x,y) = \delta_M(x,y)$
$\Leftarrow$を示す。
$x,y,z \in X$をとり、$M$上の$xy,yz,zx$パスが誘導するグラフを考える。そのグラフ上で最大辺重みである辺を考えると、それは$xy,yz,zs$パスの少なくとも2つに属している。よって$\delta_M(x,y), \delta_M(y,z), \delta_M(z,x)$の最大値はユニークではない。つまり3PCを満たす。

$|X|$に関する帰納法で、命題5の条件に「$d_T(r, x)$は$\frac{1}{2}\max_{x,y \in X} d(x, y)$以下である。」も加えた命題を示す。

$|X| = 1$の時は自明である。$|X| > 1$の場合を示す。
Ultra Metric$(X,d)$を生成する木を$M$とする。$M$の辺で重みが最大であるような辺を$e=xy$とし、その重みを$w_e$とする。$M$から$e$を取り除くと、2つの木ができる。これを$M_1, M_2$とする。帰納法の仮定から$\delta_{M_i}$について、$T_i = (V_i, E_i)$と$r_i \in V_i$が存在して、帰納法の条件を満たす。$e$の選び方より、すべての$x \in V_i$について、$d_{T_i}(r_i, x) \leq \frac{1}{2} w_e$を満たす。よって、$T = (V_1 \cup V_2 \cup \{r\}, E_1 \cup E_2 \cup \{rr_1, rr_2\})$として、辺$rr_i$の重みをそれぞれ、$\frac{1}{2}w_e - d_{T_i}(r_i, x)$とすれば、条件を満たす。