🔄

LowLinkの紹介

2023/12/19に公開

グラフ理論

dfs

idea

2024/07/30 追記：LowLink の持つデータの項において $\text{low}(v)$ の定義に誤りがあったため修正しました。

この記事は、「木 Advent Calendar 2023」の19日目です。
きのうはまぐふらいさんの「2-SATを解く」でした。
あしたは箱さんの「木に関する数学の論文の紹介」です。

グラフの特徴量、 LowLink について紹介します。

グラフのDFS

無向グラフ上で DFS (深さ優先探索) をすると、ひとつの全域木が構築されます。これを DFS 木とよびます。
なお、有向グラフの場合は、全域森が構築されます。

DFS 木を構築したあと、グラフの辺は 4 種類に分けることができます。

木辺 (tree edge): DFS 木に属する辺
木辺以外の辺:
- 後退辺 (back edge): ひとつの DFS 木上で、子孫から先祖への辺
  - 有向グラフで後退辺が存在する場合、サイクルが存在します。
- 先行辺 (forward edge): （有向グラフの場合のみ存在）ひとつの DFS 木上で、先祖から子孫への辺
- 横断辺 (cross edge): （有向グラフの場合のみ存在）結ぶ頂点が先祖・子孫の関係にない辺

LowLink の持つデータ

LowLink は各頂点について定義される以下のふたつの値です。

$\text{ord}(v)$ : DFSで頂点 $v$ を訪れた順番（何番目か）
$\text{low}(v)$ : 木辺を $0$ 回以上、~~木辺以外の辺を $1$ 回以上通って~~後退辺を $1$ 回以下通って到達可能な頂点の $\text{ord}$ の最小値

これを持つと、以下のようなことができます。

無向グラフ
- 橋^[1]の列挙
- 関節点^[2]の列挙
- 二重辺連結成分の列挙
- 二重頂点連結成分の列挙
有向グラフ
- 強連結成分分解

LowLink の求め方

LowLink はシンプルな DFS によって求めることができます。
説明は省略します。
→実装 (Rust)

橋の列挙

辺 $(u, v)$ が $\text{ord}(u) < \text{ord}(v)$ であるとする。（そうでない場合、 $u$ と $v$ を交換する。）
このとき、 $\text{ord}(u) < \text{low}(v)$ であれば、この辺は橋。
（なぜなら、 $v$ 以降に、 $u$ 以前へ戻る後退辺があれば、 $\text{low}(v) \ge \text{ord}$ となるから。）

二重辺連結成分の列挙

橋をすべて消すと、残りはすべて二重辺連結成分になる。
あとは DFS なりで連結成分をまとめる。

関節点の列挙

頂点 $u$ が

根のとき: 子が $2$ つ以上あれば関節点
それ以外のとき: $u$ の子であって $\text{ord}(u) \le \text{low}(v)$ であるような $v$ が存在すれば関節点

二重頂点連結成分の列挙

関節点をすべて消すと、残りはすべて二重頂点連結成分になる。
あとはがんばる。

強連結成分分解

LowLink をしながら求める。
スタックを用意し、 DFS の行きがけのタイミングで訪れた頂点 push する。
DFS の帰りがけのタイミングで、 $\text{low}(v) = \text{ord}(v)$ となる場合、スタックから $v$ が消えるまですべて pop する。（pop した頂点は一つの強連結成分となる。）
強連結成分が得られる順番は、トポロジカルの逆順になる。

参考

脚注

消すと連結成分が増えるような辺 ↩︎
消すと連結成分が増えるような頂点 ↩︎