無向グラフへの取り組み
- 二重辺連結成分分解と橋
- 橋とはその辺をなくすと連結でなくなる辺のこと
- 二重辺連結成分とは橋を含まない頂点集合のこと
- 無向グラフを二重辺連結成分に分解する よく分かる解説
- 各成分内では、任意の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の場合は、ガウスの消去法を使うことでサイクル基底の個数を更に減らすことができる
- サイクルの偶奇による分類
- dfs木
- 無向グラフをdfs順で回っていって使った辺のみで構築した木
- 後退辺をうまく使いながら処理していく
- スペクトルグラフ理論
- エルデシュガライの定理
- 木を最小パスで被覆する問題に対する解法
- 全ての辺について端点のどちらかを選択する。このときに、2つ以上の辺に選択されている頂点が存在しないようにせよ
問題
- 二重辺連結成分分解と橋
- 二重頂点連結成分分解と関節点
- サイクル基底
- dfs木
- エルデシュガライの定理
- 木を最小パスで被覆する問題に対する解法
- CSA69 Cover the Tree 解説1 解説2 （辺の重複あり）
- CSA61 Xor the Graph 解説1 解説2 解説3 （辺の重複なし）
