Nếu coi các địa điểm A, B, C, D trong Bảng 1 tương ứng là các đỉnh 0, 1, 2, 3 của đồ thị thì mảng hai chiều g trong Hình 1 biểu diễn đồ thị mô tả tuyến xe buýt giữa các địa điểm....

1. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN KỀ

Hoạt động 1:

Nếu coi các địa điểm A, B, C, D trong Bảng 1 tương ứng là các đỉnh 0, 1, 2, 3 của đồ thị thì mảng hai chiều g trong Hình 1 biểu diễn đồ thị mô tả tuyến xe buýt giữa các địa điểm. 

Nếu Nam bổ sung thêm thông tin có một tuyến xe buýt từ B đến D, thì mảng g biểu diễn đồ thị thay đổi như thế nào? 

Em có nhận xét gì về tính đối xứng của mảng g? 


●        Thêm Tuyến Đường: Vì B và D tương ứng với đỉnh 1 và 3, bạn sẽ thêm số ‘1’ vào vị trí (1,3) và (3,1) trong ma trận để biểu diễn tuyến đường trực tiếp giữa hai địa điểm này.

●        Cập Nhật Ma Trận: Ma trận g sau khi thêm tuyến đường mới sẽ trông như sau:

0 0 1 0

0 0 0 1

1 0 0 1

0 1 1 0

●        Tính Đối Xứng: Ma trận g có tính đối xứng qua đường chéo chính, nghĩa là nếu có tuyến đường từ đỉnh i đến đỉnh j được biểu diễn bằng số ‘1’ tại vị trí (i,j), thì cũng có tuyến đường từ đỉnh j về đỉnh i được biểu diễn bằng số ‘1’ tại vị trí (j,i). Điều này cho thấy tất cả các tuyến xe buýt đều là hai chiều.


Bình luận

Giải bài tập những môn khác