はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける無向グラフ上での特殊な数え上げ問題まとめ [スペクトルグラフ理論, 行列木定理, ケイリーの公式]

無向グラフ上で特殊な数え上げをする場合に使えるテク集

  • スペクトルグラフ理論
    • 無向グラフをあるルールで行列に変換したものを使って色んな問題を解決する 参考1 参考2
    • ラプラシアン行列の固有値0の個数は無向グラフでの連結成分の個数と同じ 解説
    • 行列木定理(ラプラシアン行列の任意の余因子は無向グラフの全域木の個数と等しい) 解説
    • 隣接行列の行列式の偶奇とそのグラフの完全マッチングの総数の偶奇が一致する 解説
  • ケイリーの公式 参考
    • n頂点のラベル付きの木の総数はn^(n-2)通りある
    • ラベル付きなので、木の形の組合せと木の頂点に数を割り当てる組合せを全て考慮した組み合わせ数
    • ケイリーの定理の問題は「行列木定理+多項式補間」の組合せでも解けるっぽい(かなり不確定)(HEのColorful Spanning Treesはこの組合せなのでケイリーの定理っぽくやっても解ける?)(Stranger Treesには「行列木定理+多項式補間」解法が存在する)

定理と問題