Square of a directed graph
Yes, this will be a home work (I am self-learning not for university) question but I am not asking for solution. Instead, I am hoping to clarify the question itself.
In CLRS 3rd edition, page 593, excise 22.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. Describe efficient algorithms for comput- ing G2 from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
However, in CLRS 2nd edition (I can't find the book link any more), page 530, the same excise but with slightly different description:
The square of a directed graph G = (V, E) is the graph G^2 = (V, E^2) such that (u,w) ∈ E^2 if and only if for some v ∈ V, both (u,v) ∈ E and (v,w) ∈ E. That is, G^2 contains an edge between u and w whenever G contains a path with exactly two edges between u and w. Describe efficient algorithms for comput- ing G^2 from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
For the old excise with "exactly two edges", I can understand and can solve it. for example, for adjacency-list, I just do v->neighbour->neighbour.neighbour, then add (v, neighbour.neighbour) to the new E^2.
But for the new excise with "at most two edges", I am confused.
What does "if and only if G contains a path with at most two edges between u and v" mean?
Since one edge can meet the condition "at most two edges", if u and v has only one path which contains only one edge, should I add (u, v) to E^2?
What if u and v has a path with 2 edges, but also has another path with 3 edges, can I add (u, v) to E^2?
Yes, that's exactly what it means. E^2 should contain (u,v) iff E contains (u,v) or there is w in V , such that E contains both (u,w) and (w,v) .
In other words, E^2 according to the new definition is the union of E and E^2 according to the old definition.
Regarding to your last question: it doesn't matter what other paths between u and v exist (if they do). So, if there are two paths between u and v , one with 2 edges and one with 3 edges, then (u,v) should be in E^2 (according to both definitions).
由d（u，v）<= 2的那些顶点V'和G ^ 2的边G'定义的图G，G ^ 2的平方是G的所有那些边，其具有从V “
链接地址: http://www.djcxy.com/p/65286.html上一篇: pagerank如何以分布式方式计算？
下一篇: 有向图的正方形