組合せとグラフの理論（塩田）2023年度

組合せとグラフの理論（塩田）第10回 (4)　閉路とカットセットの双対性

$\newcommand{\as}{^{\ast}}$

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

$G$ を連結な平面グラフ、

$G\as$ をその双対グラフとし、辺の一対一対応

$e$

$\longleftrightarrow$

$e\as$ によって

$G$ ,

$G\as$ の辺の部分集合

$C$ ,

$C\as$ が対応しているとします。

$C$

$\longleftrightarrow$

$C\as$ このとき

Th.8　

証明　

　正十二面体グラフ $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$ を逆にすると言えます。(証明終)