文献あり

〔位相空間論〕距離空間 part1.～グラフ理論を添えて～

~~今回から数回にわけて位相空間論の基礎について解説していきたいと思います.~~
めんどいので辞めます. (2024/6/5)
今回は「〔位相空間論〕距離空間 part1.～グラフ理論を添えて～」です. 距離空間の定義と例及びグラフ理論における距離を解説していきます.

用語

これからの位相空間論の記事では以下の記号を断りなく使うことがある.

$R$ :実数全体の集合. $Q$ :有理数全体の集合. $Z$ :整数全体の集合. $N$ :自然数全体の集合

以降適宜追加していく.

距離空間の定義と例

距離関数

$X$ を空でない集合とする. 関数 $d : X \times X \to R$ が次の3つ条件を満たすとき, 関数 $d$ を集合 $X$ 上の距離関数と呼ぶ.
任意の $x, y, z \in X$ に対して
(1) $d (x, y) \geq 0$ である. そして, $d (x, y) = 0 \Leftrightarrow x = y$ .
(2) $d (x, y) = d (y, x)$ .
(3) $d (x, z) \leq d (x, y) + d (y, z)$ .

上の3つの条件を距離の公理と呼ぶ.
条件(3)を三角不等式と呼ぶ.

距離空間

$X$ を空でない集合とし, $d$ を集合 $X$ 上の距離関数とする.
このとき, 対 $(X, d)$ を距離空間という.
$X$ の元を点と呼ぶ.

単に $X$ を距離空間と呼ぶこともある.

距離空間の例をいくつか挙げる.

ユークリッド空間

$R$ の $n$ 個の直積を $R^{n}$ と表す.
$R^{n}$ の元 $x = (x_{1}, x_{2}, \dots, x_{n})$ , $y = (y_{1}, y_{2}, \dots, y_{n})$ に対して, 関数 $d^{(n)} : R^{n} \times R^{n} \to R$ を以下のように定める.
$d^{(n)} (x, y) = \sqrt{(x_{1} - y_{1})^{2} + (x_{2} - y_{2})^{2} + \dots + (x_{n} - y_{n})^{2}}$

n

次元ユークリッド空間

先の記号のもとで,
$d^{(n)}$ をユークリッド距離といい, 対 $(R^{n}, d^{(n)})$ を $n$ 次元ユークリッド空間という.

$d^{(n)}$ は距離関数となり, $(R^{n}, d^{(n)})$ は距離空間となる.

(

d^{n}

は距離関数)

距離の公理を満たすことを示せばよい.
$x, y, z \in R^{n}$ で,
$x = (x_{1}, x_{2}, \dots, x_{n})$ , $y = (y_{1}, y_{2}, \dots, y_{n})$ , $z = (z_{1}, z_{2}, \dots, z_{n})$ と表そう.
(1)
$d^{(n)} (x, y) = \sqrt{(x_{1} - y_{1})^{2} + (x_{2} - y_{2})^{2} + \dots + (x_{n} - y_{n})^{2}}$ より $d^{(n)} (x, y) \geq 0$ であることは明らか.
$\begin{array}{rcl} d^{(n)} (x, y) = 0 & \Leftrightarrow & \sqrt{(x_{1} - y_{1})^{2} + (x_{2} - y_{2})^{2} + \dots + (x_{n} - y_{n})^{2}} = 0 \\ \Leftrightarrow & (x_{1} - y_{1})^{2} + (x_{2} - y_{2})^{2} + \dots + (x_{n} - y_{n})^{2} = 0 \\ \Leftrightarrow & x_{1} - y_{1} = 0, x_{2} - y_{2} = 0, \dots, x_{n} - y_{n} = 0 \\ \Leftrightarrow & x_{1} = y_{1}, x_{2} = y_{2}, \dots, x_{n} = y_{n} \\ \Leftrightarrow & x = y . \end{array}$
(2)
$\begin{array}{rcl} d^{(n)} (x, y) & = & \sqrt{(x_{1} - y_{1})^{2} + (x_{2} - y_{2})^{2} + \dots + (x_{n} - y_{n})^{2}} \\ = & \sqrt{(y_{1} - x_{1})^{2} + (y_{2} - x_{2})^{2} + \dots + (y_{n} - x_{n})^{2}} \\ = & d^{(n)} (y, x) . \end{array}$
(3)
$a_{i} = x_{i} - y_{i}, b_{i} = y_{i} - z_{i} (1 \leq i \leq n)$ とおく.
$a_{i} + b_{i} = x_{i} - z_{i}$ であるから,
$\begin{array}{rcl} (d^{(n)} (x, z))^{2} & = & \sum_{i = 1}^{n} (x_{i} - y_{i})^{2} \\ = & \sum_{i = 1}^{n} (a_{i} + b_{i})^{2} \\ = & \sum_{i = 1}^{n} a_{i}^{2} + \sum_{i = 1}^{n} b_{i}^{2} + 2 \sum_{i = 1}^{n} (a_{i} b_{i}) \\ \leq & \sum_{i = 1}^{n} a_{i}^{2} + \sum_{i = 1}^{n} b_{i}^{2} + 2 \sqrt{(\sum_{i = 1}^{n} a_{i}^{2}) (\sum_{i = 1}^{n} b_{i}^{2})} \\ = & {(\sqrt{\sum_{i = 1}^{n} a_{i}^{2}} + \sqrt{\sum_{i = 1}^{n} b_{i}^{2}})}^{2} \\ = & (d^{(n)} (x, y) + d^{(n)} (y, z))^{2} . \end{array}$
従って,
$d^{(n)} (x, z) \leq d^{(n)} (x, y) + d^{(n)} (y, z) .$
(1), (2), (3)より $d^{(n)}$ は距離関数であり, $R^{n}$ は空集合ではないので, $(R^{n}, d^{(n)})$ は距離空間となる.

