Câu hỏi:
26/06/2024 112
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?
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?
Câu hỏi trong đề:
Giải chuyên đề Tin 12 KNTT Bài 11: Khái niệm đồ thị có đáp án !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
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.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Đồ thị vô hướng G được gọi là đầy đủ nếu giữa hai đỉnh bất kì (khác nhau) đều có cạnh nối. Hãy vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n = 2, 3, 4.
Đồ thị vô hướng G được gọi là đầy đủ nếu giữa hai đỉnh bất kì (khác nhau) đều có cạnh nối. Hãy vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n = 2, 3, 4.
Xem đáp án »
11/07/2024
332
Câu 2:
Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên.
Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên.
Xem đáp án »
11/07/2024
328
Câu 3:
Vẽ đồ thị vô hướng G = (V, E) sau:
V = [0, 1, 2, 3, 4]
E = [{0,1}, {0,4}, {1,2}, {1,3}, {2,4}]
Vẽ đồ thị vô hướng G = (V, E) sau:
V = [0, 1, 2, 3, 4]
E = [{0,1}, {0,4}, {1,2}, {1,3}, {2,4}]
Xem đáp án »
26/06/2024
244
Câu 6:
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 là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.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 là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12.
Xem đáp án »
11/07/2024
159
về câu hỏi!