知识卡片
图平方连接两步内可达点
有向图的平方 G² 在 u 到 v 存在至多两条边的路径时加入 u→v。
它把两步可达关系压成一条边关系;原文只定义目标,邻接表和矩阵的高效构造仍需证明。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
The square of a directed graph G = (V, E) is the graph G2 = (V, E2) such that (u, v) ∈ E2 if and only if G contains a path with at most two edges between u and v.
参考来源
- 位置:《算法导论(第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 .