前へ / 戻る / 次へ $\newcommand{\as}{^{\ast}}$

閉路とカットセットの双対性

　$G$ を連結な平面グラフ、$G\as$ をその双対グラフとし、辺の一対一対応 $e$ $\longleftrightarrow$ $e\as$ によって $G$, $G\as$ の辺の部分集合 $C$, $C\as$ が対応しているとします。 $C$ $\longleftrightarrow$ $C\as$ このとき 証明　

　正十二面体グラフ $G$ とその双対グラフである正二十面体グラフ $G\as$ の場合で例を示しながら説明します。

(1) の $\Rightarrow$ )　 $C$ がカットセットならば $G-C$ はふたつの連結成分に分かれ、 それぞれの連結成分に属する $G$ の頂点に対応する $G\as$ の面たちは、 全平面を２つに分割します （図では左側が外面を含む方です）。
すると $C\as$ は丁度その境界線に一致し、閉路になります。

(2) の $\Rightarrow$ )　 $C$ が閉路ならば、 $C$ は $G$ の面たちを２つの連結なグループに分けます。 すなわち $C$ は $G\as$ を２つの連結成分 $G\as_1$, $G\as_2$ に分けます。

すると、$C\as$ は $G\as_1$ の頂点と $G\as_2$ を頂点を結ぶ $G\as$ の辺全ての集合 と一致し、$G\as$ のカットセットになります。

(1), (2) の $\Leftarrow$ )　は $G$ と $G\as$ を逆にすると言えます。(証明終)

前へ / 戻る / 次へ