📂グラフ理論

抽象的な双対グラフ

ビルドアップ

幾何的デュアルグラフの性質 [3]: 平面グラフ $G$ とその幾何的デュアルグラフ $G^{ \ast }$ において、$C \subset E(G)$ がサイクルの場合 $\iff$ $C^{ \ast } \subset E \left( G^{ \ast } \right)$ はカットセットである

抽象的なデュアルグラフは、一般のグラフに対して幾何的デュアルグラフと異なり、直感的ではなく抽象的に定義される。デュアルの性質を持てばそのグラフをデュアルグラフと呼ぶ。

定義 ¹

グラフ $G$ が与えられたとする。$E(G)$ と $E \left( G^{ \ast } \right)$ の間に以下を満たす一対一対応が存在するなら、$G^{ \ast }$ を$G$ の抽象的デュアルグラフと言う。

基礎的性質

抽象的デュアルグラフは、以下のように常識的な性質を持つ。

• [1]: $G^{ \ast }$ が$G$ の抽象的デュアルなら、$G$ は$G^{ \ast }$ の抽象的デュアルである。

説明

性質 2 はその証明にクラトフスキーの定理を使用するが、議論を強化しないため、学習者が必ずしも証明する価値はないかもしれない。しかし、そのステートメントが伝える意味は重要である。平面グラフの抽象的デュアルが存在するのは当然のことながら、どのような形のデュアルでも、元のグラフの構造を決定づけるという事実は数学的には全く自明ではない。

このような双対性の概念は、組み合わせ論のマトロイドへと繋がる。