組合せとグラフの理論(塩田)第10回 (2) 双対性
前へ / 戻る / 次へ
$\newcommand{\as}{^{\ast}}$
双対性
Th.5
- $G$ が連結な平面グラフであれば $G\as$ もそうである。
- $G$, $G\as$ の頂点数、辺数、面数をそれぞれ $n$, $n\as$, $m$, $m\as$, $f$, $f\as$ とすると、
$n\as = f$, $\quad m\as = m$, $\quad f\as = n$.
証明 (1) $G\as$ が平面グラフになることは
描き方よりわかります。
$G\as$ の連結性は「 $G$ の面が順番にたどれる」ということです。
(2) $n\as = f$ であることは
Def.1 (1) より。
$m\as = m$ であることは
描き方の (2) より。
すると、 $G$, $G\as$ についてオイラーの公式が成り立つことから
$n- m + f = 2 = n\as - m\as + f\as = f - m + f\as$
よって $f\as = n$. (証明終)
双対グラフの双対グラフは自分自身に戻ります。
Th.6 $G$ が連結な平面グラフであれば $(G\as)\as \cong G$.
証明 図では双対グラフに赤色を使って述べていきます。
- $G\as$ の面 $\alpha\as$ の境界辺の 1 つを $e\as$、
$e\as$ がまたいでいる $G$ の辺を $e=uv$ とすると、
$u$, $v$ のどちらか一方は面 $\alpha\as$ の中にあります。
- つまり $G\as$ の各面 $\alpha\as$ には $G$ の頂点 $u$ が 1 つ以上あります。
- 2° の対応を $\varphi:\alpha\as \mapsto u$ と表すと、
$f\as=n$ ですから $\varphi$ は一対一対応であることがわかります。
- 3° の対応によって $\varphi(\alpha\as)=u$, $\varphi(\beta\as)=v$ であるとします。
このとき、
$u$ と $v$ が $G$ で隣接していること
$\Leftrightarrow$ $\ e=uv$ が $G$ の辺であること
$\Leftrightarrow$ $\ e\as$ が $\alpha\as$ と $\beta\as$ の境界であること
$\Leftrightarrow$ $\ \alpha\as$ と $\beta\as$ は $(G\as)\as$ の頂点として隣接すること
|
となるので、$\varphi$ は $(G\as)\as$ と $G$ の隣接関係を写し合います。(証明終)