理論部門
・貪欲法が上手くいく ⇔ マトロイド
「行列のようなもの」という意味をもつマトロイドは, 有限集合Eとある三つの公理を満たすEの部分集合族Fによって(E, F)の形として定義されます. 三つの公理とは(M1): 空集合 ∈ F
(M2): AがBの部分集合, かつB∈F ならば, A∈F
(M3): Fの要素A, Bが|A| < |B|ならば, e∈ B-A が存在し, A∪{e} ∈ F とできる.
ここでFの各要素はEの部分集合になっていて, Fの各要素のことを独立集合と言ったりします. また, 独立集合のうち集合の包含関係に関して極大であるようなものを基と呼びます.
たとえば行列Aを持ってきたときにAを列ベクトルが集まったものとみなし, この列ベクトルの集合をEとし, 「線形独立である列ベクトルの集合」を独立集合とみなしたとき(E, F)はマトロイドになっています. 他にも, グラフGを持ってきたときにその辺集合をEとし, 「閉路をなさないようなEの部分集合」を独立集合とみなしたときのM=(E, F)もマトロイドとなっています. このときGの全域森(Gが連結なら全域木)はマトロイドMの基となっています.
集合Eとその部分集合Fが(M1)と(M2)を満たしており, さらにEの重み関数 w: E→R があるとします. ここで(E, F)にはFの極大な要素が存在するのでこれを基と定義します. またEの任意の部分集合Xに対して, w(X) = Σw(e) (e∈X) と定義します. このとき次の最小化問題を考えます.
min: w(X)
s.t. Xは(E,F)の基である.
この問題に対して,
「Eの要素をw(e)の値でソートし順番に付け加えて基になるようにする」という貪欲法が最適解を得るための必要十分条件が
(E, F)がマトロイドである.
というのです.
たとえばこのグラフの最小全域木問題に対するクラスカル法がこれに該当します. 他にもマッチングとかもマトロイドと絡んできて面白いのですが, 個人的には(E, F)に対する組合せ最適化問題で貪欲法がうまくいくための必要十分条件がマトロイドである, という事実が結構驚きでした. 実はこの事実はWhitneyにより「マトロイド」という単語が初めて出てくるよりもちょっと前に証明されていたようです.
・バーゼル問題
その昔, オイラーによって解かれた非常に有名な数学の問題です. 調和級数は発散しますが, 平方数の逆数を足していくとπが出てくるというのは当時高校生だった僕にとってはかなり衝撃的だった記憶があります. 一回証明をパラっと読んだくらいで全然詳しくないですが, 僕が数学にのめりこんだきっかけの一つです.・ランダム正則グラフにおける三角形の個数
ランダムグラフ理論というのはある性質を満たすグラフが存在するときに使われたのが最初でした. 具体的には「Erdős–Rényi の定理」が最も有名です.<Erdős–Rényiの定理>
任意の整数k>0 に対して, girth(最小の閉路の長さ)と染色数がkより大きいグラフが存在する.
この定理で使われたランダムグラフG(n,p)というのは, まず頂点をn個持ってきて「各頂点ペアに対して独立に確率pで辺をひくかどうか決める」ことによって生成されます. これによって生成されたランダムグラフはnとpをパラメータにもちますが, ランダムグラフの界隈ではnを無限に飛ばしたときの挙動について調べることが多いようです.
しかし, たとえばランダムな正則グラフ(各頂点の次数が等しいグラフ)を作りたいみたいなことがあるかもしれません. また, ほとんど全ての正則グラフが満たすようななにか面白い性質はないだろうか, という理論的興味があります.
Reg(n, d)で頂点数n, 次数dの正則グラフの全体を表すこととします. このときReg(n, d)の要素を一様ランダムに一つグラフをとってきたときに, そのグラフに含まれる三角形の個数は平均(d-1)^3/6のポアソン分布に従う
ということが分かっています. なんでポアソン分布が出てくるのかというと, 二項分布を近似しているからです. 一般にk角形の個数は平均(d-1)^k/2k のポアソン分布に従うようです.
「そもそもどうやって正則グラフを一様サンプリングするの？」という疑問が出てきますが実はこのサンプリング自体も研究テーマになっていて, FOCSというすごい国際会議に出てたランダム正則グラフの高速なサンプリングアルゴリズムについての論文が載っていました. 最も有名なサンプリングの方法としては「paring model」「switch」という手法があります.
・グラフ上のランダムウォークの定常分布への収束速度
グラフ上でのランダムウォークをマルコフ過程と見なし, 定常分布へどれくらいのスピードで収束していくかという議論があるのですがこれはグラフのラプラシアンの第二固有値と深く関わってくる、というものです.そもそもグラフのラプラシアンの固有値の集合のことをそのグラフのスペクトルと呼ぶらしいのですが, このスペクトルについての理論として「グラフスペクトル理論」というのが存在します. たとえばグラフ連結成分の個数はスペクトルの中の0の個数と等しい,「正規化されたラプラシアン」のスペクトルを使ってあるグラフが二部グラフであるための必要十分条件を与えることができる, などといったことがあります.
アルゴリズム部門
・xor swap
え、なんでこれだけでswapできるの！！？え！？！？？！・ワーシャルフロイド法
え、なんでこんな簡単なコードで全点対最短経路を求められるの！！？え！？！？？！
なんとなくですがワーシャルフロイド法の正当性の証明は考えるとためになるような気がします.
