algorithm - Graph - 有向图的平方

Question

是的，这将是一个家庭作业（我是自学而不是大学）问题，但我不是在寻求解决方案。相反，我希望澄清问题本身。

在CLRS 第 3 版，第 593 页，消费税 22.1-5，

有向图 G = (V, E) 的平方是图 G ² = (V, E ² )使得 (u,v) ∈ E ²当且仅当 G 包含一条在 u 之间最多有两条边的路径和 v。描述为 G的邻接列表和邻接矩阵表示从 G计算 G ^{2的有效算法。分析算法的运行时间。}

然而，在 CLRS 第 2 版中（我再也找不到书的链接），第 530 页，同样的练习，但描述略有不同：

有向图 G = (V, E) 的平方是图 G ² = (V, E ² ) 使得 (u,w) ∈ E ²当且仅当对于某些 v ∈ V，两者 (u,v ) ∈ E 和 (v,w) ∈ E。也就是说，只要 G 包含一条在 u 和 w 之间恰好有两条边的路径，G 2 就在 u 和 w 之间包含一条^边。描述为 G的邻接列表和邻接矩阵表示从 G计算 G ^{2的有效算法。分析算法的运行时间。}

对于“正好两条边”的老练习，我能理解也能解决。例如，对于邻接列表，我只需执行 v->neighbour->neighbour.neighbour，然后将 (v, neighbour.neighbour) 添加到新的 E ²中。

但是对于“最多两个边缘”的新练习，我很困惑。

“当且仅当 G 包含一条在 u 和 v 之间最多有两条边的路径”是什么意思？

由于一条边可以满足“最多两条边”的条件，如果 u 和 v 只有一条包含一条边的路径，我应该将 (u, v) 添加到 E ²吗？

如果 u 和 v 有一条有 2 条边的路径，但也有另一条有 3 条边的路径，我可以将 (u, v) 添加到 E ²吗？

Answer 1

是的，这正是它的意思。E^2应该包含(u,v)iff Econtains (u,v)or there is win V，如同时E包含(u,w)and (w,v)。

换句话说，E^2根据新定义是E和E^2根据旧定义的并集。

u关于您的最后一个问题：之间v存在哪些其他路径（如果存在）并不重要。u因此，如果和之间有两条路径v，一条有 2 条边，一条有 3 条边，那么(u,v)应该在E^2（根据两个定义）。

Answer 2

图 G、G^2 的平方由 d(u,v)<=2 的顶点 V' 和 G^2 的 eges G' 定义为 G 的所有边，其两个端点都来自 V '