Bài 3. Cho đồ thị có hướng G = (V,E), đồ thị chuyển vị của G là GT = (V, ET) sao cho (u,v) thuộc ET nếu và chỉ nếu (v,u) thuộc E. Hãy tìm thuật toán xây dựng GT từ G biết:
a) G và GT được biểu diễn bằng ma trận kề
b) G và GT được biểu diễn bằng danh sách kề.
Bài 4. Cho đồ thị G = (V, E), ta gọi bình phương của một đồ thị G là đơn đồ thị G2 = (V, E2) sao cho (u, v) thuộc E2 nếu và chỉ nếu tồn tại một đỉnh w V sao cho (u, w) và (w, v) đều thuộc E. Hãy tìm thuật toán xây dựng G2 từ G biết:
a) G và G2 được biểu diễn bằng ma trận kề
b) G và G2 được biểu diễn bằng danh sách kề.
Download Chương trình
Không có nhận xét nào:
Đăng nhận xét