33の素敵な数学小景
いろいろ調べていたら、マトウシェク先生の楽しげな著書が上梓されていたので、読んでみました。33の素敵な数学小景 フィボナッチ数、タイル張り、アルゴリズムを線形代数で眺めてみると… 代数を絡めた小問題の求解とか解析をコンパクトに紹介しています。代数かぁってなりました。テンソルまわりの勉強も、きちんとした方が良さそうですよね。
Extremal Combinatorics に関する話題も載っていて、げひってなりました。ドイツのワークショップに参加した時、この本（Extremal Combinatorics: With Applications in Computer Science (Texts in Theoretical Computer Science)）読んどいた方が良いよって勧められて、なるほど!! と思って、速攻で購入したのですよね。装丁が真っ赤でかっこ良かったし。で、完全にスルーですよ。駄目。ですね。
最近、凸多角形の三角形分割のフリップグラフの直径について、時間を見つけて、細々と調べていたのですけど、代数的？トポロジ的？に解析されていて、きっちり証明されているみたいです。n >12の時は、フリップグラフの直径は2n - 10に従うんですって。確かに、そうなってますもんね。ははん、代数ね。トポロジーね。事実だけ知っときゃ良いかって思っていた矢先に、マトウシェク・ショックですよ。この論文、読んどいた方が良さそうですかもね。よう分かりませんけど。
- Rotation distance, triangulations, and hyperbolic geometry (1988)
- A combinatorial method to find sharp lower bounds on flip distances (2013)
ぜんぜん、興味なかったのですけど、フリップ距離に関する研究とかって、誰もやってないと思ってたんですけど（ちょっと烏滸がまし過ぎる...）、着実にずんずん進捗してるんですね。俄然、楽しくなってきたぁぁ！25年経って出てきた論文、何があったんだぁぁああ！て思いますよね。知らんけど。で、フリップ距離のアルゴリズム、ぼけぇ〜ッて考えてて、やろうとしていることと同じような論文を読んで、上記の論文とか背景を知りました。この論文も、少し、楽しげ。
- Flipping Edge-Labelled Triangulations (2013)
編集距離のアルゴリズムを模倣したくなると、フリップ系列をある程度仮定できたら、良いかなぁって思いますよね。で、この方向性は、ボツにしました。知らんけど。
とかとか、言いつつ、Extremal Combinatorics を読む決意をしていない。よし！どうしよ。でも、今なら、俄然楽しく読めそうじゃ無いですか!? そうですね！読みましょう。読んでますか？
フェイクと現実の境界を溶解させる「SRシステム」の行方
今日、ちょっと、連絡したくなって、ググってみたのですが、思いかけず良い知らせがヒットして、確認できて、良かったです。大好きです。頑張れー。
元気そうな様子が確認できて、とっても良かったです。この記事は、意外と知られてなくて、ちょっと、あれでした。周知できて、よかった。よかった。わっはは。
Fundamentals of Parameterized complexity
Fundamentals of Parameterized Complexity (Texts in Computer Science)
さて、ちょっと、多くの方が読んでそうな書籍で、楽しげな書籍が、あれみたいです。めもめも。めもめも！
p.s. 全然関係ないけど、今日は、とても、会社がエキサイティングだったです！すごい！すごいすごい！えっと！
アルゴリズムイントロダクション
アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)
敬愛する恩師（計算幾何）の新著が上梓されたことを敬愛する恩師（グラフ・折り紙）から教えてもらいました。でかいそうです。３版は原書持ってるから良いかなって思ってましたけど、購入しようと思います。あと、学長就任、おめでとう御座います。こんなところで、こっそりと、お祝い申し上げます。３月に。
凸多角形の flip graph (3)
15頂点以上の凸多角形の flip graph を生成したり特徴を観察するために、アルゴリズムを整えて実装を見直してみました。結構、フルスクラッチ系で、だいぶ書き直しました。ちょっとだけ速くなっていて、15角形の flip graph は、2日と12時間くらいで生成できました。でも、今のままだと、16角形は難しいですね。
あと、本質的な改善点は、flip graph の頂点列挙と隣接関係生成には無いことが判りました。少なくとも、16角形の flip graph を出力する上で。15角形の場合、頂点集合 (std::vector
ちょっと、直径とかおいといて、どれくらいの時間で、グラフ構造を作ってくれるのかみてみたい気もします。lemon graph library は、知りませんでした。楽しげですね。でも、そろそろ、flip graph の生成については、どうでも良くなってきました。なので、現状の igraph 使ってる版のソースコードを GitHub で公開して、区切りたいと思います*1。
https://github.com/s-teramo/fgg
コメントの追記や、単体テストのコードの作成など、細かい修正をしないといけないので、コミットは続けますが、ソースコードは、それほど手を加えないようにします。不具合等の問題があれば、お知らせ下さい。それでは、さようならー。
*1:超絶きたないコードだし、需要があるのか判りませんが。また、数年後、何かを切っ掛けに、触れたくなるかもしれないので。
凸多角形の flip graph (2)
ちょこちょこと、いろいろ作業したので、凸多角形の flip graph についての、つづきの記事です。ソースコードは、まだ、ちょっと、色々、機能不足なので、あとで、展開したいと思っています。実際、２・３年前に実装したコードで、なんか途中で飽きちゃったので放置していたのですが、グラフ描画に俄然興味が出てきたので、再開しました。いろいろ修正したいコードがあるみたいです。GitHubとか使う機会が増えてきたので、そっちで管理することを考えてます。GitHubとかって、どうやって使うんですかね？よろしくお願いします。
- Cytoscape で分析
[
:W333]
cytoscape でググると、NetworkAnalyzer っていうプラグインが見つかります。最近のバージョンではデフォルトで組み込まれてるみたいなのですけど（あとで、最新のバージョンに移行しました）、私の環境では、２・３年前のバージョン(2.7.0)なのでインストールが必要でした。で、そのプラグインをインストールして、n = 11 の情報を出力してみました。横みたいな感じです。n = 12 は、メモリ制限1.5G とかにしても読めません。create view 実行しても、なんか、ダメだー。 バージョンを 3.0.2 にしてみたら、描けたー。以降は、3.0.2 で、スクリーンショットとか画像生成してます。
それから、それぞれの flip graph のトポロジ情報をこちらに置いてみました。gml 形式のファイルです。なんか、まだ、いろいろ、おしゃれ感が無いので、そのうち置き換えたいと思います。ともかく cytoscape で import できますよ。あと、ラベルとか属性をきちんと付与できたらいいのですが、できてません。ダメだー。
- nested network を使った各頂点への三角形分割追描画
[
:W333]あと、cytoscape で nested network をちくちく追加して、描画してみた際のスクリーンショットです。これに関しても、cytoscape が出力する cys 形式のファイルを上記のサイトに置きました。たぶん、cytoscape でファイルを開けば、横に示したような画面が表示されると思います。ご参考です。
ファイル (82KB)
これ、14頂点しか無いけど、結構めんどかったです。基本的な手順は、各三角形分割のグラフを1つずつ import して、それぞれの view に対してcircular レイアウトして、vismapper で nested network style を整えます。それから、flip graph を import して、すべての頂点番号が確認できるようレイアウトして、各頂点を右クリックして nested network→add nested network で、頂点番号と対応する番号が付与された三角形分割のグラフを対応づけます。最後に、vismapper で default style を整えつつ、レイアウトを調整します。試行錯誤で1時間くらいかかってしまった。cytoscape の使い方が良く分かっていないからかもしれませんが。あと、7角形もちょっと描こうと思っています。それから、nested network を表現できるグラフ形式など調べてみたいと思います。また、できれば、指定した２つの頂点間の任意の最短路をハイライトしてみたいので、そこら辺を調べてみたいです。
[
:W333]（追記）７角形の flip graph with nested network も描いてみました。これまでは、cytoscape 組み込みの organic っていうレイアウトで描画していましたが、ちょっと辺どうしの交差が多くて，良く分からなかったので、いろいろ試してみて、hierarchic で描画して、辺ができるだけ見やすくなる様に、マウスで頂点をぐりぐり移動してみました。でも、nested network は、７角形までで良いや、って思います。だって、直径を与えるような２頂点がなかなか見つからないんですよね。互いに辺素だから良いだろって感覚ではダメみたいです。これ、対角線増えると、直径を与えるような頂点対を全部出すのって、とても大変そうですね。やっぱり、ちょっと、直径を与える２つの三角形分割を表示してみたいですよね。
(追記) ちょっと、とても気になったので、正解を出してもらうことにしました。igraph で下に示した様に igraph_diameter 関数を実行すると、直径を与えるパスを出力してくれます。実行すると、(1 → 0 → 5 → 9 → 10 → 11) なんですって。ふむむ。わからん。
#include <igraph/igraph.h> #include <stdio.h> int main(int argc, char* argv[]) { igraph_t g; FILE* fp = fopen("07.gml", "r"); igraph_read_graph_gml(&g, fp); igraph_integer_t diameter; igraph_vector_t path; igraph_vector_init(&path, 0); igraph_diameter(&g, &diameter, NULL, NULL, &path, IGRAPH_UNDIRECTED, 0); printf("diameter: %d\n" (int) diameter); for (long int i = 0; i < igraph_vector_size(&path); i++) { printf("%d, ", (int) VECTOR(path)[i]); } printf("\n"); fclose(fp); igraph_destroy(&g); igraph_vector_destroy(&path); return 0; }
(メモ) igraph_diameter 関数の引数について。1. 対象のグラフ 2. 直径が格納される 3.始点指定無し 4. 終点指定無し 5. パスが格納される; 初期化した igraph_vector_t を指定しろって 6. 無向 7. 連結なので 0。非連結成分どうしの距離をどう測るかが選べるみたい。あと、計算量はO(|V|x|E|) なんですって。アルゴリズムの引用もどっかに記述してあると思うのですが、どこなんですかね。あとで。
[
:W333]
あと、NetworkAnalizer で確認して見ると、グラフ中の最短路の総数が1722で、そのうち 150 くらいが距離5みたいです。距離1の最短路の個数と同じくらいです。きれいな分布になってますね。でも、分布みたところで、っていう気もします。
- 何角形まで直径求められるか ＆ メモメモ
できれば、16角形までの直径なんかが調べられると良いなって思うので、備忘録的な表をメモってみました。頂点の個数は、n + 2 の Catalan 数で求められる値です。辺の個数は、頂点の個数に n - 3 を掛けて 2 で割った値です。flip graph の直径は、igraph の igraph_diameter 関数を使いました。'-' は、まだ求められてません。
| n-角形 | 頂点数 | 辺数 | 直径 | . | n-角形 | 頂点数 | 辺数 | 直径 |
|---|---|---|---|---|---|---|---|---|
| 4 | 2 | 1 | 1 | . | 11 | 4862 | 19448 | 12 |
| 5 | 5 | 5 | 2 | . | 12 | 16796 | 75582 | 15 |
| 6 | 14 | 27 | 4 | . | 13 | 58786 | 293930 | 16 |
| 7 | 42 | 84 | 5 | . | 14 | 208012 | 1144066 | 18 |
| 8 | 132 | 330 | 7 | . | 15 | 742900 | 4457400 | - |
| 9 | 429 | 1287 | 9 | . | 16 | 2674440 | 17383860 | - |
| 10 | 1430 | 5005 | 11 | . | 17 | 9694845 | 67863915 | - |
14角形の三角形分割の列挙は、２秒くらいで回答してくれました*1。やっぱり flip graph の生成が遅いです。二日経っても、まだやってます。７角形の flip graph の隣接頂点のラベルなんかを見ると結構離れているので、やっぱり隣接頂点集合を求める手続きをきちんと記述しないといけないんじゃないかと思います。あと、igraph のエッジ追加で１つずつ追加してるのも原因なのかも。ふむむ。あと、並列処理できるように、できるだけコンフリクトしない三角形分割の分類みたいなのも考えてみたいです。良く分かってませんが。ちょっと前に、図書館から 構造化並列プログラミング―効率良い計算を行うためのパターン を借りてみたけど、目次くらいしか見てないです。ダメだー。
（追記）14角形の flip graph が、二日と11時間くらいかかって、出力されました。良かったです。途中、いろいろと計算したり、グラフ描画したり、port update; port upgrade outdated で負荷をかけながらも、よくぞ、無事帰還なされた。とりあえず、15角形に向けて、実装の見直しをしましょう。
