距離空間【例題と証明】
この記事では、次の４つが「距離の公理」を満たすことを証明します。
- マンハッタン距離
- チェビシェフ距離(max)
- 離散距離
- $\dfrac{d(x,y)}{1+d(x,y)}$
証明の前に、距離空間の定義を確認しておきます。
定義
集合 $X$ に対して写像 $d:X\times X\to \R$ が定められ,
次の条件を満たすとき, $d$ は $X$ 上の距離関数 (metric function)という.
$(0)\ d(x,y)=0 \iff x=y$
$(1)\ d(x,y)\geq 0$
$(2)\ d(x,y)=d(y,x)$
$(3)\ d(x,z)\leq d(x,y)+d(y,z)$
距離関数 $d$ が定められた集合 $X$ を距離空間 (metric space)といい, $(X,d)$ で表す.
距離空間の例題
マンハッタン距離
例題
$\R^2$ の任意の2点 $x=(x_1,x_2),\ y=(y_1,y_2)$ に対して,
\[ d(x,y)=|x_1-y_1|+|x_2-y_2| \]
と定める. このとき, $d$ は $\R^2$ 上の距離関数であることを示せ.
- ▼ 証明
-
[証明]
距離関数の条件(0),(1),(2)は明らかに成り立つので, 条件(3)を示せばよい.
$z=(z_1,z_2)$ とすると, 三角不等式より,
\[ \eqalign{ d(x,z) & =|x_1-z_1|+|x_2-z_2| \\ &=|(x_1-y_1)+(y_1-z_1)| +|(x_2-y_2)+(y_2-z_2)| \\ &\leq |x_1-y_1|+ |y_1-z_1| +|x_2-y_2|+|y_2-z_2| \\ &=d(x,y)+d(y,z). }\] よって, $d$ は条件(3)を満たすので距離関数である.
この距離をマンハッタン距離という.
チェビシェフ距離
例題
$\R^n$ の任意の2点 $x=(x_1,\cdots,x_n),\ $
$y=(y_1,\cdots,y_n)$ に対して,
\[d(x,y)=\max\{|x_1-y_1|,\cdots,|x_n-y_n|\}\] と定める.
このとき, $d$ は $\R^n$ 上の距離関数であることを示せ.
- ▼ 証明
-
[証明]
距離関数の条件(0),(1),(2)は明らかに成り立つので, 条件(3)を示せばよい.
各 $i$ に対して,
\[ \eqalign{ |x_i-z_i| &\leq |x_i-y_i|+|y_i-z_i| \\ &\leq d(x,y)+d(y,z) }\] であることに注意すれば,
\[ \eqalign{ d(x,z) &=\max\{|x_1-z_1|,\cdots,|x_n-z_n|\}\\ &\leq\max\{|x_1-y_1|+|y_1-z_1|, \cdots,|x_n-y_n|+|y_n-z_n| \} \\ &\leq d(x,y)+d(y,z). }\] 従って, $d$ は条件(3)を満たすので $\R^n$ 上の距離関数である.
この距離をチェビシェフ距離という.
離散距離
例題
集合 $X$ に対して, $d:X\times X\to \R$ を
\[ d(x,y)=
\begin{cases}
1\ \ \ (x\neq y) \\
0\ \ \ (x=y)
\end{cases} \]
によって定めると, $d$ は $X$ 上の距離関数であることを示せ.
- ▼ 証明
-
[証明]
距離関数の条件(0),(1),(2)は明らかに成り立つので, 条件(3)を示せばよい.
$x,y,z\in X$ とする. $x=z$ のとき,
\[ d(x,z)=0\leq d(x,y)+d(y,z). \] $x\neq z$ のとき, $y\neq x$ または $y\neq z$ なので,
\[ d(x,z)=1\leq d(x,y)+d(y,z). \] 従って, $d$ は条件(3)を満たすので, $d$ は $X$ 上の距離関数である.
この距離を離散距離という.
集合 $X$ は離散距離によって離散空間になるので,
下記が成り立つ.
すべての集合は少なくとも１つの距離関数を持ち, 距離空間の構造を持つ.
その他
例題
$(X,d)$ を距離空間とする.
関数 $d':X \times X\to \R$ を
\[ d'(x,y)=\dfrac{d(x,y)}{1+d(x,y)} \]
と定めたとき, $d'$ は $X$ 上の距離関数になることを示せ.
- ▼ 証明
-
[証明]
距離関数の条件(0),(1),(2)は明らかに成り立つので, 条件(3)を示せばよい.
\[ a=d(x,z),\ b=d(x,y),\ c=d(y,z) \] とおくと, $a,b,c\geq 0$ かつ $a\leq b+c$ である.
$a=0$ のとき,
\[ d'(x,z)=0\leq d'(x,y)+d'(y,z). \] $a\neq 0$ のとき,
\[ \eqalign{ d'(x,z) &=\dfrac{a}{1+a}=\dfrac{1}{1+1/a} \\ &\leq \dfrac{1}{1+1/(b+c)} = \dfrac{b+c}{1+b+c}\\ &= \dfrac{b}{1+b+c}+\dfrac{c}{1+b+c} \\ &\leq \dfrac{b}{1+b}+ \dfrac{c}{1+c} \\ &=d'(x,y)+d'(y,z). }\] 従って, $d'$ は条件(3)を満たすので, $d'$ は $X$ 上の距離関数である.