ヨーキョクデイ

多趣味で器用貧乏なブログ

マウス新調

1 年半ぶりのマウス新調。チャタリングがうざくなってきたがゆえ。今回は 2 年保証が有効であるので、ロジクールのサポートサイトで保証を要求し、何度かのメールのやりとりののち、新品が送られてきたわけ。もうちょっと長持ちしてもいいじゃんとは思うんだが、その前のマウスが長寿すぎただけか。
e10s.hateblo.jp

HDD 買った

WD の青、4TB である。5 年選手になる、前マシンからの流用 HDD が死ぬ前に交換しておこうと。10k 弱であった。

スマホ新調

愛用の Xperia Z3 Compact だが、いわゆるタッチ切れの諸症状が出てきており、使用においてストレスフルであるがゆえ、いっそ新しくしちゃえと。Galaxy S8 SC-02J である。従来機に比べて横幅がちょっと広く、縦がかなり長いので操作に慣れるのがつらそう。

久々にプロ野球観戦

およそ 1 年半ぶりの観戦。コボパーへ。2 年前に千葉に赴いたときには中止となってしまったロッテを拝んできた。今回も雨の予報であったが、ごくたまにぱらぱらと降るレベルで、支障なし。

前回と同じく先発は則本で、上等なピッチングを見せてくれたし、好調な打線がその好調ぶりを発揮し、大勝かと思いきや、最終回にリリーフが燃えに燃えたが、勝ちは勝ち。

領域を 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| ということ。

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

たとえば、大きな島を  n 個に分けろということになった場合、その形や方角なんかを無視して、何パターンの地図が描けるかという問題。

四色問題以前

四色問題ではグラフ理論な話に持ち込むが、ここでもその技法を流用することにする。それは、それぞれの国に頂点を対応させ、隣接する国同士を辺で結ぶという操作を行うことである。たとえばこんな感じ。
f:id:electrolysis:20160725171555p:plain
黒線で囲まれた領域を赤で示したグラフに置き換える。ありがとう Inkscape

レソト

では 2 つに分ける場合を考える。ここで考えるグラフは次のようなものであろう。
f:id:electrolysis:20160725173248p:plain
2 つの領域が隣接しているのは次の場合だけか。
f:id:electrolysis:20160725173254p:plain
いや、そうではない。次のように、南アフリカの中にレソトがあるように、ある領域内に別の領域がすっぽりと含まれている場合も考えられる。包領というらしい。
f:id:electrolysis:20160725173312p:plain

これは困ったね、ということで、海(あるいは一般に周囲のどうでもいい領域)を追加してやろう。ということで、青い部分が新たに追加された。
前者のパターンについては両国が海に接している。
f:id:electrolysis:20160725175201p:plain
後者については南アフリカが海に接しているが、レソトは海に接していないということを表せる。
f:id:electrolysis:20160725175211p:plain
 n=2 の場合、この 2 パターンのみがある。

今回のまとめ

  • 国を点、国同士の隣接関係を辺としてグラフで表す
  • 海を表す点を用意し、それぞれの国の海との隣接関係も辺とする
  •  n 個の国を考える場合、1 つの海を加えて、合計  n+1 個の点が現れる