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

hamayanhamayan's blog

競技プログラミングにおける無向グラフに関する(橋、関節点)問題まとめ

二重辺連結成分分解と橋

  • 橋とはその辺をなくすと連結でなくなる辺のこと
  • 二重辺連結成分とは橋を含まない頂点集合のこと
  • 無向グラフを二重辺連結成分に分解する よく分かる解説
  • 各成分内では、任意の3頂点を取ってきた時にa->b->cとなる辺素パス(同じ辺を2回使わない)が存在する
  • 各成分を縮約して1つの頂点とすると、無向グラフは木に変換される

二重頂点連結成分分解と関節点

  • vertex biconnected components
  • 関節点とはその頂点をなくすと連結でなくなる辺のこと
  • 二重頂点連結成分とはこの分かりやすいイメージのように成分分解すること
  • ある頂点が複数の成分に属する場合がある(関節点は複数の成分に属する)
  • 奇数長サイクルだけのグラフはcactusといい、全ての二重頂点連結成分は橋かサイクルになる 解説と問題
  • 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と言うらしい