16

Yes, this will be a homework (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 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. Describe efficient algorithms for computing 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 exercise but with slightly different description:

The square of a directed graph G = (V, E) is the graph G2 = (V, E2) such that (u,w) ∈ E2 if and only if for some v ∈ V, both (u,v) ∈ E and (v,w) ∈ E. That is, G2 contains an edge between u and w whenever G contains a path with exactly two edges between u and w. Describe efficient algorithms for computing G2 from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.

For the old exercise 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 E2.

But for the new exercise 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 E2?

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 E2?

jkmartindale
  • 523
  • 2
  • 9
  • 22
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271

2 Answers2

8

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).

svick
  • 236,525
  • 50
  • 385
  • 514
  • so you mean the new excise added a little bit more trick to the old question? 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? – Jackson Tale Mar 11 '12 at 18:54
  • thanks for your addition in your answer. ok, but what is the real official definition of square of directed graph? – Jackson Tale Mar 11 '12 at 18:56
  • @JacksonTale, in math, there often are no “official” definitions, especially for concepts that are not widely used. If you read a book or a paper, you have to go by their definitions. – svick Mar 11 '12 at 18:58
-2

The square of a graph G, G^2 defined by those vertices V' for which d(u,v)<=2 and the eges G' of G^2 is all those edges of G which have both the end vertices From V'

Arun gorain
  • 1