平面グラフ
提供: Mathpedia
定義
定義 1 (アフィン的写像)
ユークリッド空間 $\mathbb{R}^s$ からユークリッド空間 $\mathbb{R}^t$ への写像 $f$ がアフィン的であるとは、任意の点 $x,y \in \mathbb{R}^s$ と $t \in [0,1]$ について $f(tx+(1-t)y)=tf(x)+(1-t)f(y)$ が成り立つことをいう。またユークリッド空間の部分集合 $A \subset \mathbb{R}^s$ からユークリッド空間 $\mathbb{R}^t$ への写像がアフィン的であるとは、アフィン的な $\mathbb{R}^s$ から $\mathbb{R}^t$ への写像への拡張を持つことをいう。
定義 2 (折れ線)
ユークリッド空間 $\mathbb{R}^n$ 上の折れ線とは、単位区間 $[0,1]\subset \mathbb{R}$ からの連続同相写像であって、有限個の点を除いてその近傍でアフィン的であるようなもののことをいう。このとき $\{0,1\}$ の像としてとれる点を、折れ線の端点であるという。また折れ線 $S$ について $S$ の端点の集合を $e(S)$ とよぶ。
定義 3 (描画された平面グラフ)
描画された平面グラフ $(V,E)$ とは、次の性質を充たす集合の組のことを指していう:
- $E$ は $\mathbb{R}^2$ の折れ線の集合である;
- $V$ は $\mathbb{R}^2$ の部分集合である;
- $E$ の要素の端点は $V$ に含まれる;
- $E$ の要素は、その内部に $E$ のほかの要素の内部の点や $V$ の点を含まない;
- $E$ の相異なる辺であって端点集合が一致するようなものは存在しない。
定義 4 (描画された平面グラフに伴うグラフ)
描画された平面グラフ $(V,E)$ について、$(V,E)$ に伴うグラフ $(V',E')$ とは、次のようにして得られるグラフのことである:
- $V' = V$;
- $E' = \{e(S)|S \in E\}$.
定義 5 (平面グラフ)
グラフ $G$ が平面グラフであるとは、ある描画された平面グラフ $G^+$ が存在して、$G$ が $G^+$ に伴うグラフと同型になることをいう。
information
情報源
- R. Diestel. "Graph Theory". Springer (2000).
