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

hamayanhamayan's blog

競技プログラミングにおける無向グラフに関する（橋、関節点、サイクル基底、lowlink）問題まとめ

競技プログラミング

無向グラフへの取り組み

  • 二重辺連結成分分解と橋
    • 橋とはその辺をなくすと連結でなくなる辺のこと
    • 二重辺連結成分とは橋を含まない頂点集合のこと
    • 無向グラフを二重辺連結成分に分解する よく分かる解説
    • 各成分内では、任意の3頂点を取ってきた時にa->b->cとなる辺素パス（同じ辺を2回使わない）が存在する
    • 各成分を縮約して1つの頂点とすると、無向グラフは木に変換される
  • 二重頂点連結成分分解と関節点
    • vertex biconnected components
    • 関節点とはその頂点をなくすと連結でなくなる辺のこと
    • 二重頂点連結成分とはこの分かりやすいイメージのように成分分解すること
    • ある頂点が複数の成分に属する場合がある(関節点は複数の成分に属する)
    • 全ての単純サイクルが奇数長だけであるグラフは、すべての二重頂点連結成分が橋または単純サイクルをなすcactus graphになる 解説と問題
    • In a biconnected graph with n ≥ 3 points, for any three different vertices a, b, c, there is a simple path to from a to b going through c.
    • これも各成分を縮約すると、木となるが、Block-Cut Treeと言うらしい
    • lowlink(参考)を知っていると良い(lowlinkを知ってると良い問題 その2)
  • サイクル基底
    • cycle basis, 無向グラフのサイクルについての理論
    • 日本語で競プロ向けに書いてあるのはKUPC2012のKの解説
    • 無向グラフを好きなルートで回って特定の所に行く時の最適化で使える
    • dfsを1回することでサイクル基底が得られる。xorの場合は、ガウスの消去法を使うことでサイクル基底の個数を更に減らすことができる
  • サイクルの偶奇による分類
    • 偶数長サイクルだけのグラフは二部グラフである
    • 奇数長サイクルだけのグラフはcactusといい、全ての二重頂点連結成分は橋かサイクルになる 解説と問題
      • cactusグラフでは辺を共有する閉路は存在しない（つまり、閉路の全列挙が現実的な時間でできる）問題
  • dfs木
    • 無向グラフをdfs順で回っていって使った辺のみで構築した木
    • 後退辺をうまく使いながら処理していく
  • スペクトルグラフ理論
  • エルデシュガライの定理
  • 木を最小パスで被覆する問題に対する解法
    • 参考
    • 「辺の重複あり」適切に葉同士で繋ぐ
    • 「辺の重複無し」奇数次の点に適当に辺を張ってオイラー閉路作って切っていく
  • 全ての辺について端点のどちらかを選択する。このときに、2つ以上の辺に選択されている頂点が存在しないようにせよ
    • 連結成分において、（辺の数）≦（頂点の数）であればよい
    • 問題1 問題2

問題