lowlinkで橋・関節点を特定する

概要

lowlinkによる橋・関節点の検出

DFS木の到達時刻とlowlink値から、除去で連結性が変わる辺・頂点を特定する。

考え方

tinとlowの更新

無向graphの各辺にIDを付け、全成分でDFS森を作る。tin[v]はvへ初めて入った時刻で、時刻は全探索を通して一つずつ増やす。low[v]は、vからDFS木を下り、その後高々一本の非木辺を通って到達できる頂点のtinの最小値とする。木を下らない場合も含み、初期値は low[v]=tin[v] である。

vの各隣接辺(v,u)を見て、vへ入った親辺のIDだけは除く。uが未訪問ならDFSし、戻った後に low[v]=min(low[v],low[u])。訪問済みなら low[v]=min(low[v],tin[u]) とする。無向DFSに異なる枝間の横断辺はなく、祖先への辺が迂回路を与える。既訪問の子孫への辺はtin[u]>tin[v]なので最小値を下げない。親頂点への別の平行辺は正しい迂回路なので飛ばさない。

橋と関節点の違い

木辺(v,u)が橋である条件は low[u]>tin[v]。u部分木からvまたはその祖先への別の辺がないので、この辺を除くと切れる。low[u]=tin[v]ならvへの別の辺で戻れて橋ではない。

非根vが関節点である条件は、DFS子uの少なくとも一つについて low[u]≥tin[v]。v自身を取り除くと、vへ戻るだけの辺も使えず、その子部分木が親側から切れる。どの子も厳密に古い祖先へ戻れれば、vを通らず全子部分木を親側へ接続できる。

DFS根には親側がないので条件が変わる。根が関節点であるのはDFS木の子が二つ以上のときだけ。子が一つなら根を消しても全残り頂点はその子部分木でつながる。子が二つなら両部分木の間に辺はない(あればDFSで同じ子へ入る)ため、根の除去で分離する。元から非連結なら各DFS根で同じ判定を行う。橋の辺ID・関節点の頂点IDを保存して、削除候補や縮約の入力へ戻す。

成立条件と計算量

各辺・頂点を定数回処理してO(V+E)時間・空間。自己loopはlowを下げず橋でもない。根の子数はgraph上の次数ではなくDFS木の子数である。橋の厳密不等号と非根関節点の広義不等号を区別する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。DFS木と後退辺を区別し、lowlinkの不変量から橋・関節点を判定する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-lowlink-critical-structure

習得する技能

  • DFS木の到達時刻とlowlink値を計算し、橋と関節点の判定条件を説明できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 状態グラフのモデリングと探索。

このUnitを直接前提とする単元: なし。

DFS木を作れることを前提に、到達時刻とlowlink値から橋・関節点を判定する。

このUnitでは扱わないもの

  • 次数条件に基づく葉の反復削除と、答えを保つgraph core・kernelへの縮約。

根拠