最近また数え上げ欲が高まってきている。重い腰を上げて本棚に何冊かある数え上げの本を読もうかと考えたが、そこまでの気力がない。相変わらず、だるーん、としている。今日の気分的に、軽くググって知識を広げよう、と考えた。
やはり列挙といえば基本はグラフの列挙だろうか。書籍「グラフの数え上げ」は持っているし、OEISに数のデータがあるのも知っているが、図としては意外と見る機会がない（そもそも、普通の無向unlabeledグラフの列挙を図示しても面白味に欠けるからだろう）。個人的には、大量の数え上げには興味がなく、たかだか数100程度の数え上げを「画像で」見たいのである。それは、もともとの興味が数学的なものではなくて、パズル的なものだからである（私の頭が「数学に興味あり」モードならまた違ってくるが、今はそういうマイブープではない）。こんな感じのことを考えていて、じゃあ面白いグラフの数え上げのテーマや、その図がないか、と考えた。
少し調べてみて、下のサイトを見つけた。
[1] http://www.nakano-lab.cs.gunma-u.ac.jp/Enu/enumeration.html
群馬大学、中野研究室の3つの研究成果を紹介しているようだ。面白そうだが、古いページらしく、ところどころリンク切れしているのが残念である。
理解できた範囲でメモしておく。
１つ目は、フロアプランの列挙。
図１のようなものを列挙しているようだ。偶然だが、最近私が少し考えていた長方形の連結図形の列挙と似ている。掘り下げて調べれば今のテーマに関連する知見が得られそうである。
少し調べたところ、有料論文以外だと、下の論文を見つけることができた。
[2] https://www.jstage.jst.go.jp/article/aija/82/735/82_1389/_article/-char/en
面白そうである。後で読みたい。
２つ目は、「2連結内部極大平面グラフの列挙」とのことである（図２）。
極大平面グラフというのは、すべての面（外側の面を含む）が三角形の平面グラフであり、内部極大平面グラフというのは、外側の面だけは三角形でなくても良いものらしい。最初、三角形に限定するメリットが分からなかった。そこで、関連する知識を強化するために少し調べて、下のスライドを見つけた。
[3] http://dopal.cs.uec.ac.jp/okamotoy/lect/2017/geomcover/lect09.pdf
このスライドでは幾何的被覆問題への応用の観点から書いているようだ。極大平面グラフのイメージ図があってわかりやすい。
極大という風に呼ぶ理由は、平面グラフの間に包含関係を考えると理解ができた。そして、感覚的に、これに興味を持つ理由に納得ができた。このスライドは学生向けの講義資料らしく、わかりやすい印象なので、他の記述も見ていく。
Mengerの定理（「メンガーの定理」という発音のようだ、メンバーのスポンジで有名なKarl Menger氏）というものが紹介されている。面白そうである。
Mengerの定理は、任意のグラフに始点と終点が与えられたとき、互いに交差しない経路の数が、グラフを2つに分割するような頂点集合の最小サイズと一致する、というものだ。図４は先ほどのサイト[3]にあった説明図だが、秀逸な図で、言いたいことがよくわかる。
記事を見てきた順番のため、うっかりこの定理は平面グラフに対する定理かと思ったが、一般の無向グラフに対して成り立つらしい。
サイト[3]では、これに続いてα-分離集合、平面的分離集合定理というものを紹介している（むしろそちらが主題のようだ）。それらもざっくりと主張だけを眺めた。感覚的には、グラフを、全体のルートくらいのオーダーの数の頂点によって、同じくらいの大きさの領域に分けていくことができる、という定理のようだ。
α-分離集合は一般のグラフ、こちらは平面グラフ限定のようだ。 ここの議論をじっくり読むのもなかなか楽しそうである。が、読んでいる途中にまた別の興味がわいたので、そちらについて調べた（興味がうつろいやすい…）。
サイト[3]では、Mengerの定理の中で、内点素という言葉が出てきた。この言葉を知らなかった（または、知ったことがあったが忘れた）ため調べた。
[4] https://ja.wikipedia.org/wiki/%E9%81%93_(%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96)
Wikipediaの「道(グラフ理論)」の項目の文中に説明があった。グラフの辺をたどっていくような経路を道と呼び、複数の道が点を共有しないときに「点素」、特に、内部の点を共有しない時に「内点素」と呼ぶようだ。グラフ理論は地味に用語が多く、感覚的にわかりそうな、しかし慎重でなくてはならないものが多いので、なかなか身につかない…
ところで、関連する次の論文を見つけた。題目は「平面グラフで長さの総和最小な非交差道を求めるアルゴリズム」で、電子情報通信学会の論文である。
[5] http://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF_J/J091.pdf
PDF直リンクよりこちらの方がいいかもしれない（https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902170718305831）。
情報方面の論文であるため、数学的というより、アルゴリズム的な話のようだ。
この論文の問題提起で面白いと思うのは、一つの辺について複数回通ってもいいところと、「面」で外側と内側に分けているところである。複数回通ってもいいが交差してはいけない、というのは、単線と複線（http://h-syouyuyaki.dreamlog.jp/archives/51356708.html）を連想した（これを見たとき衝撃的だったのでよく覚えている）。
論文中の説明図（図６）も、どこかパズルっぽいイメージを感じとることができる。ペンパにするのは難しいかもしれないが、ゆるいルールで、ちょっとしたパズルにはできそうである。迷路みたいな軽めのパズルでもいいだろう。話がそれたが、論文[5]について、とりあえず1章と2章を読んだ。ここまでは特に難しいことは書いていない印象であり、ここからが面白いところだろう。…これも「後で読む」候補に加えよう。
私がインターネット上で情報を調べるときは、しばしばこのように興味が次々と移ろって収集がつかなくなる。興味のある記事をどれか一つに絞って読みたいところだが、果たして今読むべきなのはどれだろうか。結局は、あまり思考の流れを枝分かれさせず、一番最初に考えていた本筋の流れを大切にするべきなのかもしれない。
