Năm 1736, nhà bác học Euler đưa ra bài toán, được gọi là bài toán 7 cây cầu

Giải Chuyên đề Tin 12 Bài 11: Khái niệm đồ thị sách - Kết nối tri thức

Khởi động trang 49 Chuyên đề Tin học 12: Năm 1736, nhà bác học Euler đưa ra bài toán, được gọi là bài toán 7 cây cầu ở Königsberg. Tại thành phố cổ Königsberg của nước Phổ cũ (nay thuộc nước Nga) có dòng sông Pregel vắt ngang qua, chia thành phố thành các vùng riêng biệt. Bài toán Euler đặt ra là làm sao đi qua tất cả 7 cây cầu này, mỗi cầu chỉ được phép đi qua đúng một lần.

Em hãy giải bài toán trên.

Có thể dùng mô hình dữ liệu nào để mô phỏng bài toán này?

Lời giải:

Bài toán 7 cây cầu ở Königsberg có thể được giải bằng một số phương pháp, trong đó một phương pháp hiệu quả là sử dụng đồ thị. Mô hình đồ thị có thể được sử dụng để mô phỏng bài toán này.

Một cách tiếp cận đơn giản là sử dụng đồ thị vô hướng, trong đó mỗi cầu được biểu diễn bởi một cạnh của đồ thị, và mỗi khu vực của thành phố được biểu diễn bởi một đỉnh. Bài toán trở thành việc tìm một đường đi qua tất cả các cầu (cạnh) một lần và quay lại nút xuất phát (đỉnh xuất phát).

Một cách khác để mô hình hóa bài toán này là sử dụng cây tìm kiếm nhị phân. Mỗi nút trong cây có thể biểu diễn một câu chuyện từ điểm xuất phát đến các cây cầu, trong đó mỗi cầu được đi qua một lần. Bằng cách này, ta có thể tìm kiếm một đường đi hợp lệ (nếu tồn tại) từ điểm xuất phát đến các cây cầu và quay lại điểm xuất phát.

Tùy thuộc vào cách tiếp cận, mô hình dữ liệu sẽ thay đổi. Đối với mô hình đồ thị, ta có thể sử dụng ma trận kề hoặc danh sách kề để biểu diễn đồ thị. Đối với mô hình cây tìm kiếm nhị phân, mỗi nút có thể lưu trữ thông tin về cầu đã đi qua và các khu vực đã được ghé thăm.

Lời giải bài tập Chuyên đề Tin 12 Bài 11: Khái niệm đồ thị sách hay, ngắn gọn khác:

• Hoạt động 1 trang 49 Chuyên đề Tin học 12: Tìm hiểu khái niệm về đồ thị: Trao đổi, thảo luận về mô hình đồ thị, các khái niệm cơ bản của đồ thị ....

• Câu hỏi 1 trang 51 Chuyên đề Tin học 12: Cây, cây nhị phân và cây tìm kiếm nhị phân có là mô hình đồ thị không? ....

• Câu hỏi 2 trang 51 Chuyên đề Tin học 12: Vẽ đồ thị vô hướng G = (V, E) sau: V = [0, 1, 2, 3, 4] ....

• Câu hỏi 3 trang 51 Chuyên đề Tin học 12: Mô tả tập hợp đỉnh V và tập hợp cạnh E của đồ thị vô hướng trong Hình 11.7 ....

• Hoạt động 2 trang 52 Chuyên đề Tin học 12: Đọc, trao đổi và thảo luận các khái niệm, định nghĩa liên quan đến đồ thị ....

• Câu hỏi 1 trang 53 Chuyên đề Tin học 12: Khi nào một đỉnh của đồ thị có bậc bằng 0? ....

• Câu hỏi 2 trang 53 Chuyên đề Tin học 12: Xác định ma trận kề và danh sách kề của các đồ thị ở Hình 11.11 ....

• Hoạt động 3 trang 53 Chuyên đề Tin học 12: Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính. Thảo luận xem cách nào ....

• Câu hỏi trang 55 Chuyên đề Tin học 12: Thiết lập bộ dữ liệu biểu diễn gồm (n, V, E, A, Adj) cho các đồ thị sau ....

• Luyện tập 1 trang 55 Chuyên đề Tin học 12: Đồ thị ứng với mô hình bài toán 7 cây cầu ở Königsberg có phải là đơn đồ thị không ....

• Luyện tập 2 trang 55 Chuyên đề Tin học 12: Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên ....

• Vận dụng 1 trang 55 Chuyên đề Tin học 12: Đồ thị vô hướng G được gọi là đầy đủ nếu giữa hai đỉnh bất kì (khác nhau) ....

• Vận dụng 2 trang 55 Chuyên đề Tin học 12: Đồ thị trong Hình 11.17 có bao nhiêu thành phần liên thông? ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---