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

hamayanhamayan's blog

競技プログラミングにおける高度なグラフ理論問題まとめ

スペクトルグラフ理論

問題化されている(のを探せた)理論

1. ラプラシアン行列の固有値0の個数は無向グラフでの連結成分の個数と同じ 解説
2. (行列木定理)ラプラシアン行列の任意の余因子は無向グラフの全域木の個数と等しい 解説
3. 隣接行列の行列式の偶奇とそのグラフの完全マッチングの総数の偶奇が一致する 解説
4. 余因子の値は逆行列から得られる 参考
5. 行列式は掃き出し法で計算できる

サイクルの偶奇による分類

  • 偶数長サイクルだけのグラフは二部グラフである
  • 奇数長サイクルだけのグラフはcactusといい、全ての二重頂点連結成分は橋かサイクルになる 解説と問題