Đồ thị - Hình vuông của đồ thị có hướng

Question

Có, đây sẽ là một công việc nhà (tôi tự học không phải cho đại học) câu hỏi nhưng tôi không yêu cầu giải pháp. Thay vào đó, tôi hy vọng sẽ làm sáng tỏ câu hỏi đó.

Trong CLRS 3rd edition, trang 593, tiêu thụ đặc biệt 22,1-5,

Các bậc hai của một đồ thị có hướng G = (V, E) là đồ thị G^2 = (V, E^2) như vậy (u, v) ∈ E^2 nếu và chỉ khi G chứa đường dẫn có ở tối đa hai cạnh giữa u và v. Mô tả các thuật toán hiệu quả để tính G2 từ G cho cả danh sách kề và các biểu diễn ma trận kề nhau của G. Phân tích thời gian chạy của các thuật toán của bạn.

Tuy nhiên, trong CLRS 2nd edition (Tôi không thể tìm thấy liên kết cuốn sách nữa), trang 530, thuế môn bài tương tự, nhưng với mô tả hơi khác nhau:

Các bậc hai của một đồ thị có hướng G = (V, E) là đồ thị G^2 = (V, E^2) sao cho (u, w) ∈ E^2 nếu và chỉ nếu đối với một số v ∈ V, cả hai (u, v) ∈ E và (v, w) ∈ E. Tức là, G^2 chứa một cạnh giữa u và w bất cứ khi nào G chứa đường dẫn với chính xác hai cạnh giữa u và w. Mô tả các thuật toán hiệu quả để tính toán G^2 từ G cho cả danh sách kề và các biểu diễn ma trận kề nhau của G. Phân tích thời gian chạy của các thuật toán của bạn.

Đối với phép loại cũ với "chính xác hai cạnh", tôi có thể hiểu và có thể giải quyết. ví dụ, đối với danh sách kề, tôi chỉ làm v-> neighbour-> neighbour.neighbour, sau đó thêm (v, neighbour.neighbour) vào E^2 mới.

Nhưng đối với bài thi mới với "tối đa hai cạnh", tôi bị nhầm lẫn.

"nếu và chỉ khi G chứa đường dẫn có tối đa hai cạnh giữa u và v" nghĩa là gì?

Vì một cạnh có thể đáp ứng điều kiện "tối đa hai cạnh", nếu u và v chỉ có một đường dẫn chỉ chứa một cạnh, tôi có nên thêm (u, v) vào E^2 không?

Nếu u và v có đường đi với 2 cạnh, nhưng cũng có một đường dẫn khác với 3 cạnh, tôi có thể thêm (u, v) vào E^2 không?

Answer 1

Vâng, đó chính xác là ý nghĩa của nó. E^2 nên chứa (u,v) iff E chứa (u,v) hoặc có w trong V, chẳng hạn rằng E chứa cả (u,w) và (w,v).

Nói cách khác, E^2 theo định nghĩa mới là liên kết của E và E^2 theo định nghĩa cũ.

Liên quan đến câu hỏi cuối cùng của bạn: không quan trọng những đường dẫn khác giữa u và v tồn tại (nếu có). Vì vậy, nếu có hai đường dẫn giữa u và v, một có 2 cạnh và một cạnh có 3 cạnh thì (u,v) phải ở trong E^2 (theo cả hai định nghĩa).

Answer 2

Hình vuông của biểu đồ G, G^2 được xác định bởi các đỉnh V 'mà d (u, v) < = 2 và eges G' của G^2 là tất cả các cạnh của G có cả hai end endices Từ V '