ちょうど n 面をもつ方形描画の符号

本節では, ちょうどn面をもつ底辺つき方形描画に対して符号を定義する[53].

3,4章では, 各点の次数が高々3の底辺つき方形描画を取り扱っていたが, 本節では,

6.2. ちょうどn面をもつ方形描画の符号 83

図 6.6: ちょうど5面をもつ底辺つき方形描画の根描画R₍₅₎.

v v v

F F F

(a) (b) (c)

図 6.7: (a), (b)上向き消去可能な第1面と, (c)左向き消去可能な第1面 各点の次数は高々4の底辺つき方形描画を扱っていく. 次数が5の点を含む底辺つ き方形描画は存在しないので, 本節では,全ての底辺つき方形描画を取り扱うこと になる.

ちょうどn(≥ 2)面をもつ底辺つき方形描画からなる集合をS_nとする. S_n中の 各方形描画に符号を定義するため, Snの間に根つき木の構造を定義する.

いくつかの定義からはじめよう.

外周上の2本の垂直線分を含む面をスパン面と呼ぶ. 直感的に, スパン面は, 方 形描画の西側と東側の外面に隣接している. スパン面F の下側にある全ての面が スパン面であるならば,F を底スパン面と呼ぶ. これ以降の図では底スパン面を点 線で書きあらわす. n面をもつ底辺つき方形描画をRとする. Rの全ての面が底ス パン面であるならば, Rを, ちょうどn面の方形描画の根描画と呼び, R_(n)と書く.

例として, 図6.6にR₍₅₎を示す.

S_n中の底辺つき方形描画をR 6= R_(n)とする. 外周上の左上隅の点を含むRの 面をF とする. F をRの第1面と呼ぶ. 図中の方形描画の第1面は全て灰色で表 されている. F の右下隅の点をvとする. もし, vが南へのびる線分をもつならば, F を上向き消去可能という. 図6.7(a)と(b)に上向き消去可能な第1面の例を示す.

そうではなく(vが南へのびる線分をもたず),vが東へのびる線分をもつならば, F を左向き消去可能という. 図6.7(c)に左向き消去可能な第1面の例を示す.

84 第6章 様々な離散構造の符号

(a)

(b)

図 6.8: (a)上向き消去可能な第1面を消去, (b)左向き消去可能な面の消去

次にRの第1面を消去し, 新たに面を1つだけRに追加することを考えよう.

R 6= R_(n)であり, かつ, n ≥ 2なので, Rの第1面F は, 上向き消去可能であるか, または, 左向き消去可能であるか,のどちらかである. もしF が上向き消去可能で あるならば,上方向にF を押しつぶしてF の下方にある各面を広げ, Rの下側に底 スパン面を追加する. 図6.8(a)に例を示す. 同様に, もしF が左向き消去可能であ るならば,左方向にF を押しつぶしてF の左方にある各面を広げ, Rの下側に底ス パン面を追加する. 図6.8(b)に例を示す.

どちらの場合も,Rの面を1つだけ消去して, 新たに面を1つだけ追加するので, 得られる方形描画もS_nに含まれる. また, 得られる方形描画はS_n中のRとは別の 方形描画である.

上で示したの操作により,底辺つき方形描画RからS_n中の方形描画を得ること ができる. Rから得られる方形描画をP(R)と書くことにする. R 6=R_(n)なる全て の方形描画Rに対してP(R)を定義できることに注意しよう. このとき,RをP(R) の子描画, P(R)をRの親描画とそれぞれ呼ぶことにする.

S_n中の任意の方形描画Rが与えられたとき, 繰り返し親描画を求めることによ り,R, P(R), P(P(R)), . . .なる方形描画の列を得る. この列の最後には必ずR_(n)が 現れる. P(R)の底スパン面の個数はRよりも1つだけ多いことに注意しよう. 図 6.9に描画の列の例を示す.

これら全ての描画の列を併合したものをちょうどn面をもつ方形描画の家系木 T_nと定義する. T_nの各点はS_n中の底辺つき方形描画に対応し,各辺は,RとP(R) の間の関係に対応する. 家系木の根は必ずR_(n)である. 図6.10にT₄の例を示す.

図6.10において, 実線の辺は, 上向きに第1面を消去することを表している. 同様 に, 点線の辺は, 左向きに第1面を消去することを表している. 各辺に書かれてい