📂グラフ理論

幾何的デュアルグラフ

定義 ¹

与えられた平面グラフ $G$に対して、幾何学的双対グラフ $G^{ \ast }$は以下のように作られる。

• ステップ 1.
  $G$の各フェース $f$に対応する頂点 $v^{ \ast }$を置く。
• ステップ 2.
  $G$の各エッジ $e$と重なるように対応するエッジ $e^{ \ast }$を描く。
• ステップ 3.
  元のグラフを消して、$v^{ \ast }$と$e^{ \ast }$で構成されるグラフを$G^{ \ast }$とする。

---

• 平面グラフが描かれると、平面上で区別される領域をフェースと呼ぶ。

説明

双対性^dualityは、数学や物理学全般で一般的に見られる普遍的な概念であり、関数解析学では双対空間などの形で現れる。具体的に、以下のグラフ $G$に対してその双対グラフ $G^{ \ast }$を作ってみよう:

グラフ $G$は3つのフェース $f_{1} , f_{2}, f_{3}$を持っている。各フェースに対応する3つの頂点 $v^{ \ast }$を次のように置く。

今、各 $v^{ \ast }$を繋ぐエッジ $e^{ \ast }$を引く。ただし、この時のエッジは全て元のグラフのエッジ $G$を通るように引かなければならない。

元のグラフを消せば、求めていた$G$の双対グラフ $G^{ \ast }$だけが残る。$G$が単純グラフだからといって$G^{ \ast }$も単純グラフである必要はないことに注意せよ。

一方で、双対グラフは次のような直感的な性質を持ち、特に性質[3]は、双対という概念が抽象的に拡張される可能性を示している。

基本性質

• [1]: 連結平面グラフ $G$が $n$個の頂点、$m$個のエッジ、$f$個のフェースを持ち、その幾何学的双対グラフ $G^{ \ast }$が $n^{ \ast }$個の頂点、$m^{ \ast }$個のエッジ、$f^{ \ast }$個のフェースを持つ場合、 $$n^{ \ast } = f \\ m^{ \ast } = m \\ f^{ \ast } = n$$
• [2]: $G$が連結平面グラフなら、$G^{\ast \ast}$は$G$と同型である。
• [3]: 平面グラフ $G$とその幾何学的双対グラフ $G^{ \ast }$について、$C \subset E(G)$がサイクル $\iff$ $C^{ \ast } \subset E \left( G^{ \ast } \right)$はカットセットになる

証明

[3]

$(\Rightarrow)$

$G$のサイクル $C$は少なくとも一つのフェースを囲んでいるので、これらのフェースに対応する$G^{ \ast }$の頂点集合 $S \ne \emptyset$が存在するだろう。$C$に対応する$C^{ \ast }$を$G^{ \ast }$から取り除くと、$G^{ \ast }$は$S$だけで構成されたグラフと$V(G) \setminus S$だけで構成された2つのサブグラフに分かれるので、$C^{ \ast }$は$G^{ \ast }$のカットセットになる。

---

$(\Leftarrow)$

実質同じなので省略する。

■