はむ。日記

離散数学とか解析学とかアニメについてつぶやきます。

最短距離の起こる回数

離散幾何

[Thm]

平面上に $n$ ( $n≧3$ )個の点が与えられたとき、最短距離は $3n - 6$ 個より多くは起こりえない。

(証明)

最短距離を $r$ とおく。

点の個数 $n$ のグラフGを次のように定める。

「Gの頂点集合を $P_{1},P_{2},...,P_{n}$ とする。また2点 $P_{i}$ , $P_{j}$ 間の距離が $r$ のときに限りそれら2点を結ぶ。この操作により得られた線分の集合をGの辺集合と定める。」

[Claim]

Gは平面グラフである。

(proof of Claim)

Gが平面グラフでないとする。

つまり2辺 $P_{i}P_{j}$ , $P_{k}P_{l}$ が点 $Q$ で交わっているとする。

三角不等式より

${ QP_{i} + QP_{k} ≧ P_{i}P_{k}}$

$QP_{j} + QP_{l} ≧ P_{j}P_{l}$ .

よって

${\displaystyle\ P_{i}P_{j} + P_{k}P_{l} ＞ P_{i}P_{k} + P_{j}P_{l}}$

つまり ${\displaystyle\ 2r ＞ P_{i}P_{k} +P_{j}P_{l}}$

これより $P_{i}P_{k}$ , $P_{j}P_{l}$ の少なくとも一方は $r$ 未満である。

これは $r$ の定義に矛盾する。■

Claimにより、Gが単純平面グラフであることがわかる。

よって

togedemaru419.hatenablog.com

↑により点の個数 $n$ の平面グラフGの辺の本数、つまり最短距離が起こる回数は $3n - 6$ 以下である。■

うまいことグラフを定義して特定の距離が起こる回数を、定義したグラフの辺数に帰着させてるところが面白いですよね。