読者です 読者をやめる 読者になる 読者になる

ヨーキョクデイ

いろいろ雑食

領域を 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$ 個の点が現れる

シャア専用マウス買った

日常 PC

3 年ぶりのマウス新調。チャタリングが気になってきたので。
今回は新機軸として、ロジクールのマウス M336 の赤をチョイスした。シャア専用とはこの色からイメージしただけである。ちょうどタイムセールで安かったので。

今まで、マイパソコンを初めてゲットして以来サンワサプライのマウスだけをチョイスしてきたのだが、浮気したくなったのだ。また、初めての無線。しかも Bluetooth。ただ、パソコンがそれに対応していないので、プラネックスの USB の Bluetooth なそれも購入。人気商品らしいので。
PLANEX Bluetooth USBアダプター Ver.4.0+EDR/LE(省エネ設計)対応 BT-Micro4

PLANEX Bluetooth USBアダプター Ver.4.0+EDR/LE(省エネ設計)対応 BT-Micro4

ここ数年、同じ型のマウスばかり買い換えてきたので、いろいろととまどいがある。特に、ホイールの回転が非常に軽く、ちょっと触っただけで回ってしまう上、ホイールボタンが非常に重いため、まともに中クリックしようとするとホイールが回ってしまったりする。これに慣れるまでは Firefox でのブラウジングがつらいままであろう。誤算である。ただ、ホイールのチルト(これも初めて)がよい具合の軽さなので、これに中クリックを割り当てて対処している。ホイールの回転も、ホイールの脇を人差し指か中指で押さえる形で、ある程度の誤操作は避けられそう。運用でカバーということになるが、従来品よりもちょっとサイズが大きいことも含めて、自分の好きないわゆるつまみ持ちからの脱却は必至。

パソコン組んだった

PC 日常

先代が 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 台構成にしたわけで、起動の速さに感動。使用中もいい具合っぽい。

HERCULES のギタースタンドが壊れたので交換してもらった

日常 音楽



というわけで、HERCULES のギタースタンドである GS414B が壊れた。高さ調節用のプラスチック部品があるのだが、これがもげたのだ。ゴムっぽい質感の素材が劣化してねばねばしていた。

絶望とともに、急な散財の必要を悲観したが、インターネッツ上には同製品が物故割れたという報告が多数見られ、仲間の存在に多少は安堵したが、その中に、輸入代理店に問い合わせると無償で交換してもらえるという情報がちらほら。朗報だった。のりさんのブログに詳しくまとめられているので挙げておく。

ameblo.jp
ameblo.jp

さっそくモリダイラ楽器にぶしつけなメールを送った。すると、やはり無償交換という対応にしてもらうことになり、新品を入手できることになったのだ。いくつかのメールのやりとりを交わし、最初の報告から 4 日後、赤フン兄貴によってブツが送られてきた。前例のように、到着時に故障品を引き渡すという方法だった。

このように、非常に好意的な対応をしてもらったモリダイラ楽器には足を向けて寝られない。そして交換事例をインターネッツの海に広げてくれた諸兄に感謝する。

おそらく、GS414B の脚に貼られた MADE IN CHINA シールに記載されている記号が生産時期を示していると思われる。故障品の当該記号は見ていないが、今回送られてきた物には A015I と記載されており 2015 年製かもしれないと判断でき、故障していないおそらく 2011 年購入品には A011D と記載されていて、2011 年製であると読めば、これは改良型なので(上記ののりさん情報による)、同様の症状は起こらないはず。

mbed で Eject-io っぽいのを実装して、mbed な踏切を動かす

mbed

www.adventar.org

Eject Advent Calendar 2015 の 14 日目。

Eject-io とは 2 年前に登場した次世代 I/O I/F であるらしい。

この Eject-io を模したシステムを mbed LPC1768(青 mbed)で作ったわけだ。eject コマンドのようなものを自力で再実装していたら、eject 対象のデバイスも自作したいよねということになったのがきっかけ。

本家のように、USB マスストレージクラス、特に USB 接続の CD-ROM ドライブとしてふるまい、パソコンなんかに接続して eject したりできるものだ。これの実装は既存プログラムの改変だ。

この USB MSC の実装をベースに CD-ROM ドライブとしてふるまうように最低限のコマンドを実装したりいらないものを削ったりしている。ソースは見せられないよ!

