ヨーキョクデイ

いろいろ雑食

領域を n 個の小領域に分割する・2

前回はグラフで考えようということを書いたが、では具体的にどんな特徴を持つグラフを考えればいいのか。

まず、必然的に各国は離島であったりしてはいけないし、島は海に隣接してないといけないので、連結。また、平面上の地図へのマッピング(平面への埋め込み)が可能であるから、平面的。さらに、自国同士の国境は存在しないし単純な隣接関係を考えるだけで 2 国間の国境線の数を数えるわけではないということで、ループや多重辺を含まない単純。今後は連結で平面的な単純グラフを考える。

その具体的な形とパターン数は、位数ごとに($4$ までだが)、Planar Connected Graph -- from Wolfram MathWorld に示されている。特に、パターン数は A003094 - OEIS に登録されている。ありがたいことに、それら全パターンのグラフが graph6 形式 で配布されているページがあるので有効利用。

とりあえず位数 $5$ までの全パターンを手書きしてみたが、かなりしんどいので、Sage に読み込ませてうんたらすることにした。

海は特別

$n+1$ 個の点において、海は区別して扱わなければならない。特別視する点をと呼ぶらしい。根を持つグラフを rooted graph と呼ぶらしい。日本語では根付きグラフと呼ぶのだろうが、インターネッツ上にその日本語の情報が余りにも少ないのは。

また、地図からグラフへのマッピングの定義より、

  • グラフ $G$ の点 $v_{sea}$ が海である $\Rightarrow$ $v_{sea}$ は切断点ではない

というのも、海が切断点であれば、海によって島が分断されるからである。ゆえに、海となり得る点は切断点ではない点である。たとえば、位数 $3$ のグラフにおいて、3 つの点が直線上に並んだグラフは端の 2 点(下の図の $0$ と $1$)は切断点ではないので海の候補であるが、真ん中の点(下の図の $2$)は切断点なので、海にはなれない。
f:id:electrolysis:20160801014209p:plain

3 つの点が三角形をなすグラフはすべての点が切断点ではないので海の候補である。
f:id:electrolysis:20160801014237p:plain

つまり海となり得る点とはどういうことだってばよ

では、位数 $3$ の場合は 2 種類あるグラフの 6 つの点すべてを考えるべきか。いや、グラフの対称性を考える。

前者の例では端の 2 点は同一視できるし、後者の例では 3 つの点すべてを同一視できる。同一視できる点を同じ色で表すと次のようになる。
f:id:electrolysis:20160801014259p:plain
f:id:electrolysis:20160801014305p:plain

ゆえに、この場合は $|\{\{0,1\},\{2\}\}|+|\{\{0,1,2\}\}|=3$ ゆえに代表して 3 つの点だけを根として考えれば済む。同様に、位数 $4$ の場合も 6 種類の 24 個の点ではなく、11 の点だけを根として考えようという話である。1 つの例を挙げると、この場合は $\{\{0\},\{1,2\},\{3\}\}$ という点の組に分けられる。
f:id:electrolysis:20160801014348p:plain

同じ色の点は入れ替えたところで元のグラフと同じですよという話だ。そういう同値関係を考えたときの同値類を考えたことになる。群論のことはよくわからないが、別の言い方をすれば、自己同型群の軌道がどうこうということらしい。

グラフの位数ごとに同値類の総数をカウントすると、どうやら A126201 - OEIS であるらしい。とにかくこれらの数がある点の組から(代表元をとってきて)切断点でないものをピックアップしていけば、その点を海とした場合の隣接関係が定まる。

切断点を考慮すれば、位数 $3$ の場合は代表して次の 2 パターンを考えるということである。海とする点を水色で示した。
f:id:electrolysis:20160801015206p:plainf:id:electrolysis:20160801015228p:plain
次の場合は水色の点は海として不適なので、ありえないパターンである。
f:id:electrolysis:20160801015212p:plain
位数 $4$ の先の例では、海として不適な点を排除すれば、
f:id:electrolysis:20160801015316p:plainf:id:electrolysis:20160801015325p:plain
の 2 つが考えられる。全体では他に 6 つがある。

で、具体的な数は?

位数グラフの数 (A003094)同一視できる点の組の数 (A126201)A126201 のうち海とできる数
1111
2111
3232
46118
5205743
699375302
764633982897
859744004335673
971885585440536035
10105280598954939200799

何をやってたか

  • $M_n$ を、海に囲まれた島を $n$ の(形を問わない)領域に分割した地図の描き方からなる集合とする
  • $G_n$ を、位数 $n$ の連結で平面的な単純グラフのうち非同型なものたちからなる集合とする
  • $G^\prime_n$ を $G_n$ のそれぞれの元について、同一視できない根を持たせたものたちからなる集合とする
  • $G^{\prime\prime}_n$ を $G^\prime_n$ から根が切断点であるものを除いた集合とする
  • $f:M_n \to G^{\prime\prime}_{n+1}$ を $M_n$ の各領域を $G^{\prime\prime}_{n+1}$ の根以外の点に、海を根に割り当て、地図の隣接関係(境界線を共有する関係)を点の隣接関係として表す写像とする

というざっくりしすぎな定義のもとで、$\left|G_n\right|$、$\left|G^\prime_n\right|$、$\left|G^{\prime\prime}_n\right|$ を調べた。最終的に気になるのは $\left|M_n\right|$ なのだが。ネックなのは、$f$ が全射ではあるが、単射とは限らないということだ。つまり、隣接関係は等しくても、鏡映関係の地図が書けたりする場合はそれぞれから等しいグラフが生成されるのだ。ゆえに、一般に $\left|M_n\right| \geq \left|G^{\prime\prime}_{n+1}\right|$ ということ。