lowlinkアルゴリズム
注意
ほとんど自分向けなのでわかりにくいかもしれません
正直数学的厳密性にはかけた考え方ですが、アルゴリズムを理解し覚えるための「覚え方」、「考え方」と思って見ていただけると幸いです
手順
①始点を適当に決め、DFSで探索を行う
→発見されるまでにかかった手数を$cost$とする
→このとき経由した辺によって構成される木を$T$とする
→経由しなかった辺を$backEdge$とする
②探索が終了したら以下の3つの最小値をとる$v$の$minCost$を決める
- $cost(v)$
- もし頂点$t$との間に$backEdge$が存在するならば$cost(t)+1$
- 子のminCost
③各頂点$v$とその親$parent(v)$において以下のいずれかの式を満たすならば$parent(v)$は関節点である
(a) $v$または$parent(v)$が$root$のとき,その$root$が子を二つ持つならば関節点である
(b) $cost(parent(v)) < minCost(v)$
オーダー
各頂点において$cost$を計算するのは$O(1)$
$minCost$の計算においては隣接する$backEdge$を全て調べるから隣接辺$T(v)$を用いて$O(T(v))$
判定は$O(1)$であるから
$\sum_v(O(1)+0(T(v)) = O(|V|)+O(|E|)=O(|V|+|E|)$
解説
②について
$minCost$はDFSでは通らなかった経路を通った場合を含めた実質的最短コストのようなもの
DFSでは4番目に発見されたノードは$backEdge$を考慮すると実質的には2番目の頂点とほぼ同等コストと考えられる
また、親は子よりも早く発見されると期待できるため子の$minCost$も含めている
と考えると理解しやすい・・・かも・・・（数学的な厳密性はない）
この$minCost$の求め方によって**親の$minCost$は子の$minCost$以下であると保証できる**（ここ重要！！！！！）
③について
(a)について
以下左図に示したのは、ルートが子を二つ持ち、かつルートが関節点になっていない場合である。
しかし、DFSを行っていることからこのような木$T$が生成されることはなく、右図のような気が生成されるはずである（左優先探索の場合）
よってDFSによって得られた木$T$のルートについて、子が二つ存在することはルートが関節点であるための必要十分条件と言える。
(b)について
親の$minCost$は子の$minCost$以下であると保証できる（ここ重要！！！！！）
より$v$の子の実質的最短コストは$v$の実質的最短コストより大きい。
また、(b)が成立するとき$parent(v)$の発見コスト（実質的最短コストでない）よりも$v$および、$v$の子の実質的最短コストは大きくなる。
すなわち、どのように最短で$v$およびその子孫を見つけようとしても$parent(v)$を発見した後でしか発見できないことがコストの関係からわかる。
このことから$parent(v)$がなければ連結性が失われることがわかる。
逆に親のコストと子の実質的最短コストが等しい、または親のコストより子の実質的最短コストが小さい場合,その親を経由しなくても親の祖先からその子にたどり着ける経路が存在するということであり
$parent(v)$がなくても連結性は失われないことがわかる。