愛用の Xperia Z3 Compact だが、いわゆるタッチ切れの諸症状が出てきており、使用においてストレスフルであるがゆえ、いっそ新しくしちゃえと。Galaxy S8 SC-02J である。従来機に比べて横幅がちょっと広く、縦がかなり長いので操作に慣れるのがつらそう。
MIDI キーボード買った
Roland の A-49 という代物。評判がよさそうだったのでチョイス。諸々の活動が捗るのではなかろうか。
久々にプロ野球観戦
およそ 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$)は切断点なので、海にはなれない。
3 つの点が三角形をなすグラフはすべての点が切断点ではないので海の候補である。
つまり海となり得る点とはどういうことだってばよ
では、位数 $ 3$ の場合は 2 種類あるグラフの 6 つの点すべてを考えるべきか。いや、グラフの対称性を考える。
前者の例では端の 2 点は同一視できるし、後者の例では 3 つの点すべてを同一視できる。同一視できる点を同じ色で表すと次のようになる。
ゆえに、この場合は $ |\{\{0,1\},\{2\}\}|+|\{\{0,1,2\}\}|=3$ ゆえに代表して 3 つの点だけを根として考えれば済む。同様に、位数 $ 4$ の場合も 6 種類の 24 個の点ではなく、11 の点だけを根として考えようという話である。1 つの例を挙げると、この場合は $ \{\{0\},\{1,2\},\{3\}\}$ という点の組に分けられる。
同じ色の点は入れ替えたところで元のグラフと同じですよという話だ。そういう同値関係を考えたときの同値類を考えたことになる。群論のことはよくわからないが、別の言い方をすれば、自己同型群の軌道がどうこうということらしい。
グラフの位数ごとに同値類の総数をカウントすると、どうやら A126201 - OEIS であるらしい。とにかくこれらの数がある点の組から(代表元をとってきて)切断点でないものをピックアップしていけば、その点を海とした場合の隣接関係が定まる。
切断点を考慮すれば、位数 $ 3$ の場合は代表して次の 2 パターンを考えるということである。海とする点を水色で示した。
次の場合は水色の点は海として不適なので、ありえないパターンである。
位数 $ 4$ の先の例では、海として不適な点を排除すれば、
の 2 つが考えられる。全体では他に 6 つがある。
で、具体的な数は?
位数 | グラフの数 (A003094) | 同一視できる点の組の数 (A126201) | A126201 のうち海とできる数 |
---|---|---|---|
1 | 1 | 1 | 1 |
2 | 1 | 1 | 1 |
3 | 2 | 3 | 2 |
4 | 6 | 11 | 8 |
5 | 20 | 57 | 43 |
6 | 99 | 375 | 302 |
7 | 646 | 3398 | 2897 |
8 | 5974 | 40043 | 35673 |
9 | 71885 | 585440 | 536035 |
10 | 1052805 | 9895493 | 9200799 |
何をやってたか
- $ 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}$ の根以外の点に、海を根に割り当て、地図の隣接関係(境界線を共有する関係)を点の隣接関係として表す写像とする
というざっくりしすぎな定義のもとで、$\abs{G_n}$、$\abs{G^\prime_n}$、$ \abs{G^{\prime\prime}_n}$ を調べた。最終的に気になるのは $ \abs{M_n}$ なのだが。ネックなのは、$ f$ が全射ではあるが、単射とは限らないということだ。つまり、隣接関係は等しくても、鏡映関係の地図が書けたりする場合はそれぞれから等しいグラフが生成されるのだ。ゆえに、一般に $ \abs{M_n} \geq \abs{G^{\prime\prime}_{n+1}}$ ということ。
領域を n 個の小領域に分割する
たとえば、大きな島を $n$ 個に分けろということになった場合、その形や方角なんかを無視して、何パターンの地図が描けるかという問題。
四色問題以前
四色問題ではグラフ理論な話に持ち込むが、ここでもその技法を流用することにする。それは、それぞれの国に頂点を対応させ、隣接する国同士を辺で結ぶという操作を行うことである。たとえばこんな感じ。
黒線で囲まれた領域を赤で示したグラフに置き換える。ありがとう Inkscape。
レソト
では 2 つに分ける場合を考える。ここで考えるグラフは次のようなものであろう。
2 つの領域が隣接しているのは次の場合だけか。
いや、そうではない。次のように、南アフリカの中にレソトがあるように、ある領域内に別の領域がすっぽりと含まれている場合も考えられる。包領というらしい。
これは困ったね、ということで、海(あるいは一般に周囲のどうでもいい領域)を追加してやろう。ということで、青い部分が新たに追加された。
前者のパターンについては両国が海に接している。
後者については南アフリカが海に接しているが、レソトは海に接していないということを表せる。
$n=2$ の場合、この 2 パターンのみがある。
今回のまとめ
- 国を点、国同士の隣接関係を辺としてグラフで表す
- 海を表す点を用意し、それぞれの国の海との隣接関係も辺とする
- $n$ 個の国を考える場合、1 つの海を加えて、合計 $n+1$ 個の点が現れる
シャア専用マウス買った
3 年ぶりのマウス新調。チャタリングが気になってきたので。
今回は新機軸として、ロジクールのマウス M336 の赤をチョイスした。シャア専用とはこの色からイメージしただけである。ちょうどタイムセールで安かったので。
Logicool ロジクール Bluetooth マウス M336 レッド M336RD
- 出版社/メーカー: ロジクール
- 発売日: 2015/09/10
- メディア: Personal Computers
- この商品を含むブログを見る
PLANEX Bluetooth USBアダプター Ver.4.0+EDR/LE(省エネ設計)対応 BT-Micro4
- 出版社/メーカー: プラネックス
- 発売日: 2012/02/10
- メディア: Personal Computers
- 購入: 3人 クリック: 9回
- この商品を含むブログを見る
パソコン組んだった
先代が 5 年選手になって、それより前に買った流用パーツがあったりと寿命が近いと感じたため、先日新調した。
- CPU
- Intel / Core i5 6600 (3.3GHz)
- CPU クーラ
- ENERMAX / ETS-N30R-HE
- マザーボード
- ASRock / H170 Pro4
- SSD 1/2
- SanDisk / Extreme PRO SDSSDXPS-240G-J25 (240GB)
- HDD 1
- Western Digital / WD30EFRX (3TB)
- HDD 2
- Seagate / ST2000DM001 (2TB)(流用)
- 光学ドライブ
- パイオニア / BDR-206JBK(流用)
- メモリ
- Crucial / CT2K8G4DFD8213 (16GB)
- グラフィックボード
- なし
- ケース
- Fractal Design / Define R5
- 電源
- Seasonic / SSR-450RMS (450W)
というハードウェア構成で、OS は Windows 10 Pro 64 ビット版。新規購入分で総額 14 万弱。5 年は使える「中の上」を目指した。流用した HDD は酷使されているので、いずれ新調したい。今のところグラボはいらないかな。
SSD を初導入し、システム用ドライブと作業用ドライブと 2 台構成にしたわけで、起動の速さに感動。使用中もいい具合っぽい。