Processing math: 100%

組合せとグラフの理論（塩田）第10回 (2)　双対性
前へ / 戻る / 次へ

双対性

Th.5　
  1. G が連結な平面グラフであれば G∗ もそうである。
  2. G, G∗ の頂点数、辺数、面数をそれぞれ n, n∗, m, m∗, f, f∗ とすると、
    n∗=f, m∗=m, f∗=n.
証明　(1)　G∗ が平面グラフになることは描き方よりわかります。 G∗ の連結性は「 G の面が順番にたどれる」ということです。
(2)　n∗=f であることは Def.1 (1) より。 m∗=m であることは描き方の (2) より。 すると、 G, G∗ についてオイラーの公式が成り立つことから
n−m+f=2=n∗−m∗+f∗=f−m+f∗
よって f∗=n. (証明終)

　双対グラフの双対グラフは自分自身に戻ります。
Th.6　G が連結な平面グラフであれば (G∗)∗≅G.
証明　図では双対グラフに赤色を使って述べていきます。
  1. G∗ の面 α∗ の境界辺の 1 つを e∗、 e∗ がまたいでいる G の辺を e=uv とすると、 u, v のどちらか一方は面 α∗ の中にあります。
  2. つまり G∗ の各面 α∗ には G の頂点 u が 1 つ以上あります。
  3. 2° の対応を φ:α∗↦u と表すと、 f∗=n ですから φ は一対一対応であることがわかります。
  4. 3° の対応によって φ(α∗)=u, φ(β∗)=v であるとします。 このとき、
    u と v が G で隣接していること
       ⇔  e=uv が G の辺であること
       ⇔  e∗ が α∗ と β∗ の境界であること
       ⇔  α∗ と β∗ は (G∗)∗ の頂点として隣接すること
    となるので、φ は (G∗)∗ と G の隣接関係を写し合います。(証明終)

前へ / 戻る / 次へ