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

mayoko’s diary

プロコンとかいろいろ。

アルゴリズム

主にこれを参考にしました。こっち読んだほうが良いと思います(これは自分用のメモ)。
http://www.i.kyushu-u.ac.jp/~eiji/GraphCombinatorics/graph-combinatorics5.pdf

ラベルつき木の数は  n^{n-2}

証明の仕方も面白いですね。

辺ラベルが付いている根付き木を Un, ラベル付き木の数を Tn とする。
Tn をベースに Un を求める
ラベル付き木をひとつ決めるごとに, 根の決め方が n 通り, 辺のラベルの付け方が (n-1)! 通りなので, Un = n! * Tn

Un を普通に数える
辺を適当に貼っていく。
一度「u -> v」というように貼った場合, v に向かってもう一回 「w -> v」 というように辺を貼ることは許されない。それ以外は自由に辺を貼れるので, 場合の数は  U_n = \prod_{k=1}^{n-1} (nk) = n^{n-2}*n!

以上より
 T_n = U_n/n! = n^{n-2}

順序木の数はカタラン数と等しい

カタラン数は, 「原点からスタートして, +1 進むか, -1 進むかを選べる。ただし, 現座標が負になるような移動は ng なときの, valid な移動の数」でよく使われます。順序木の場合も, 「頂点を一個先に進める, 一個戻る」という動作が許されますが, 根から一個戻るという動作は許されないので, 結局カタラン数と一致します(適当)。
母関数よくわからないですが valid な括弧列も同じ理論でカタラン数に一致することが言えそうです。

行列木定理

各行,列がそれぞれ頂点に対応しており,対角成分にはその頂点の次数,非対角成分については枝がある部分に−1,ない部分に 0 を格納した |V|×|V| の正方行列をラプラシアン行列(グラフラプラシアン)と言います。で, 任意のグラフ G について, G の全域木の個数は, G に対応したラプラシアン行列 L の余因子の値に等しい。

証明書きたい