lowlinkによる橋・関節点の検出
DFS木の到達時刻とlowlink値から、除去で連結性が変わる辺・頂点を特定する。
この典型を扱う単元: lowlinkで橋・関節点を特定する
検索別名: Low-Link、bridges and articulation points、橋・関節点
未知問からこの典型を見つける手掛かり
- 扱う対象
- back edge
- dfs木
- グラフ
- 辺
- 頂点
- 使う手掛かり
- 橋
- 連結成分が増え
- 関節点
- 除去すると切断
- 保つ不変量
- low
- ord
- 先祖への辺
- 到達時刻
- 求めるもの
- bridge
- critical edge
- 二辺連結成分
- 関節点
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
学習成果と学習単位
DFS木の到達時刻とlowlink値を計算し、橋と関節点の判定条件を説明できる。
lowlinkで橋・関節点を特定するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。