知识卡片
分量图收缩强连通内部边
把每个强连通分量压成一个顶点,原图两个分量间存在边时,分量图保留对应有向边。由不同分量不能双向可达,分量图必为 DAG。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
, vk}, and it contains one vertex vi for each strongly connected component Ci of G. There is an edge (vi, vj) ∈ ESCC if G contains a directed edge (x, y) for some x ∈ Ci and some y ∈ Cj.
参考来源
- 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[55000,60000))。
- 结论依据:原文定义每个分量对应一个顶点及跨分量边;引理20.13排除分量间双向路径。
- 原始内容:The vertex set V SCC is { v 1 , v 2 , … , v k }, and it contains one vertex v i for each strongly connected component C i of G . There is an edge ( v i , v j ) ∈ E SCC if G contains a directed edge ( x , y ) for some x ∈ C i and some y ∈ C j .