知识卡片

普通读书笔记卡 · 3648.e

图平方连接两步内可达点

理解等级:初级

有向图的平方 G² 在 u 到 v 存在至多两条边的路径时加入 u→v。

它把两步可达关系压成一条边关系;原文只定义目标,邻接表和矩阵的高效构造仍需证明。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[5000,10000))。 - 结论依据:练习20.1-5给出图平方的边存在条件。 - 原始内容:The square of a directed graph G = ( V , E ) is the graph G 2 = ( V , E 2 ) such that ( u , v ) ∈ E 2 if and only if G contains a path with at most two edges between u and v .