3行目から4行目の変形では次のシュワルツの不等式を用いた.
シュワルツの不等式
任意の実数 $a_{1}, \dots, a_{n}$ , $b_{1}, \dots, b_{n}$ に対して
$(\sum_{i = 1}^{n} a_{i} b_{i})^{2} \leq (\sum_{i = 1}^{n} a_{i}^{2}) \cdot (\sum_{i = 1}^{n} b_{i}^{2})$
が成り立つ.
証明は簡単のため省略する. (右辺-左辺を計算すればそれが0以上であることがわかる.)

(3)において $a_{i} = x_{i} - y_{i}, b_{i} = y_{i} - z_{i} (1 \leq i \leq n)$ としたのはいささか技巧的に見えるかもしれないが, $d^{(n)} (x, z)$ , $d^{(n)} (x, y)$ , $d^{(n)} (y, z)$ を考えれば自然な方法であることがわかるだろう.

少し詳しく書きすぎたかもしれない. 今後はここまで詳しく書かないが自分で行間を埋めながら読んでほしい.

離散距離空間

$X$ を空でない集合とし, 関数 $d : X \times X \to R$ を次で定める.
$x, y \in X$ に対して
$d (x, y) = \begin{array}{r} {\begin{cases} 1 (x \neq y) \\ 0 (x = y) \end{cases} \end{array}$
$d$ を $X$ 上の離散距離といい対 $(X, d)$ を離散距離空間という.

離散距離空間

空でない集合 $X$ 上の離散距離 $d$ が距離関数であることを示せ.

クリックして略解をチェック

距離の公理(1)~(3)を満たすことを示せばよい.
$x, y, z \in X$ とする.
(1), (2)は明らかだろう.
(3)は $x = z$ と $x \neq z$ で場合分けすると良い.

これより, 離散距離空間は距離空間となる.

コラム:tea break

グラフと距離

tea break がtea break であるために厳密さを欠くところがありますがご了承ください. (詳しく知りたい方は, グラフ理論の本を手に取ってみると良いです. )

グラフとは, 点と点同士をつなぐ辺の集まりである.

グラフ

(単純無向)グラフとは空でない有限集合 $V$ と $E$ との組 $(V, E)$ のことである. $V$ の冪集合 $P (V)$ の部分集合のうち, 2つの元からなる集合全体のなす集合を $[V]^{2}$ で表し, $[V]^{2}$ の部分集合を $E$ とする.
$V, E$ をそれぞれ頂点集合, 辺集合と呼ぶ.
頂点集合の元を頂点, 辺集合の元を辺と呼ぶ.
$E = [V]^{2}$ のとき, グラフを完全グラフと呼ぶ.
$V, E$ からなるグラフ $G$ を $G = (V, E)$ などと書く.

$[V]^{2}$ を定義するうえで分かりやすさを重視した結果語弊を生む可能性のあるものになってしまった. よって, これを解消するためにex:graphや図を載せたこれで理解してくれると幸いである.
他の定義と異なる場合があるが, それは有向グラフであったり多重グラフであったりを考えていることがある. また, 単に今回の趣旨とは外れるため定義を簡単にしたところがある. 詳しく知りたい方は調べてみると良い.

$V = {1, 2, 3}$ とすると, その冪集合 $P (V)$ は $P (V) = {\emptyset, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}$
である. $[V]^{2}$ は
$[V]^{2} = {{1, 2}, {1, 3}, {2, 3}}$
である.
即ち, $E$ は ${{1, 2}}$ や ${{1, 2}, {1, 3}}$ や ${{1, 2}, {1, 3}, {2, 3}} = [V]^{2}$ などである.

def:graph補足

(単純無向)グラフをわかりやすく図にしよう.
例えば頂点集合 $V = {a, b, c, d}$ ,辺集合 $E = {{a, b}, {a, c}, {a, d}, {c, d}}$ のとき, グラフ $G = (V, E)$ は次のように図示できる.

即ち, グラフ $G$ の頂点を過不足なく書き, 辺に対応する線分を引く(つまり, 辺 ${a, b}$ に対して頂点 $a, b$ を繋げるように線分を引く).

グラフで距離を考える!!

さあ!この図を見たら「距離」を考えたくなるでしょう!!
グラフ理論の言葉での「距離」の定義は時期尚早である. (きちんとした定義はほかの記事で扱うことにする)
ではどのような「関数」を考えたら「距離の公理」を満たすことができるかを考察していこう.

次のグラフ $G$ を考えよう.

def:distanceを再掲しておく.

$X$ を空でない集合とする. 関数 $d : X \times X \to R$ が次の3つ条件を満たすとき, 関数 $d$ を集合 $X$ 上の距離関数と呼ぶ.
任意の $x, y, z \in X$ に対して
(1) $d (x, y) \geq 0$ である. そして, $d (x, y) = 0 \Leftrightarrow x = y$ .
(2) $d (x, y) = d (y, x)$ .
(3) $d (x, z) \leq d (x, y) + d (y, z)$ .

さて, ここでの集合 $X$ は空でない集合である必要があった.
...! 頂点集合 $V$ は定義より空でなかった!!
そこで関数 $d^{†} : V \times V \to R$ を次のように考えてみるのはどうだろうか.

(上の例を用いた説明)
頂点 $α$ と頂点 $β$ との「間」にある辺の数を「2つの頂点間の距離」 $d^{†} (α, β)$ とすると $d^{†}$ は距離の公理を満たす.

$d$ と $e$ の間にある辺の数は1なので $d^{†} (d, e) = 1$ , $c$ と $e$ の間にある辺の数は2なので $d^{†} (c, e) = 2$ である.
ふむ...これは「頂点間の離れ度合い」を表していているのかな...なら $d^{†}$ は距離関数といっても良さそう...?
Q. 本当にそうだろうか.
A. これは距離関数にはならないしそもそも関数ですらない.
$d^{†} (b, c)$ を考える. これはすぐに $d^{†} (b, c) = 1$ だと言いたくなるが実際には $d^{†} (b, c) = 2$ なども取りうることがわかる.

(違うグラフでの例も挙げた)
ここで問題になったのは, 頂点から頂点への経路が一意に定まらないので複数値が考えられることと, 同じところを繰り返すことで複数値が考えられることであった.
ではどうしたらよいだろうか...
以下の概念を用いて上で挙げた「他の例」のような状況を考えなくて済む.

道

すべての頂点が異なる経路を道という.

また, 複数の値をとることを解消するために道(経路)に含まれる辺の数(道(経路)の長さという)の最小値を考えてみる.
上の予想を改良して次の予想を立てる.

異なる2頂点 $α, β$ を結ぶ道の長さの最小値を2頂点の距離と呼び $d^{†} (α, β)$ と表せば $d^{†}$ は距離の公理を満たす.

それっぽくなってきたが $d^{†}$ は「距離の公理」を満たすのだろうか?
このままでは満たさないことは明らかである.
( $∵$ $α, β$ が同じ頂点の場合に一切触れていないから)

異なる2頂点 $α, β$ を結ぶ道の長さの最小値を2頂点の距離と呼び $d^{†} (α, β)$ と表し, $α = β$ のとき $d^{†} (α, β) = 0$ と定める.このとき $d^{†}$ は距離の公理を満たす.

def:distanceを再再掲しておく.

$X$ を空でない集合とする. 関数 $d : X \times X \to R$ が次の3つ条件を満たすとき, 関数 $d$ を集合 $X$ 上の距離関数と呼ぶ.
任意の $x, y, z \in X$ に対して
(1) $d (x, y) \geq 0$ である. そして, $d (x, y) = 0 \Leftrightarrow x = y$ .
(2) $d (x, y) = d (y, x)$ .
(3) $d (x, z) \leq d (x, y) + d (y, z)$ .

簡単な計算によって(1),(2),(3)が成り立つ...と思いきや一つ忘れていることがある.
ここでdef:graphに戻ろう.
気付いたであろうか?そう, グラフには以下のようなものも含まれるのである.

このようなグラフを連結でないグラフと呼ぶ.

この記事では便宜上, グラフの頂点間の距離を考えるときそのグラフは連結なグラフとする.
(例えば図5における $a, e$ や $e, f$ の距離を $d^{†} (a, e) = \infty$ とすることもあるがここでは扱わない)

連結なグラフ

グラフ $G$ のどの異なる2頂点を選んでもそれらを結ぶ道が存在するとき $G$ を連結なグラフであるという.

さあ, 予想の時間です.

連結なグラフ $G = (V, E)$ に対して $V$ 上の関数 $d^{†} : V \times V \to R$ を次で定めると $d^{†}$ は距離関数となる.
$α, β \in V$ とし
$(I)$ $α = β$ のとき $d^{†} (α, β) = 0$ .
$(I I)$ $α \neq β$ のとき $α, β$ を結ぶ道の長さの最小値を $l$ とすると $d^{†} (α, β) = l .$

つまり, この予想は関数 $d^{†}$ を定義したときにそれが「距離の公理」を満たすかどうかを問うている.

予想1,2(2')はうまくいかなかったが, 予想3はうまくいくだろうか.
「三度目の正直」となるか, はたまた「二度あることは三度ある」のか, 「閲覧者の顔も三度」ここらで決着をつけたい.

Q. この予想は正しいか?

A. 正しい!

では証明してみよう.
def:distanceを再再再掲しておく. (もう覚えたかな?)

$X$ を空でない集合とする. 関数 $d : X \times X \to R$ が次の3つ条件を満たすとき, 関数 $d$ を集合 $X$ 上の距離関数と呼ぶ.
任意の $x, y, z \in X$ に対して
(1) $d (x, y) \geq 0$ である. そして, $d (x, y) = 0 \Leftrightarrow x = y$ .
(2) $d (x, y) = d (y, x)$ .
(3) $d (x, z) \leq d (x, y) + d (y, z)$ .

(1),(2)は $d^{†}$ の定義から明らかであろう.
(3)
$(i)$
$x = z$ のとき
$(I)$ から $d^{†} (x, z) = 0$ , $(1)$ から $d^{†} (x, y) \geq 0, d^{†} (y, z) \geq 0$ より
$d^{†} (x, z) = 0 \leq d^{†} (x, y) + d^{†} (y, z) .$
$(ii)$
$x \neq z$ のとき
$(a)$ $x = y$ のとき
$d^{†} (x, z) = d^{†} (x, x) + d^{†} (x, z) = d^{†} (x, y) + d^{†} (y, z) .$
$(b)$ $y = z$ のとき
$d^{†} (x, z) = d^{†} (x, z) + d^{†} (z, z) = d^{†} (x, y) + d^{†} (y, z) .$
$(c)$ $x \neq y, y \neq z$ のとき
定義より
長さ $d^{†} (x, y)$ の道と, 長さ $d^{†} (y, z)$ の道が存在して, それらの道をつなぎ合わせることで長さ $d^{†} (x, y) + d^{†} (y, z)$ の $x$ と $z$ の経路を作れる.
$x$ と $z$ の経路は $x$ と $z$ の道を含むので
$d^{†} (x, z) \leq d^{†} (x, y) + d^{†} (y, z) .$
以上より, $d^{†}$ は距離の公理を満たし $V$ 上の距離関数となる.

終わりに

tea break が以外にも長くなったため今回はここで終わろうと思う.
~~次回は距離空間の開集合や近傍, 連続について扱う.~~
~~次々回で扱う位相空間の先駆けとして理解を確かなものにして欲しい.~~

参考文献

[1]

内田伏一, 集合と位相, 数学シリーズ, 裳華房

[2]

和久井道久, 代数トポロジーの基礎　基本群とホモロジー群, 近代科学社

[3]

阿原一志, 計算で身につくトポロジー, 共立出版

[4]

オノコウスケ, 「連結、グラフ距離、組み合わせグラフ、同型なグラフ」【幾何学の基礎シリーズ】グラフ理論編その3, 数理科学修士卒３人が書く数理ブログ小野研究室, 閲覧日 2024年4月26日, https://for-spring.com/geometry/graph_theory-3/

投稿日：2024年4月27日

更新日：2024年6月5日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

おはぎ

572

他の人のコメント

コメントはありません。

読み込み中

おはぎ

〔位相空間論〕距離空間 part1.～グラフ理論を添えて～

用語
距離空間の定義と例
ユークリッド空間
離散距離空間
コラム:tea break
グラフと距離
グラフで距離を考える!!
終わりに
参考文献

〔位相空間論〕 距離空間 part1.～グラフ理論を添えて～

用語

距離空間の定義と例

ユークリッド空間

離散距離空間

コラム:tea break

グラフと距離

グラフで距離を考える!!

終わりに

参考文献

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

〔位相空間論〕距離空間 part1.～グラフ理論を添えて～