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ị
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.
Giải Chuyên đề Tin 12 Bài 2: Biểu diễn đồ thị trên máy tính - Cánh diều
Hoạt động 1 trang 57 Chuyên đề Tin học 12: 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 ?
Lời giải:
* 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ư sau: 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.
* Nhận xét tính đối xứng của mảng:
- Cập nhật ma trận: Ma trận này sau khi thêm tuyến đường mới sẽ trông như sau:
- Tính đối xứng: Tất cả các tuyến xe buýt đều là hai chiều vì ma trận 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).
Lời giải bài tập Chuyên đề Tin 12 Bài 2: Biểu diễn đồ thị trên máy tính hay, chi tiết khác: