知识卡片

普通读书笔记卡 · 3652.b

分量图收缩强连通内部边

理解等级:中级

把每个强连通分量压成一个顶点,原图两个分量间存在边时,分量图保留对应有向边。由不同分量不能双向可达,分量图必为 DAG。

这张卡片看不懂?

已有反馈 · 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 .