知识卡片

普通读书笔记卡 · 3644.c.2.b

分量的最轻出边是安全边

理解等级:中级

在当前森林 (V,A) 中取任一连通分量 C,连接 C 与其他分量的最轻边对 A 安全。因为以 C 的顶点集合构造的割尊重 A,能直接套用割性质。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第21章 最小生成树 · 查看原书依据

      light edge connecting C to some other component in GA, then (u, v) is safe for A. Proof The cut (VC, V – VC) respects A, and (u, v) is a light edge for this cut. Therefore, (u, v) is safe for A. ▪ Exercises 21.1-1 Let (

    参考来源

    - 位置:《算法导论(第4版)》第21章《最小生成树》(OEBPS/chapter021.xhtml,文本字符[10000,15000))。 - 结论依据:推论21.2把割性质应用于当前森林的单个连通分量。 - 原始内容:light edge connecting C to some other component in G A , then ( u , v ) is safe for A . Proof The cut ( V C , V – V C ) respects A , and ( u , v ) is a light edge for this cut. Therefore, ( u , v ) is safe for A . ▪ Exercises 21.1-1 Let (