このために USB の B コネクタ(メス)が必要になったので買った。

www.switch-science.com

で、この Eject-io っぽいのは 1 ビットの状態を持っていて、それは論理トレイの論理開閉状態であって、論理オープン状態であれば出力ピン(ディジタル出力)が Hi に、論理クローズ状態であれば Low となる仕様である。

eject コマンドの先には物理トレイによる運動エネルギを与えるブラックボックス(物理ドライブ)が直結するわけではなく、電気的な装置があってもいいのだ。さらにその先に今までのように任意の装置を接続すればよいというのが Eject-io の根本的なアイディアだと思う。

これが最小構成の画像。
f:id:electrolysis:20151214171235j:plain

Windows 10 が認識するとこうなる。
f:id:electrolysis:20151214180636p:plain

eject コマンドで遊ぶのは手段であって目的ではないので、これを間違えると eject おじさんが憤慨するらしい。いわゆる Before Eject まででは満足しない。

ところで、以前 mbed で作った踏切のプロトタイプがある。踏切好きが高じた結果だ。そもそもこのために mbed を買った気がする。

これは踏切警報器(警報灯と警報音発生器のセット)のような何かと遮断機ような何かからなる。警報灯は LED(ディジタル出力)、警報音はライン出力あるいはアンプ経由でスピーカ(富豪的にリアルタイムで波形を作ってアナログ出力)、遮断機は RC サーボという具合だ。これをタクトスイッチ経由でオンオフさせる仕組みだ。こだわりがいろいろとあるが、詳しく書くと長くなるのでやめる。

でだ。ここからが After Eject の話である。

このスイッチを撤去し、Eject-io っぽいのの出力によってスイッチングできれば最高ではないかと思うわけである。物理スイッチを手で押す代わりに、パソコンからコマンド一発で制御できるのだ。

この Eject-io っぽいのの出力ピンを mbed 踏切のピン変化割り込みな入力ピンに繋いで、Low -> Hi、すなわち論理トレイの論理オープンで踏切が閉まり、その逆で踏切が開くというシステムを作ってみたのがこの動画だ。

ワイヤーネットで HDD をテレビに VESA マウントする装置を作った

日常

俺が工作したくなる季節、それが冬。

テレビがそれなりに大きいのをいいことに、その裏が物置と化しており、整理が必要だったので。

まずは対象物。

テレビ
東芝 REGZA R3 32V
録画用外付け HDD
BUFFALO HD-LB2.0TU2/N(1kg くらい)

で、工事に使った金物とか。

六角ボルト
M6、長さ 12mm x2 (@15 円)
ワッシャ
M6、厚さ 1mm x2 (@5 円)
L 字金具
八幡ねじ 曲板 黒 L-60B No.61 x2 (@218 円)
ワイヤーネット
ダイソー 約 44cmx29.5cm 耐荷重 3kg くらい x1 (@108 円)
結束バンド
L=150mm W=3.6mm(100 本で 178 円)数本

という感じで 600 円程度のマウント装置を作った。

f:id:electrolysis:20151207215348j:plain

L 字金具で網をぶら下げる仕様。

テレビの仕様では、ねじ穴は 200mm x 200mm の間隔で付いていて、穴の深さは 13mm となっており、ボルトをそのまま入れるとボルトの頭部付近の部分が 2mm ほど余る感じだった。L 字金具が 2mm 厚で、ワッシャの 1mm が加わるので、ねじ部は 9mm しか入っていないと想定できる。15mm 長のボルトにすればよかったかもしれないが、VESA 規格に則れば何ら問題はないチョイスだと思う。

無線 LAN 周辺の工事で、ONU と(たぶん BBR-4HG か BBR-4MG と思われる)ルータとハブ (GS105) とその他コード類をワイヤーネットにくくりつけた一式を某所の壁に設置していった職人さんがいて、俺もこういうのやってみたい(コナミ缶)と思っていたので、このソリューションを選んだ次第。

パソコン周辺も、電源タップや LAN ハブやオーディオ I/F やらが無造作に置いてあるので、こんな感じでまとめておきたいのだが、どこに設置しようかという悩みが。パソコンケースのサイドパネルが有力候補ではあるが。