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

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

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

定理と問題

• ラプラシアン行列の固有値0の個数は無向グラフでの連結成分の個数と同じ
  • yukicoder No.330 Eigenvalue Decomposition

• 行列木定理
  • ARC018 僕は友達が少ない 解説1 解説2
  • yukicoder No.310 2文字しりとり (激ムズ kmjpさんの解説)
  • AtCoder Paint Red and Make Graph 解説1 解説2（行列式は掃き出し法で計算できる）
  • SRM551 Div1 Hard SweetFruits 解説
  • HE Colorful Spanning Trees

• 隣接行列の行列式の偶奇とそのグラフの完全マッチングの総数の偶奇が一致する
  • ARC054 C.鯛焼き
  • Codeforces Round #382 (Div. 1) D. Permutations 解説（余因子の値は逆行列から得られる 参考）

• ケイリーの公式
  • TCO2014 Round3B Div1 Hard TreeDistance 解説1 解説2
  • CF459 Stranger Trees 解説

以下、工事中（たぶん一生工事中）

• LGV公式
  • 何も理解してない。DAG上で特殊な条件下で数え上げできるみたい。非交叉経路の個数を数える？
    • https://www.ioi-jp.org/camp/2017/2017-sp_camp-kumabe2.pdf
  • [H - Random Robots](https://atcoder.jp/contests/abc216/tasks/abc216_h)
  • [(19) ꑄ꒖ꐇꌅꏂ🐈さんはTwitterを使っています 「初めて見たLGV（writer、Laycurseさんだった気がする。解説スライドが見つからない...） https://t.co/Vy5GYol299 CFで出た回（懐かしい） https://t.co/1mBPPLor1d 応用例（むずいけど綺麗） https://t.co/PMcqVhvNYi」 / Twitter](https://twitter.com/snuke_/status/1431979034179633158)